автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Построение многосторонних мультилинейных алгоритмов в условиях различных моделей безопасности

На правах рукописи

Косолапое Дмитрий Олегович

ПОСТРОЕНИЕ МНОГОСТОРОННИХ МУЛЬТИЛИНЕЙНЫХ АЛГОРИТМОВ В УСЛОВИЯХ РАЗЛИЧНЫХ МОДЕЛЕЙ БЕЗОПАСНОСТИ I

05.13.18 - математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Владивосток 2010

2 5 НОЯ 2010

004613604

Работа выполнена на кафедре информационной безопасности Дальневосточного государственного университета

Научный руководитель:

доктор физико-математических наук, профессор КОРНЮШИН Павел Николаевич

Официальные оппоненты:

доктор физико-математических наук, профессор НУРМИНСКИЙ Евгений Алексеевич

доктор физико-математических наук, профессор СТЕПАНОВА Алёна Андреевна

Ведущая организация:

Морской государственный университет имени адмирала Г.И. Невельского (г. Владивосток)

Защита состоится « 10 » декабря 2010 г. в 10:00 часов на заседании диссертационного совета Д 005.007.01 в Институте автоматики и процессов управления ДВО РАН по адресу: 690041, г. Владивосток, ул. Радио, 5.

С диссертацией можно ознакомиться в библиотеке Института автоматики и процессов управления ДВО РАН по адресу: 690041, г. Владивосток, ул. Радио, 5.

Автореферат разослан « 2 » ноября 2010 г.

Ученый секретарь

диссертационного совета Д 005.007.01, к.т.н. ' A.B. Лебедев

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Развитие информационных технологий и средств обработки, хранения и передачи информации привело к необходимости защищать данные на всех этапах информационного обмена. Криптографический уровень защиты информации является своего рода «последней линией обороны», т.к. позволяет защищать информацию даже после получения к ней доступа злоумышленником. При этом обеспечивается определенный уровень криптографической стойкости, т.е. способности криптографического алгоритма противостоять возможным атакам на него. Стойким считается алгоритм, для успешной атаки на который злоумышленнику необходимы недостижимые вычислительные ресурсы, недостижимый объём перехваченных открытых и зашифрованных сообщений или же такое время раскрытия, что по его истечению защищенная информация будет уже не актуальна. Стойкость криптографических алгоритмов доказывается в условиях определенных математических моделей безопасности.

Известны различные виды моделей безопасности, классифицирующиеся по ряду критериев, например, по защищаемому объекту (модели безопасности доступа). Под моделями безопасности криптографических примитивов понимаются формализованные модели поведения вероятного злоумышленника при попытке нарушения стойкости криптографических алгоритмов.

Появление в 1976 г. асимметричной криптографии (У. Диффи и М. Хеллман) значительно расширило возможности криптографии и положило начало разработке большого количества криптографических алгоритмов. С математической точки зрения стойкость асимметричных криптоалгоритмов основана на сложности решения известных математических задач, таких как, например, задач факторизации целого числа и дискретного логарифмирования в конечном поле. Алгоритмы решения данных задач имеют субэкспоненциальную сложность, поэтому при определенных размерах ключей их решение полагается невозможным на современном этапе развития вычислительной техники.

В 90-е гг. XX в. получили распространение асимметричные криптоалгоритмы на основе эллиптических кривых. Данные алгоритмы строятся с помощью преобразования семейства алгоритмов Эль-Гамаля, а их стойкость основана на сложности решения задачи дискретного логарифмирования в группе точек эллиптической кривой. Известно, что задача дискретного логарифмирования в конечном поле не сложнее задачи дискретного логарифмирования в группе точек эллиптической кривой, заданной над конечным полем.

В 2000 г. А. Жу был предложен первый билинейный алгоритм -асимметричный криптоалгоритм ключевого соглашения на основе билинейных спариваний в группе точек эллиптической кривой. Стойкость билинейных

алгоритмов основана на сложности решения билинейных проблем Диффи-Хеллмана. В настоящее время не существует эффективных математических алгоритмов решения данных проблем. С помощью билинейного спаривания также были построены эффективные алгоритмы на основе идентификационных данных - криптоалгоритмы, в которых открытый ключ абонента получается явным образом из его идентификатора.

К настоящему времени разработан ряд билинейных криптографических алгоритмов, таких как: алгоритм шифрования на основе идентификационных данных (Д. Боне, М. Франклин), алгоритм избирательного шифрования (Д. Боне, Г. Крещенцо, Р. Островски, Г. Персиано), алгоритм подписи (Д. Боне, Б. Линн, X. Шахем), алгоритм слепой подписи (А. Болдырева), алгоритм мультиподписи (А. Болдырева), алгоритм короткой подписи (Ф. Занг, Р. Сафави-Наини, В. Сусило), алгоритм распределения ключа (Р. Сакаи, К. Огиши, М. Казахара), алгоритмы шифроподписи на основе идентификационных данных (Д. Мэлони-Ли и Б. Либерт, Д. Квисквотер). Данные алгоритмы обеспечивают безопасность информации при её обмене несколькими абонентами.

В случае группового обмена информацией билинейные криптоалгоритмы могут быть использованы при условии разбиения группы абонентов на подгруппы из нескольких абонентов и последовательного применения данных алгоритмов к каждой подгруппе. Данный метод приводит к повышению вычислительной и связной сложности обеспечения безопасности информации для всей группы.

Для решения задачи обеспечения безопасного группового информационного обмена в 2002 г. Д. Боне и А. Сильверберг были предложены первые мультилинейные алгоритмы - алгоритм ключевого соглашения и алгоритм широковещательного шифрования. В данных алгоритмах было использовано мультилинейное отображение, являющееся обобщением билинейного спаривания до случая п аргументов. Также в 2002 г. Х.К. Ли, Х.С. Ли, Я.Р. Ли было предложено семейство мультилинейных алгоритмов ключевого соглашения. Стойкость данных алгоритмов основана на сложности решения мультилинейных проблем Диффи-Хеллмана.

Предложенные мультилинейные алгоритмы имеют ряд недостатков, связанных со стойкостью, а именно: для алгоритма широковещательного шифрования Д. Боне и А. Сильверберг не показана стойкость к адаптивным атакам с выбором шифротекста, для алгоритмов ключевого соглашения Х.К. Ли, Х.С. Ли, Я.Р. Ли не предусмотрена возможность выявления злоумышленника. Также, для ряда криптографических примитивов (таких, как шифрование на основе идентификационных данных, избирательное шифрование и шифроподпись) до настоящего времени не было предложено групповых (многосторонних) алгоритмов, что усложняет использование данных примитивов для групп абонентов.

Поэтому в настоящее время возникла трудность построения многосторонних алгоритмов, являющихся более эффективными для группы абонентов, чем многократное применение алгоритмов для подгрупп из нескольких абонентов. При этом стойкость данных алгоритмов не должна быть ниже, чем стойкость схемы многократного применения алгоритмов для подгрупп из нескольких абонентов.

Таким образом, тема проводимого в данной работе исследования является актуальной. Из актуальности темы работы следует ее цель.

Целью работы является разработка семейства многосторонних мультилинейных алгоритмов, являющихся доказуемо стойкими в условиях различных моделей безопасности.

Задачи исследования. Для достижения поставленной цели решались следующие задачи:

1) построение математических моделей безопасности многосторонних криптографических примитивов;

2) разработка многосторонних алгоритмов широковещательного шифрования, избирательного шифрования, подписи, слепой подписи, распределения ключа, шифроподписи и ключевого соглашения;

3) доказательство стойкости и оценка сложности разработанных многосторонних алгоритмов.

Научная новизна полученных результатов заключается в следующем.

1) Разработаны более сильные математические модели безопасности для многосторонних криптографических примитивов;

2) Предложены многосторонние мультилинейные алгоритмы, позволяющие использовать билинейные криптографические примитивы в случае большого количества абонентов;

3) Доказаны стойкость к адаптивной атаке с выбранным открытым текстом базового алгоритма широковещательного шифрования на основе идентификационных данных, стойкость к адаптивной атаке с выбранным шифротекстом полного алгоритма широковещательного шифрования на основе идентификационных данных и стойкость алгоритма ключевого соглашения на основе идентификационных данных с выявлением злоумышленника в расширенной модели безопасности ключевого соглашения;

4) Разработаны математические проблемы, обеспечивающие приемлемый уровень сложности для обеспечения стойкости многосторонних алгоритмов.

Методы исследования. В диссертации применяются методы современной алгебры конечных полей, теория вероятностей, теория сложности алгоритмов, математические модели безопасности криптографических примитивов.

Теоретическая и практическая значимость работы. В работе предложены математические модели безопасности широковещательного

шифрования при адаптивной атаке с выбором шифротекста и открытого текста, расширенная модель безопасности ключевого соглашения, многосторонние математические проблемы, проведено строгое доказательство стойкости предложенных криптографических алгоритмов в условиях разработанных математических моделей безопасности.

Использование мультилинейных отображений позволит снизить связную и вычислительную сложность многосторонних алгоритмов, усилив их стойкость. Предложенные мультилинейные алгоритмы могут быть использованы при построении многосторонних криптосистем для обеспечения конфиденциальности и аутентичности информационного обмена группы абонентов.

Апробация результатов. Полученные результаты докладывались на региональной научно-технической конференции «Знание, творчество, профессионализм» (Владивосток, 2005), 3-й и 4-й Международных научно-практических конференциях «Интеллектуальные технологии в образовании, экономике и управлении» (Воронеж, 2006-2007), Региональной конференции студентов, аспирантов и молодых ученых по физике (Владивосток, 2006), конференции «Информационная безопасность в открытом образовании» (Магнитогорск, 2007), 48-й, 50-й и 51-й Всероссийских научных конференциях ТОВМИ (Владивосток, 2005, 2007-2008), Российской школе-семинаре «Синтаксис и семантика логических систем» (Владивосток, 2008), Всероссийских конференциях студентов, аспирантов и молодых ученых по физике ДВГУ (Владивосток, 2007, 2009), XXXIII Дальневосточной математической школе-семинаре имени академика Е.В. Золотова (Владивосток, 2008), Всероссийской научно-технической конференции студентов, аспирантов и молодых ученых (Томск, 2009), семинаре кафедры информационной безопасности ДВГУ (Владивосток, 2009), семинаре Института автоматики и процессов управления ДВО РАН (Владивосток, 2009).

Публикации. По материалам диссертации опубликовано 18 работ, в том числе 2 в журналах, рекомендуемых ВАК.

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения и списка литературы, включающего 67 наименований. Содержание работы изложено на 138 страницах текста. Работа содержит 2 таблицы и 2 рисунка.

СОДЕРЖАНИЕ РАБОТЫ

Во введении рассматривается состояние проблемы на сегодняшний день и актуальность темы исследования, формулируется цель и задачи диссертационной работы, приводится ее краткое содержание.

В первой главе исследуются математические основы билинейных и мультилинейных криптографических алгоритмов, рассматриваются

билинейные и мультилинейные криптографические алгоритмы, предложенные к настоящему времени. Первая глава состоит из 3 разделов.

В первом разделе описываются математические аспекты билинейной криптографии, история билинейных алгоритмов и математические проблемы, на сложности решения которых основана стойкость билинейных алгоритмов.

Во втором разделе рассматриваются базовый и полный билинейные алгоритмы шифрования Боне и Франклина на основе идентификационных данных, алгоритм избирательного шифрования, алгоритм подписи Боне, Линна и Шахема, алгоритм слепой подписи, алгоритм мультиподписи, алгоритм подписи Занга, Сафави-Наини и Сусило, однораундовый алгоритм выработки общего ключа А. Жу, алгоритм распределения ключа Сакаи, Огиши и Казахара, алгоритм шифроподписи Мэлони-Ли и алгоритм шифроподписи Либерта и Квисквотера.

В третьем разделе рассматривается обобщение билинейного спаривания -мультилинейное отображение и предложенные к настоящему времени мультилинейные алгоритмы. Стойкость данных алгоритмов в соответствующих моделях безопасности основана на сложности решения многосторонних мультилинейных математических проблем. ~

Сформулированы следующие и-сторонние математические проблемы, на сложности решения которых основана стойкость многосторонних алгоритмов: и-сторонняя проблема распознавания Диффи-Хеллмана, и-сторонняя вычислительная проблема Диффи-Хеллмана, мультилинейная проблема Диффи-Хеллмана (MDH), проблема инверсии Диффи-Хеллмана и общая проблема Диффи-Хеллмана. --■■

Предложены следующие п -сторонние математические проблемы, на сложности решения которых может быть основана стойкость будущих многосторонних алгоритмов: и-сторонняя слабая проблема Диффи-Хеллмана, обратная и-сторонняя вычислительная проблема Диффи-Хеллмана, обобщенная мультилинейная проблема Диффи-Хеллмана, мультилинейная проблема распознавания Диффи-Хеллмана и мультилинейная проблема распознавания Диффи-Хеллмана для случая хеширования.

л-сторонняя слабая проблема Диффи-Хеллмана заключается в сложности получения набора (*,(?,...,¿„2) по заданному набору (P,Q,s,P,...,snP), где P,QeG, Р - образующий элемент аддитивной циклической группы G простого порядка д, a eZ".

Обратная и-сторонняя вычислительная проблема Диффи-Хеллмана заключается в сложности нахождения ЬР, beZ't, удовлетворяющего равенству а,...а„ =rbmodq по заданному набору (Р,а^Р,...,апР,гР), где , a Р -

образующий элемент аддитивной циклической группы G простого порядка q.

Обобщенная мультилинейная проблема Диффи-Хеллмана (GMDH -General Multilinear Diffie-Hellman problem) заключается в сложности получения

набора (Q,fi(Q'P2>—P^Y'""") по заданному набору (Р,а2Р,агР,...,ап^Р), где

элементы а2,а}.....a„+1sZ'? выбираются случайно, Q,P2.....Pntl - произвольные

элементы аддитивной циклической группы G простого порядка q, Р -образующий элемент группы G,, а ц - п -мультилинейное отображение.

Мультилинейная проблема распознавания Диффи-Хеллмана (DMDH -Decisional Multilinear Diffie-Hellman problem) заключается в сложности проверки равенства г = ц(Р,Р,...,Р)°лпо заданному набору (P,aiP,a1P,...,a„tiP,r), где элементы a1,a2,...,a„+1)reZ' выбираются случайно, Р -образующий элемент аддитивной циклической группы G простого порядка q, а у - п -мультилинейное отображение.

Мультилинейная проблема распознавания Диффи-Хеллмана для случая хеширования (DHMDH - Decisional Hash Multilinear Diffie-Hellman problem)

заключается в сложности проверки равенства г = H{jj{P,P.....по

заданному набору (,Р)а]/>,а2.Р,...,д,,+,Я,г), где tfl,i72,...,antl,reZ'? выбираются случайно, задана хеш-функция Я: G2 , G, - мультипликативная циклическая группа простого порядка q, Р - образующий элемент аддитивной циклической группы G, простого порядка q, а ц - л-мультилинейное отображение.

Во второй главе предложены мультилинейные алгоритмы, полученные с помощью обобщения соответствующих билинейных алгоритмов на мультилинейный случай, рассмотрены возможности построения данных алгоритмов в модели Л-ичного дерева и возможности их использования в случае отсутствия мультилинейных отображений для всех значений п. Вторая глава состоит из 3-х разделов.

В первом разделе построены многосторонние мультилинейные алгоритмы.

Построен базовый мультилинейный алгоритм широковещательного шифрования на основе идентификационных данных (MulBasicIdent). Данный алгоритм решает задачу шифрования сообщения для л абонентов с идентификаторами Ю„...,Юп. Алгоритм представлен этапами инициализации, получения закрытого ключа, шифрования и расшифрования.

Пусть ке 2 - принимаемый алгоритмом на этапе инициализации параметр стойкости. Этап инициализации представлен следующими процедурами.

1. На основе к Центром генерации закрытых ключей (PKG) генерируется простой порядок q групп G, и G2, 2л-мультилинейное отображение yu:G1xG1x...xGl ->G2 и произвольный образующий элемент группы

2«

PeG,, где G, - аддитивная циклическая группа, a G2 - мультипликативная циклическая группа.

2. Центром РКХЗ случайным образом выбираются элементы л,,...,.$„ е 2* и вычисляется набор открытых ключей = = .г„/\

3. Центром РКС выбираются криптографические хеш-функции Я,: {О,I}' -> <7" и Я2: {0,1}' для некоторого /е2, где {0,1}' - множество двоичных векторов произвольной длины, а {0,1}' - множество двоичных векторов длины I.

В данном алгоритме пространства сообщений и шифротекстов представляют собой множества .9 = {0,1}' и С = (?,"х {0,1}' соответственно, элементы л,,...,^ являются мастер-ключами абонентов, а системными параметрами является набор (с?,, Сг, /, Л ,..., , Я,, Я2).

Особенностью алгоритмов на основе идентификационных данных является необходимость получения абонентом закрытого ключа у Центра РКС. На этапе получения закрытого ключа проводятся следующие вычисления:

1) для идентификаторов абонентов /£>,,...,/£>„ е{0,1}' Центром РКХЗ вычисляются = Я,(Ю,)£= Я,(/0„)еС,';

2) Центром РКЙ вычисляются и передаются абонентам по защищенному каналу закрытые ключи ¡1Щ = .....= , ^ еС,, где

........ - мастер-ключи.

На этапе шифрования сообщения М с помощью идентификаторов Ю1,...,Юп е {0,1}' абонентом выполняются следующие операции:

1) вычисляются = ЯД/О,)еО,,...,^ = Я,(/Ол)еО,";

2) выбирается случайный элемент г е ;

3) вычисляется шифротекст С = (гР,м®Н2 (&'))> где ?=.....аю.'Рр^'—Реиь)^ о;.

Для расшифрования шифротекста С=(и,У) абонентом с идентификатором Ю1 с помощью закрытого ключа </ю е ^ вычисляется открытый текст следующим образом:

)) = М.

Корректность алгоритма подтверждается выполнением следующего равенства, смысл которого сводится к подстановке в аргумент функции Я2 на этапе расшифрования выражений для закрытого ключа Лщ и элемента

и = гР:

>•••> £?я>,_, 1 ^Ш,, '■■■'Ою.'РриЬ, > —> ^риЬ^'У > РриЬм >— '-^>114, ) =

=ма^ ,-,вю,,ррА.....л..., ^ г=у=.

Так как V-М ® Я2(#г), то на этапе расшифрования получаем

На основе алгоритма МиЮаБюИеги с помощью метода Фуджисаки-Окамото построен полный алгоритм широковещательного шифрования на основе идентификационных данных (МиШиНМеп^ МКШОИД).

МКШОИД также представлен этапами инициализации, получения закрытого ключа, шифрования и расшифрования.

Пусть к е 2 - принимаемый алгоритмом на этапе инициализации параметр стойкости. Этап инициализации представлен следующими процедурами.

1. На основе к Центром РКв генерируется простой порядок ? групп О, и 2/7-мультилинейное отображение /и:01х0,х...х01 ->02 и произвольный

2я

образующий элемент группы Р е б,, где ^ - аддитивная циклическая группа, а Сг - мультипликативная циклическая группа.

2. Центром РКХЗ случайным образом выбираются элементы е Ж' и вычисляется набор открытых ключей = 51Р,...,Р^ = з,Р, Р^. еСг

3. Центром РКО выбираются криптографические хеш-функции Я,: (0,1}' -> С,', Я2 :С2 ->{0,1}' для некоторого /е2, Н,: {0,1}'х{0,1}' -лЪ\ и Н4: {0,1}' -»{0,1}'.

В данном алгоритме пространства сообщений и шифротекстов представляют собой множества 3 = {0,1}' и С = С1'х{0,1}'х{0,1}' соответственно, элементы .?,,...,.?„ е2,'ч являются мастер-ключами абонентов, а системными параметрами является набор .

На этапе получения закрытого ключа проводятся следующие вычисления:

1) для идентификаторов абонентов Ю....../£>„€{0,1}' Центром РКХЗ

вычисляются =Я|(/Д)€С1',...,2,д_ = Я,(/£>„)еС";

2) Центром РКХ5 вычисляются и передаются абонентам по защищенному каналу закрытые ключи , с!ю е О,, где

- мастер-ключи.

На этапе шифрования сообщения М с помощью идентификаторов Я),,...,/Оя е {0,1}' абонентом выполняются следующие операции:

1) вычисляются (2,0, = Н,(Ю,)е = Я,(Ю„)е С?,*;

2) выбирается случайный вектор сг € {0,1}', / е 2;

3) вычисляется г = Нъ(а,М), г е ;

4) вычисляется шифротекст С = ^гР,а®Н2^г),М®Н4(а)^, где Я = Я(0,П| ,-Рм,-,-Р^.) е о;.

Для расшифрования шифротекста С ~{и,У,\У) абонентом с идентификатором ю, выполняются следующие процедуры.

1. Если U eG[, то шифротекст не принимается. В противном случае, с помощью закрытого ключа dm е G,' вычисляется:

V ® Н2 МО*,.....Q,0iX. ¿щ. Q!Dm Q,d. ■ Р* ■.... Р„»ьы РМи1,-,РриК )) = <?.

2. Абонентом вычисляется W Ф И,(а) = М.

3. Абонентом вычисляется г = Н} (а-, М), reZT и проверяется U = rP. Если равенство не выполняется, то шифротекст не принимается, в противном случае полагается, что М - открытый текст.

Корректность алгоритма подтверждается аналогично MulBasicIdent.

Помимо алгоритмов широковещательного шифрования на основе идентификационных данных также предложены многосторонние мультилинейные алгоритмы избирательного шифрования, подписи, слепой подписи, распределения ключа и шифроподписи.

Во втором разделе мультилинейный алгоритм подписи построен в модели к -ичного дерева.

В третьем разделе исследована возможность использования мультилинейных алгоритмов в случае отсутствия мультилинейных отображений для всех значений п. В данном случае возможна модификация алгоритмов добавлением фиктивных абонентов до ближайшего возможного значения п. После этапа инициализации алгоритма первые п-r абонентов берут на себя функции эмуляции недостающих абонентов, где п - ближайшее допустимое количество абонентов, а г - реальное количество абонентов, п > г.

В третьей главе построены математические модели безопасности широковещательного шифрования, доказана стойкость предложенных алгоритмов MulBasicIdent и MulFullIdent (МКШОИД) в условиях данных моделей и проведена оценка вычислительной сложности всех предложенных в главе 2 криптографических алгоритмов. Третья глава состоит из 3-х разделов.

В первом разделе рассмотрены существующие модели безопасности, вычислительные модели, модели злоумышленников и типы проводимых атак.

Во втором разделе построены математические модели безопасности, в условиях которых проводится доказательство стойкости алгоритмов широковещательного шифрования. Модели безопасности широковещательного шифрования основаны на играх, проводимых злоумышленником (атакующим алгоритмом) с запросчиком (challenger).

Игра злоумышленника, проводящего атаку на алгоритм широковещательного шифрования, состоит из процедуры инициализации, 2-х этапов проведения запросов, постановки задачи и вывода результата.

Во время инициализации запросчик принимает параметр стойкости к е N, запускает процедуру инициализации алгоритма, передает атакующему алгоритму параметры params и сохраняет мастер-ключи master-keys в секрете. Определены G, - аддитивная циклическая группа простого порядка q с

образующим элементом Р, и - мультипликативная циклическая группа простого порядка ц.

На этапе I атакующий алгоритм генерирует запросы ...,?„ и отправляет их запросчику, где является:

1) запросом закрытого ключа {/£>,'). В данном случае запросчик запускает процедуру генерации закрытого ключа е б,, соответствующего открытому ключу (#>,), и передает атакующему алгоритму.

2) запросом расшифрования (Ю'„С,'). В данном случае запросчик запускает процедуру генерации закрытого ключа с1\, соответствующего открытому ключу (Щ)- Далее запускает процедуру расшифрования шифротекста С/ с помощью <1[ и передает полученный открытый текст атакующему алгоритму.

Данные запросы проводятся адаптивно, т.е. каждый запрос может зависеть от ответов на запросы .

После завершения этапа 1 атакующий алгоритм генерирует 2 открытых

текста Ма, Л/, е 9 равной длины и набор идентификаторов абонентов /£>,...../£>„,

для которых он проводит атаку, где 9 - множество открытых текстов произвольной длины. Единственным ограничением является тот факт, что Ю^Ю] при / = 1,...,л,у = 1,...,от во время этапа 1.

Постановка задачи запросчика атакующему алгоритму имеет следующий вид. Запросчик случайно выбирает бит бе {0,1} и отправляет Сь = Епсгур1(рагат5, Ю,.....Юп,Мь) алгоритму.

На этапе 2 атакующий алгоритм генерирует и отправляет запросчику дополнительные запросы где q¡ является:

1) запросом закрытого ключа (Щ)> гДе Ю^Ю) для / = 1,...,/!,/ = т+1,...,/. Запросчик отвечает так же, как и во время этапа 1.

2) запросом расшифрования где (/£>], С])ф(ю„С,) для / = 1,..., л, / =/и+ 1,...,/. Запросчик отвечает так же, как и во время этапа 1.

Данные запросы могут проводиться адаптивно, как и во время этапа 1.

В качестве результата атакующий алгоритм возвращает бит ¿'€{0,1} и выигрывает игру, если 6 = 6'.

Выигрышем при проведении атаки злоумышленника А на алгоритм Е называется следующая функция параметра стойкости к е N:

AdveAk)-

Pr[6 = 6']-i

где Pr[i = 6'] - вероятность события, состоящего в

совпадении значений битов Ъ и Ь'.

Атакующий алгоритм в определенной выше игре называется П"Ш-ГОВ-ССА злоумышленником. Если для всех полиномиальных во времени ШБ-ГОВ-

CCA злоумышленников А, способных проводить запросы закрытого ключа и расшифрования на алгоритм Е, функция AdvEil(k) является пренебрежимо малой, то определенная выше игра является математической моделью безопасности широковещательного шифрования при адаптивной атаке с выбором шифротекста, а алгоритм Е в условиях данной модели является IND-IDB-CCA стойким (семантически стойким к адаптивной атаке с выбором шифротекста). В современной криптографии при построении алгоритмов шифрования проводится доказательство их стойкости в модели безопасности при адаптивной атаке с выбором шифротекста. Данная атака является самой сильной среди существующих атак на алгоритмы шифрования.

Злоумышленник А, способный проводить только запросы закрытого ключа, называется IND-IDB-CPA злоумышленником. Если для всех полиномиальных во времени IND-IDB-CPA злоумышленников А, способных проводить запросы закрытого ключа на алгоритм Е, функция AdvEA(k) является пренебрежимо малой, то игра атакующего алгоритма и запросчика является математической моделью безопасности широковещательного шифрования при адаптивной атаке с выбором открытого текста, а алгоритм Е в условиях данной модели является IND-IDB-CPA стойким (семантически стойким к адаптивной атаке с выбором открытого текста).

Автором работы доказана стойкость алгоритма MulBasicIdent в условиях математической модели безопасности широковещательного шифрования при адаптивной атаке с выбором открытого текста и предположении сложности мультилинейной проблемы Диффи-Хеллмана (MDH).

Для доказательства IND-IDB-CCA стойкости алгоритма MulFuHIdent доказана IND-CPA стойкость связанного алгоритма MulBasicPub - алгоритма широковещательного шифрования с открытым ключом (не использующего идентификационных данных). MulBasicPub состоит из 3-х процедур -генерации ключа, шифрования и расшифрования.

На этапе генерации ключа по заданному параметру стойкости ке Ъ* алгоритмом выполняется:

1) запускается генератор С и на основе к генерируются 2 группы GVG1 простого порядка q и 2 л -мультилинейное отображение fj:GlxGlx...xGl ->G,, выбирается произвольный образующий элемент группы

2л

PeG<;

2) случайным образом выбираются элементы i,.....sn е Ъ\ и

вычисляются =stP,...,PpllK =s„P, далее случайным образом выбираются Qrn,.....Qrn, eG,';

3) выбирается криптографическая хеш-функция Н2 :G, {0,1}" для некоторого »sN;

4) возвращается открытый ключ абонента с индексом г - набор (яА'02>М>п,Р,ррщ,С!ю1>нг) изакрытыйключ а1П = ев;.

Для шифрования сообщения Ме{0,1}' выбирается случайный элемент

геЪ\ и вычисляется шифротекст С = (гР,М®Нг(£г)}, где * = ..........

Для расшифрования шифротекста С-(и,У) ¡-м абонентом С помощью закрытого ключа ¿т е б,' вычисляется:

у@н2ш101...............я „„.))=л/.

Доказательство стойкости алгоритма МиШаБгсРиЬ следует из следующей леммы.

Лемма 3.4 Пусть Нг ->{0,1}" - случайный оракул, где » е N, а А - 1Ш>-СРА злоумышленник, имеющий выигрыш е{к) при атаке на МиЮаБюРиЬ. Предположим, что А выполняет в общем > 0 запросов к Нг для каждого абонента, дИ е N. Тогда существует алгоритм В, решающий проблему МБН для генератора С с выигрышем не менее 2пе(к) / ^ и временем работы не более 0(п*Нте(А)), где и - количество абонентов, а Нте(А) - время работы злоумышленника А.

С помощью данной леммы и ряда утверждений доказана стойкость алгоритма МиШиНИеШ (МКШОИД) в условиях математической модели безопасности широковещательного шифрования при адаптивной атаке с выбором шифротекста и предположении сложности ГуГОН. Следующая теорема представляет собой один из основных результатов диссертации.

Теорема 3.7 В предположении, что хеш-функции н„нг,н„н, являются случайными оракулами, алгоритм МиШиНМеШ является 1М)-ГОВ-ССА стойким при предположении сложности проблемы МБН в генерируемых генератором в группах. Пусть существует 1>Ш-ШВ-ССА злоумышленник А, имеющий для каждого абонента выигрыш при атаке на МиШиНИеп!, и А проводит

атаку за время, не превышающее >(к) е К, где к е N - параметр стойкости. Пусть А выполняет не более дЕ е N запросов закрытого ключа, не более е N запросов расшифрования и не более еН запросов к оракулам

#2,Я3,Н, соответственно. Тогда существует алгоритм В, решающий МБН для генератора О, со временем выполнения /,(£) е К, при этом для его выигрыша и времени выполнения справедливы следующие неравенства:

АсЫсл{к)>Ъ&О,,А| Ф) ,?„,,?„ ]/<?„, , /,(к) <п(/(*),Чн>,д),

\е(\ + Че+Ч[>) ) 1

где

РО^(ф\?„,,д^,д0) = —--гМк)+ 1)0-2/-1),

2(Я„, +Ян,)

Щщ, «*). Чн, -<?»,) = + 0(iq,u + q,h )w),

п - количество абонентов, ws N - длина а.

Доказательство теоремы основано на последовательном применении доказанных утверждений и леммы. Возможность проведения атаки IND-IDB-ССА злоумышленником на алгоритм MulFullIdent с выигрышем с(к) и временем t(k) приводит к возможности проведения атаки IND-CCA

злоумышленником на алгоритм MulBasicPubhy с выигрышем с' >-^- и

еЦ + Яс + Я»)

временем t' < 0(t) (утверждение 3.9). В свою очередь, возможность проведения атаки IND-CCA злоумышленником на алгоритм MulBasicPubhy с выигрышем s' и временем t' приводит к возможности проведения атаки IND-CPA злоумышленником на алгоритм MulBasicPub с выигрышем £"*FO^(e',qH),qHi,qD) и временем t"<FOtlm{t',qHt,qHi) (утверждение 3.8). Возможность проведения атаки IND-CPA злоумышленником на алгоритм MulBasicPub с выигрышем е" и временем t" приводит к возможности решения мультилинейной проблемы Диффи-Хеллмана с выигрышем e">2hs" / q,h и

временем t" < 0(nt") (лемма 3.4).

Из приведенных выше утверждений получена оценка выигрыша злоумышленника при решении проблемы MDH и его времени работы:

е(к)

е">2пе"lq„ >2nFO^e',qH q„ ,qD)/q„ ZlnFO^—--—<Чн,,Чн,.10)'Ч„,,

e(l + qE + qD)

tmS0{nt") < nFO„m,(t',qH>,qHi)< nFO,imm,qH.,?„,)■

Теорема доказана.

В сравнении с предложенным Боне и Сильверберг алгоритмом мультилинейного широковещательного шифрования предложенный алгоритм МКШОИД является более безопасным, т.к. обладает стойкостью к самому сильному типу атак злоумышленника.

В третьем разделе проведена оценка вычислительной эффективности предложенных в главе 2 мультилинейных алгоритмов. Показано, что МКШОИД является вычислительно и связно более эффективным, чем последовательное применение аналогичного по стойкости билинейного алгоритма Боне и Франклина.

В четвертой главе предложен алгоритм аутентифицированного ключевого соглашения на основе идентификационных данных и проведено доказательство стойкости алгоритма в расширенной модели безопасности ключевого соглашения.

В первом разделе рассмотрены результаты Х.К. Ли, Х.С. Ли, Я.Р. Ли, полученные в 2002 г.

Во втором разделе построен алгоритм ключевого соглашения. Алгоритм представлен процедурами инициализации, генерации и рассылки закрытых ключей, публикации, выработки ключа и верификации.

На этапе инициализации проводится генерация параметров алгоритма. Пусть (/[ и G2 - мультипликативные циклические группы одинакового простого порядка p,a g - образующий элемент группы G,. Пусть заданы 2 хеш-функции

Я,: {0,1}* -* G," и Я2: G," -> Z'p. Пусть Ю.....,/£>„ - идентификаторы п абонентов

Л,.....А„, вырабатывающих общий секретный ключ. Пусть е„_{: G"'1 -» G2 - (л-1)-

мультилинейное отображение.

На этапе генерации и рассылки закрытых ключей для каждого абонента с идентификатором ID, (l<i<л) Центром PKG вычисляется открытый ключ ß4=tf,(/4)6G,. Далее Центром PKG генерируется набор случайных целых

чисел i,.....s„ е[1,/)-1], являющихся мастер-ключами абонентов. По данным

мастер-ключам Центром PKG вычисляется набор открытых ключей

РрЛ =g"=("'(/A)'l,.....P^gKWieG» набор долгосрочных закрытых ключей

dIDi =Я,(Ю|)'|,...,^;о_ = Я, (/£),)'■ oG, и каждому абоненту передается его долгосрочный закрытый ключ по защищенному каналу.

На этапе публикации каждым абонентом А, выбирается случайное целое число а, е[1,р-1] и вычисляется g"1 е G,. А, рассылает всем остальным абонентам краткосрочный открытый ключ g"1, а at сохраняет в секрете.

На этапе выработки ключа по полученным значениям и идентификаторам i -м абонентом вычисляется набор открытых ключей Q,a = Я, (/£),) е G, (1 < / < п). Далее вычисляется ключ следующего вида

~ »-iVs 'r„h,.......rPubH>8 [">!>„,<■">

Процедура верификации заключается в следующем. Выработанный ключ каждый абонент зашифровывает с помощью своего идентификатора (например, билинейным алгоритмом шифрования Боне и Франклина) и отправляет полученное значение Центру генерации закрытых ключей PKG. Центр PKG расшифровывает полученные значения и проверяет равенство всех выработанных ключей. В случае равенства Центр PKG широковещательно рассылает всем абонентам сигнальное сообщение одобрения передачи. В случае обнаружения одного или более ключей, не совпадающих с другими ключами, Центр PKG широковещательно рассылает сообщение отказа передачи и идентификаторы абонентов, являющихся злоумышленниками.

Автором работы предложена расширенная модель безопасности ключевого соглашения и доказана стойкость построенного алгоритма ключевого соглашения в условиях данной модели.

Теорема 4.1 Предложенный алгоритм ключевого соглашения является стойким к атакам активного злоумышленника в расширенной модели

безопасности ключевого соглашения при предположении сложности мультилинейной проблемы Диффи-Хеллмана и доверия к Центру генерации закрытых ключей.

В заключении диссертационной работы приводятся основные и дополнительные результаты исследований, проводится обоснование целесообразности использования математического аппарата мультилинейных отображений при построении многосторонних криптосистем будущего,

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

1. Построено семейство многосторонних алгоритмов с применением математического аппарата мультилинейных отображений, а именно, алгоритмы широковещательного шифрования на основе идентификационных данных, избирательного шифрования, подписи, слепой подписи, шифроподписи, ключевого соглашения на основе идентификационных данных с возможностью выявления злоумышленника.

2. Разработаны математические модели безопасности и математические проблемы, на сложности решения которых может быть основана стойкость многосторонних алгоритмов будущего.

3. Доказано, что алгоритм МКШОИД обладает стойкостью к адаптивным атакам с выбором шифротекста при предположении сложности проблемы МЭН. Для обеспечения безопасного группового обмена информацией алгоритм МКШОИД является вычислительно и связно более эффективным, чем многократное применение билинейного алгоритма Боне и Франклина.

4. Предложен алгоритм ключевого соглашения на основе идентификационных данных. Преимуществом данного алгоритма является использование идентификационных данных абонентов и возможность выявления злоумышленника во время выполнения алгоритма. Показана стойкость предложенного алгоритма ключевого соглашения в расширенной модели безопасности ключевого соглашения. Проведена программная реализация алгоритма для случая 3-х абонентов.

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Гончаров С.М., Косолапое Д.О., Харин Е.А. Выработка уникальных псевдослучайных последовательностей на основе клавиатурного почерка // Научно-практическая конференция «Информационная безопасность в открытом образовании». Тезисы докладов. - Магнитогорск: МаГУ, 2007. - С. 65-66.

2. Гончаров С.М., Косолапов Д.О., Харин Е.А. Мультилинейная схема шифрования Боне-Франклина на основе идентификационных данных // Научно-

практическая конференция «Информационная безопасность в открытом образовании». Тезисы докладов. - Магнитогорск: МаГУ, 2007. - С. 67-69.

3. Гончаров С.М., Косолапов Д.О. Использование мультилинейных отображений для построения безопасных систем группового обмена данными // Российская школа-семинар «Синтаксис и семантика логических систем». Тезисы докладов. - Владивосток: Изд-во Дальнаука, 2008. - С. 13-16.

4. Корнюшин П.Н., Гончаров С.М., Косолапов Д.О. Схема короткой групповой подписи в модели k-ичного дерева // Материалы 51-й всероссийской научной конференции. - Владивосток: ТОВМИ, 2008. - С. 79-81.

5. Косолапов Д.О., Гончаров С.М., Корнюшин П.Н. Хеш-цепи в многосторонних платежах // Материалы XLVIII Всероссийской межвузовской научно-технической конференции. - Владивосток: ТОВМИ, 2005. - С. 75-76.

6. Косолапов Д.О. Многосторонние микроплатежи и ведение счета клиента в мобильной сети // Сборник докладов региональной научно-технической конференции «Знание, творчество, профессионализм». -Владивосток: МГУ им. адм. Г.И. Невельского, 2005. - С. 418-422.

7. Косолапов Д.О., Гончаров С.М., Корнюшин П.Н. Криптосистемы на основе идентификационных данных для обеспечения безопасности информационного обмена в мобильной телефонии // Материалы 3-й Международной Научно-практической конференции «Интеллектуальные технологии в образовании, экономике и управлении». - Воронеж: ВИЭСУ, 2006.-С. 271-273.

8. Косолапов Д.О., Гончаров С.М. Оптимизация билинейного Тейт-спаривания в группе точек эллиптической кривой на базе алгоритма Миллера // Региональная конференция студентов, аспирантов и молодых ученых по физике. Тезисы докладов. - Владивосток: ДВГУ, 2006. - С. 168-169.

9. Косолапов Д.О. Возможности построения криптосистем на основе мультилинейных форм // Всероссийская конференция студентов, аспирантов и молодых ученых по физике. 14-16 ноября 2007. Материалы конференции. -Владивосток: ДВГУ, 2007. - С. 120-121.

10. Косолапов Д.О., Гончаров С.М., Корнюшин П.Н. Мультилинейные отображения и возможности построения новых криптосистем // Материалы 50-й Всероссийской научной конференции. Т. 2. - Владивосток: ТОВМИ, 2007. -С. 39-40.

11. Косолапов Д.О., Корнюшин П.Н. Обобщение билинейных криптосистем шифрования и подписи // Материалы IV международной научно-практической конференции «Интеллектуальные технологии в образовании, экономике и управлении 2007». - Воронеж: ВИЭСУ, 2007. - С. 285-288.

12. Косолапов Д.О., Гончаров С.М. Групповая мультилинейная схема электронно-цифровой подписи // XXXIII Дальневосточная математическая школа-семинар имени академика Е.В. Золотова: тезисы докладов. -Владивосток: Изд-во Дальнаука, 2008. - С. 18.

13. Косолапов Д.О., Харин Е.А., Гончаров С.М., Корнюшин П.Н. Генерация ключевых последовательностей на основе рисунка радужной оболочки глаза // Проблемы правовой и технической защиты информации: сб. научных статей. - Барнаул: Изд-во Алт. Ун-та, 2008. - С. 145-150.

14. Косолапов Д.О., Харин Е.А., Гончаров С.М., Корнюшин П.Н. Использование рисунка радужной оболочки глаза для генерации ключевой пары // Доклады Томского государственного университета систем управления и радиоэлектроники, 2(18), часть 1. - Томск: Изд-во ТГУСУР, 2008. - С. 30-31.

15. Косолапов Д.О., Харин Е.А., Гончаров С.М., Корнюшин П.Н. Мультилинейные протоколы в асимметричной криптографии // Доклады Томского государственного университета систем управления и радиоэлектроники, 2(18), часть 1. - Томск: Изд-во ТГУСУР, 2008. - С. 51-53.

16. Косолапов Д.О., Харин Е.А., Корнюшин П.Н. Мультилинейные криптосистемы шифрования, подписи и распределения ключей // Проблемы правовой и технической защиты информации: сб. научных статей. - Барнаул: Изд-во Алт. Ун-та, 2008. - С. 116-120.

17. Косолапов Д.О., Гончаров С.М., Корнюшин П.Н. Протокол ключевого соглашения на основе идентификационных данных с возможностью выявления злоумышленника // Всероссийская конференция студентов, аспирантов и молодых ученых по физике. 27-29 апреля 2009. Материалы конференции. -Владивосток: ДВГУ, 2009. - С. 109-111.

18. Косолапов Д.О. Протокол ключевого соглашения на основе идентификационных данных с возможностью выявления злоумышленника // Материалы докладов Всероссийской научно-технической конференции студентов, аспирантов и молодых ученых 12-15 мая 2009 г, Тематический выпуск «Системная интеграция и безопасность», ч. 3. - Томск: В-Спектр, 2009. - С. 277-283.

Личный вклад автора. Все основные результаты, представленные в диссертационной работе, получены автором самостоятельно. Работы [6, 9, 18] выполнены автором самостоятельно. В работах [2-5, 7, 8, 10-12, 15-17] автор участвовал в постановке проблемы, провел необходимые теоретические исследования, связанные с построением математических моделей безопасности и разработкой мультилинейных алгоритмов, и соответствующие вычисления, связанные с доказательством стойкости предложенных алгоритмов для решения задачи обеспечения безопасности группового информационного обмена. В работах [1, 13, 14] автор сформулировал возможность использования в многосторонних алгоритмах ключевых последовательностей на основе клавиатурного почерка и рисунка радужной оболочки глаза.

/

Косолапое Дмитрий Олегович

ПОСТРОЕНИЕ МНОГОСТОРОННИХ МУЛЬТИЛИНЕЙНЫХ АЛГОРИТМОВ В УСЛОВИЯХ РАЗЛИЧНЫХ МОДЕЛЕЙ БЕЗОПАСНОСТИ

Автореферат

Подписано в печать Усл. печ. л. 1,0. Уч.-изд. л. 0,83

Формат 60x84/16 Тираж 100 экз. Заказ 32.

Издано ИАПУ ДВО РАН, г. Владивосток ул. Радио, 5 Отпечатано участком оперативной печати ИАПУ ДВО РАН г. Владивосток ул. Радио, 5

Список обозначений.

Введение.

Глава 1. Теоретические аспекты билинейных и мультилинейных алгоритмов.

1.1 Основы билинейной криптографии.

1.2 Билинейные алгоритмы.

1.2.1 Алгоритм шифрования Боне и Франклина на основе идентификационных данных.

1.2.2 Алгоритм избирательного шифрования.

1.2.3 Алгоритм подписи Боне, Линна и Шахема.

1.2.4 Алгоритм слепой подписи.

1.2.5 Алгоритм мультиподписи.

1.2.6 Алгоритм 788 короткой подписи.

1.2.7 Однораундовый алгоритм трехстороннего ключевого соглашения Антуана Жу.

1.2.8 Алгоритм распределения ключа Сакаи, Огиши и Казахара.

1.2.9 Алгоритм шифроподписи Мэлони-Ли.

1.2.10 Алгоритм шифроподписи Либерта и Квисквотера.

1.3 Мультилинейные отображения и алгоритмы.

Глава 2. Построение мультилинейных алгоритмов.

2.1 Мультилинейные алгоритмы.

2.1.1 Мультилинейные алгоритмы широковещательного шифрования. на основе идентификационных данных.

2.1.2 Мультилинейный алгоритм избирательного шифрования.

2.1.3 Мультилинейные алгоритмы подписи.

2.1.4 Мультилинейный алгоритм слепой подписи.

2.1.5 Мультилинейный алгоритм распределения ключа.

2.1.6 Мультилинейные алгоритмы шифроподписи.

2.2 Мультилинейные алгоритмы в модели к -ичного дерева.

2.2.1 Алгоритмы ключевого соглашения в модели к -ичного дерева.

2.2.2 Мультилинейный алгоритм подписи в модели А:-ичного дерева.

2.3 Возможности построения мультилинейных алгоритмов.

Глава 3. Стойкость мультилинейных алгоритмов.

3.1 Модели безопасности криптографических примитивов.

3.2 Стойкость мультилинейных алгоритмов широковещательного шифрования на основе идентификационных данных.

3.3 Вычислительная эффективность мультилинейных алгоритмов.

Глава 4. Алгоритм ключевого соглашения на основе идентификационных данных. 110 4.1 Алгоритмы многостороннего аутентифицированного ключевого соглашения Ли

Развитие информационных технологий и средств обработки, хранения и передачи информации привело к необходимости защищать данные на всех этапах информационного обмена. Для обеспечения защиты информации необходимо обеспечить ее конфиденциальность, целостность и доступность.

Защиту данных можно осуществлять правовыми и организационно-техническими методами. Организационно-технические методы представлены физическим, аппаратным, программным и математическим (криптографическим) уровнями. Криптографический уровень защиты информации является своего рода «последней линией обороны», т.к. позволяет защищать информацию даже после получения к ней доступа злоумышленником. При этом обеспечивается определенный уровень криптографической стойкости, т.е. способности криптографического алгоритма противостоять возможным атакам на него. Стойким считается алгоритм, для успешной атаки на который злоумышленнику необходимы недостижимые вычислительные ресурсы, недостижимый объём перехваченных открытых и зашифрованных сообщений или же такое время раскрытия, что по его истечению защищенная информация будет уже не актуальна. Стойкость криптографических алгоритмов доказывается в условиях определенных математических моделей безопасности.

Известны различные виды моделей безопасности, классифицирующиеся по ряду критериев, например, по защищаемому объекту (модели безопасности доступа). Под моделями безопасности криптографических примитивов понимаются формализованные модели поведения вероятного злоумышленника при попытке нарушения стойкости криптографических алгоритмов.

Появление в 1976 г. асимметричной криптографии (У. Диффи и М. Хеллман) значительно расширило возможности криптографии и положило начало разработке большого количества криптографических алгоритмов. С математической точки зрения стойкость асимметричных криптоалгоритмов основана на сложности решения известных математических задач, таких как, например, задач факторизации целого числа и дискретного логарифмирования в конечном поле. Алгоритмы решения данных задач имеют субэкспоненциальную сложность, поэтому при определенных размерах ключей их решение полагается невозможным на современном этапе развития вычислительной техники.

Примерами асимметричных алгоритмов являются стандарт США на цифровую подпись DSS (Digital Signature Standard) и российские стандарты на ЭЦП ГОСТ Р34.10 94 и ГОСТ Р34.10 2001.

В 90-е гг. XX в. получили распространение асимметричные криптоалгоритмы на основе эллиптических кривых. Данные алгоритмы строятся с помощью преобразования семейства алгоритмов Эль-Гамаля, а их стойкость основана на сложности решения задачи дискретного логарифмирования в группе точек эллиптической кривой. Известно, что задача дискретного логарифмирования в конечном поле не сложнее задачи дискретного логарифмирования в группе точек эллиптической кривой, заданной над конечным полем.

В 2000 г. А. Жу был предложен первый билинейный алгоритм -асимметричный криптоалгоритм ключевого соглашения на основе билинейных спариваний в группе точек эллиптической кривой. Стойкость билинейных криптоалгоритмов основана на сложности решения билинейных проблем Диффи-Хеллмана. В настоящее время не существует эффективных математических алгоритмов решения данных проблем. С помощью билинейного спаривания также были построены эффективные алгоритмы на основе идентификационных данных -криптоалгоритмы, в которых открытый ключ абонента получается явным образом из его идентификатора. Криптоалгоритмы на основе идентификационных данных позволяют упростить инфраструктуру открытых ключей.

К настоящему времени разработан ряд билинейных криптографических алгоритмов, таких как: алгоритм шифрования на основе идентификационных данных (Д. Боне, М. Франклин), алгоритм избирательного шифрования (Д. Боне, Г. Крещенцо, Р. Островски, Г. Персиано), алгоритм подписи (Д. Боне, Б. Линн, X. Шахем), алгоритм слепой подписи (А. Болдырева), алгоритм мультиподписи (А. Болдырева), алгоритм короткой подписи (Ф. Занг, Р. Сафави-Наини, В. Сусило), алгоритм распределения ключа (Р. Сакаи, К. Огиши, М. Казахара), алгоритмы шифроподписи на основе идентификационных данных (Д. Мэлони-Ли и Б. Либерт, Д. Квисквотер). Данные алгоритмы обеспечивают безопасность информации при её обмене несколькими абонентами.

В случае группового обмена информацией билинейные алгоритмы могут быть использованы при условии разбиения группы абонентов на подгруппы из нескольких абонентов и последовательного применения данных алгоритмов к каждой подгруппе. Данный метод приводит к повышению вычислительной и связной сложности обеспечения безопасности информации для всей группы.

Для решения задачи обеспечения безопасного группового информационного обмена в 2002 г. Д. Боне и А. Сильверберг были предложены первые мультилинейные алгоритмы — алгоритм ключевого соглашения и алгоритм широковещательного шифрования. В данных алгоритмах было использовано мультилинейное отображение, являющееся обобщением билинейного спаривания до случая п аргументов. Также в 2002 г. Х.К. Ли, Х.С. Ли, Я.Р. Ли было предложено семейство мультилинейных алгоритмов ключевого соглашения. Стойкость данных алгоритмов основана на сложности решения мультилинейных проблем Диффи-Хеллмана.

Актуальность темы. Предложенные мультилинейные алгоритмы имеют ряд недостатков, связанных со стойкостью, а именно: для алгоритма широковещательного шифрования Д. Боне и А. Сильверберг не показана стойкость к адаптивным атакам с выбором шифротекста, для алгоритмов ключевого соглашения Х.К. Ли, Х.С. Ли, Я.Р. Ли не предусмотрена возможность выявления злоумышленника. Также, для ряда криптографических примитивов „ (таких, как шифрование на основе идентификационных данных, избирательное шифрование и шифроподпись) до настоящего времени не было предложено групповых (многосторонних) алгоритмов, что усложняет использование данных примитивов для групп абонентов.

Поэтому в настоящее время возникла трудность построения многосторонних алгоритмов, являющихся более эффективными для группы абонентов, чем многократное применение алгоритмов для подгрупп из нескольких абонентов. При этом стойкость данных алгоритмов не должна быть ниже, чем стойкость схемы многократного применения алгоритмов для подгрупп из нескольких абонентов.

Таким образом, тема проводимого в данной работе исследования является актуальной. Из актуальности темы работы следует ее цель.

Цель работы. Разработка семейства многосторонних мультилинейных алгоритмов, являющихся доказуемо стойкими в условиях различных моделей безопасности.

Решаемые задачи. Для достижения поставленной цели решались следующие задачи:

1. построение математических моделей безопасности многосторонних криптографических примитивов;

2. разработка многосторонних алгоритмов широковещательного шифрования, избирательного шифрования, подписи, слепой подписи, распределения ключа, шифроподписи и ключевого соглашения;

3. доказательство стойкости и оценка сложности разработанных многосторонних алгоритмов.

Научная новизна полученных результатов заключается в следующем.

1. Разработаны более сильные математические модели безопасности для многосторонних криптографических примитивов;

2. Предложены многосторонние мультилинейные алгоритмы, позволяющие использовать билинейные криптографические примитивы в случае большого количества абонентов;

3. Доказаны стойкость к адаптивной атаке с выбранным открытым текстом базового алгоритма широковещательного шифрования на основе идентификационных данных, стойкость к адаптивной атаке с выбранным шифротекстом полного алгоритма широковещательного шифрования на основе идентификационных данных и стойкость алгоритма ключевого соглашения на основе идентификационных данных с выявлением злоумышленника в расширенной модели безопасности ключевого соглашения;

4. Разработаны математические проблемы, обеспечивающие приемлемый уровень сложности для обеспечения стойкости многосторонних алгоритмов.

Основными результатами данной работы являются следующие результаты.

1. Построено семейство многосторонних алгоритмов с применением математического аппарата мультилинейных отображений, а именно, алгоритмы широковещательного шифрования на основе идентификационных данных, избирательного шифрования, подписи, слепой подписи, шифроподписи, ключевого соглашения на основе идентификационных данных с возможностью выявления злоумышленника.

2. Разработаны математические модели безопасности и математические проблемы, на сложности решения которых может быть основана стойкость многосторонних алгоритмов будущего.

3. Доказано, что алгоритм МКШОИД обладает стойкостью к адаптивным атакам с выбором шифротекста при предположении сложности проблемы 1УГОН. Для обеспечения безопасного группового обмена информацией алгоритм МКШОИД является вычислительно и связно более эффективным, чем многократное применение билинейного алгоритма Боне и Франклина.

4. Предложен алгоритм ключевого соглашения на основе идентификационных данных. Преимуществом данного алгоритма является использование идентификационных данных абонентов и возможность выявления злоумышленника во время выполнения алгоритма. Показана стойкость предложенного алгоритма ключевого соглашения в расширенной модели безопасности ключевого соглашения. Проведена программная реализация алгоритма для случая 3-х абонентов.

В данной работе также были получены дополнительные результаты.

1. Проведена оценка вычислительной эффективности всех предложенных алгоритмов.

2. Алгоритм подписи построен в модели к -ичного дерева.

3. Исследована возможность использования мультилинейных алгоритмов в случае невозможности построения п -мультилинейных отображений для любых значений п.

Научная апробация. Полученные результаты докладывались на региональной научно-технической конференции «Знание, творчество, профессионализм» (Владивосток, 2005), 3-й и 4-й Международных научно-практических конференциях «Интеллектуальные технологии в образовании, экономике и управлении» (Воронеж, 2006-2007), Региональной конференции студентов, аспирантов и молодых ученых по физике (Владивосток, 2006), конференции «Информационная безопасность в открытом образовании» (Магнитогорск, 2007), 48-й, 50-й и 51-й Всероссийских научных конференциях ТОВМИ (Владивосток, 2005, 2007-2008), Российской школесеминаре «Синтаксис и семантика логических систем» (Владивосток, 2008), Всероссийских конференциях студентов, аспирантов и молодых ученых по физике ДВГУ (Владивосток, 2007, 2009), XXXIII Дальневосточной математической школе-семинаре имени академика Е.В. Золотова (Владивосток, 2008), Всероссийской научно-технической конференции студентов, аспирантов и молодых ученых (Томск, 2009), семинаре кафедры информационной безопасности ДВГУ (Владивосток, 2009), семинаре Института автоматики и процессов управления ДВО РАН (Владивосток, 2009).

Публикации. По материалам диссертации опубликовано 18 работ, в том числе 2 в журналах, рекомендуемых ВАК.

1. Гончаров С.М., Косолапов Д.О., Харин Е.А. Выработка уникальных псевдослучайных последовательностей на основе клавиатурного почерка // Информационная безопасность в открытом образовании, под ред. Е.В. Зеркиной, Г.Н. Чусавитиной. — Магнитогорск: МаГУ, 2007. - С. 65-66.

2. Гончаров С.М., Косолапов Д.О., Харин Е.А. Мультилинейная схема шифрования Боне-Франклина на основе идентификационных данных // Информационная безопасность в открытом образовании, под ред. Е.В. Зеркиной, Г.Н. Чусавитиной. — Магнитогорск: МаГУ, 2007. - С. 67-69.

3. Гончаров С.М., Косолапов Д.О. Использование мультилинейных отображений для построения безопасных систем группового обмена данными // Российская школа-семинар «Синтаксис и семантика логических систем». Тезисы докладов. - Владивосток: Изд-во Дальнаука, 2008. - С. 13-16.

4. Корнюшин П.Н., Гончаров С.М., Косолапов Д.О. Схема короткой групповой подписи в модели k-ичного дерева // Материалы 51-й всероссийской научной конференции. - Владивосток: ТОВМИ, 2008. - С. 79-81.

5. Косолапов Д.О., Гончаров С.М., Корнюшин П.Н. Хеш-цепи в многосторонних платежах // Материалы XLVIII Всероссийской межвузовской научно-технической конференции. - Владивосток: ТОВМИ, 2005. - С. 75-76.

6. Косолапов Д.О. Многосторонние микроплатежи и ведение счета клиента в мобильной сети // Сборник докладов региональной научно-технической конференции «Знание, творчество, профессионализм». - Владивосток: МГУ им. адм. Г.И. Невельского, 2005. - С. 418-422.

7. Косолапов Д.О., Гончаров С.М., Корнюшнн П.Н. Криптосистемы на основе идентификационных данных для обеспечения безопасности информационного обмена в мобильной телефонии // Материалы 3-й Международной Научно-практической конференции «Интеллектуальные технологии в образовании, экономике и управлении». - Воронеж: ВИЭСУ, 2006. - С. 271-273.

8. Косолапов Д.О., Гончаров С.М. Оптимизация билинейного Тейт-спаривания в группе точек эллиптической кривой на базе алгоритма Миллера // Региональная конференция студентов, аспирантов и молодых ученых по физике. Тезисы докладов. -Владивосток: ДВГУ, 2006. - С. 168-169.

9. Косолапов Д.О. Возможности построения криптосистем на основе мультилинейных форм // Всероссийская конференция студентов, аспирантов и молодых ученых по физике. 14-16 ноября 2007. Материалы конференции. -Владивосток: ДВГУ, 2007. - С. 120-121.

10. Косолапов Д.О., Гончаров С.М., Корнюшин П.Н. Мультилинейные отображения и возможности построения новых криптосистем // Материалы 50-й Всероссийской научной конференции. Т. 2. - Владивосток: ТОВМИ, 2007. - С. 39-40.

11. Косолапов Д.О., Корнюшин П.Н. Обобщение билинейных криптосистем шифрования и подписи // Материалы IV международной научно-практической конференции «Интеллектуальные технологии в образовании, экономике и управлении 2007». - Воронеж: ВИЭСУ, 2007. - С. 285-288.

12. Косолапов Д.О., Гончаров С.М. Групповая мультилинейная схема электронно-цифровой подписи // XXXIII Дальневосточная математическая школа-семинар имени академика Е.В. Золотова: тезисы докладов. - Владивосток: Изд-во Дальнаука, 2008. - С. 18.

13. Косолапов Д.О., Харин Е.А., Гончаров С.М., Корнюшин П.Н. Генерация ключевых последовательностей на основе рисунка радужной оболочки глаза // Проблемы правовой и технической защиты информации: сб. научных статей. -Барнаул: Изд-во Алт. Ун-та, 2008. - С. 145-150.

14. Косолапов Д.О., Харин Е.А., Гончаров С.М., Корнюшин П.Н. Использование рисунка радужной оболочки глаза для генерации ключевой пары // Доклады Томского государственного университета систем управления и радиоэлектроники, 2(18), часть 1. - Томск: Изд-во ТГУСУР, 2008. - С. 30-31.

15. Косолапов Д.О., Харин Е.А., Гончаров С.М., Корнюшин П.Н. Мультилинейные протоколы в асимметричной криптографии // Доклады Томского государственного университета систем управления и радиоэлектроники, 2(18), часть 1. - Томск: Изд-во ТГУСУР, 2008. - С. 51-53.

16. Косолапов Д.О., Харин Е.А., Корнюшин П.Н. Мультилинейные криптосистемы шифрования, подписи и распределения ключей // Проблемы правовой и технической защиты информации: сб. научных статей. - Барнаул: Изд-во Алт. Унта, 2008. - С. 116-120.

17. Косолапов Д.О., Гончаров С.М., Корнюшин П.Н. Протокол ключевого соглашения на основе идентификационных данных с возможностью выявления злоумышленника // Всероссийская конференция студентов, аспирантов и молодых ученых по физике. 27-29 апреля 2009. Материалы конференции. - Владивосток: ДВГУ, 2009.-С. 109-111.

18. Косолапов Д.О. Протокол ключевого соглашения на основе идентификационных данных с возможностью выявления злоумышленника // Материалы докладов Всероссийской научно-технической конференции студентов, аспирантов и молодых ученых 12-15 мая 2009 г, Тематический выпуск «Системная интеграция и безопасность», ч. 3. - Томск: В-Спектр, 2009. - С. 277-283.

Личный вклад автора. Все основные результаты, представленные в диссертационной работе, получены автором самостоятельно. Работы [6, 9, 18] выполнены автором самостоятельно. В работах [2-5, 7, 8, 10-12, 15-17] автор участвовал в постановке проблемы, провел необходимые теоретические исследования, связанные с построением математических моделей безопасности и разработкой мультилинейных алгоритмов, и соответствующие вычисления, связанные с доказательством стойкости предложенных алгоритмов для решения задачи обеспечения безопасности группового информационного обмена. В работах [1, 13, 14] автор сформулировал возможность использования в многосторонних алгоритмах ключевых последовательностей на основе клавиатурного почерка и рисунка радужной оболочки глаза.

Теоретическая и практическая значимость работы. В работе предложены математические модели безопасности широковещательного шифрования при адаптивной атаке с выбором шифротекста и открытого текста, расширенная модель безопасности ключевого соглашения, многосторонние математические проблемы, проведено строгое доказательство стойкости предложенных криптографических алгоритмов в условиях разработанных математических моделей безопасности.

Использование мультилинейных отображений позволит снизить связную и вычислительную сложность многосторонних алгоритмов, усилив их стойкость. Предложенные мультилинейные алгоритмы могут быть использованы при построении многосторонних криптосистем для обеспечения конфиденциальности и аутентичности информационного обмена группы абонентов.

Методы исследования. В диссертации применяются методы современной алгебры конечных полей, теория вероятностей, теория сложности алгоритмов, математические модели безопасности криптографических примитивов.

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения и списка литературы, включающего 67 наименований. Содержание работы изложено на 138 страницах текста. Работа содержит 2 таблицы и 2 рисунка.

Заключение

В связи со значительным расширением масштабов информационного обмена актуальной является разработка стойких и эффективных многосторонних алгоритмов, т.е. алгоритмов, осуществляющих криптографическое преобразование для группы абонентов. Предложенное Боне и Сильвербсрг обобщение билинейного спаривания -мультилинейное отображение, позволяет упростить большинство многосторонних алгоритмов и построить некоторые из них на основе соответствующих билинейных алгоритмов.

Данные мультилинейные алгоритмы явились предметом исследования в данной работе.

Перечислим основные результаты диссертации:

1. Построено семейство многосторонних алгоритмов с применением математического аппарата мультилинейных отображений, а именно, алгоритмы широковещательного шифрования на основе идентификационных данных, избирательного шифрования, подписи, слепой подписи, шифроподписи, ключевого соглашения на основе идентификационных данных с возможностью выявления злоумышленника.

2. Разработаны математические модели безопасности и математические проблемы, на сложности решения которых может быть основана стойкость многосторонних алгоритмов будущего.

3. Доказано, что алгоритм МКШОИД обладает стойкостью к адаптивным атакам с выбором шифротекста при предположении сложности проблемы МБН. Для обеспечения безопасного группового обмена информацией алгоритм МКШОИД является вычислительно и связно более эффективным, чем многократное применение билинейного алгоритма Боне и Франклина.

4. Предложен алгоритм ключевого соглашения на основе идентификационных данных. Преимуществом данного алгоритма является использование идентификационных данных абонентов и возможность выявления злоумышленника во время выполнения алгоритма. Показана стойкость предложенного алгоритма ключевого соглашения в расширенной модели безопасности ключевого соглашения. Проведена программная реализация алгоритма для случая 3-х абонентов.

Перечислим дополнительные результаты диссертации.

1. Проведена оценка вычислительной эффективности всех предложенных алгоритмов.

2. Проведен анализ возможности использования мультилинейных алгоритмов с учетом результата Боне и Сильверберг о построении мультилинейных отображений высоких порядков мультилинейности.

3. Мультилинейный алгоритм подписи построен в модели /с-ичного дерева.

Все результаты, представленные в диссертационной работе, получены автором самостоятельно. Лемма 3.4, теоремы 3.1, 3.7 и 4.1 сформулированы и доказаны автором диссертации. Автором диссертации показана корректность использования для мультилинейного случая утверждений 3.2, 3.3, 3.5, 3.9, 3.10 и 3.11. Остальные утверждения, используемые в работе, были сформулированы и доказаны другими авторами.

Из дополнительных результатов наиболее важным является оценка возможности построения мультилинейных алгоритмов из условия невозможности построения г -мультилинейных отображений для любых порядков мультилинейности г. Возможна модификация существующих мультилинейных алгоритмов добавлением фиктивных абонентов до ближайшего возможного значения г. После этапа инициализации алгоритма первые г-п абонентов берут на себя функции эмуляции недостающих абонентов, где г - ближайшее допустимое количество абонентов, п -реальное количество абонентов, г>п.

Также один из предложенных алгоритмов мультилинейной подписи был реализован в модели к -ичного дерева. На его примере можно сделать вывод о том, что аналогичным образом в модели А:-ичного дерева можно построить и другие мультилинейные алгоритмы, предложенные в диссертации и многосторонние мультилинейные алгоритмы, которые будут разрабатываться в будущем.

Результаты проведенной работы позволяют построить эффективную и безопасную систему многостороннего обмена информацией для группы абонентов, что является актуальной задачей в области информационной безопасности настоящего времени.

Использование мультилинейных криптографических отображений позволит значительно уменьшить связную сложность многосторонних алгоритмов, сократив объем передаваемой информации, и потенциально может снизить вычислительную сложность алгоритмов при построении эффективно вычислимых мультилинейных отображений. До настоящего времени не удалось построить криптографические мультилинейные отображения со степенью мультилинейности выше 2. Исследования по разработке таких отображений являются одним из предметов дальнейших научных изысканий.

1. Гончаров С.М. Построение протоколов ключевого соглашения криптоконференции на основе к-мультилинейных отображений: Дис. канд. физ.-мат. наук: 05.13.18. Владивосток, 2006. - 113 с.

2. Коршошин П.Н., Гончаров С.М., Косолапов Д.О. Схема короткой групповой подписи в модели к-ичного дерева // Материалы 51-й всероссийской научной конференции. Владивосток: ТОВМИ, 2008. - С. 79-81.

3. Косолапов Д.О. Возможности построения криптосистем на основе мультилинейных форм // Всероссийская конференция студентов, аспирантов и молодых ученых по физике. 14-16 ноября 2007. Материалы конференции. -Владивосток: ДВГУ, 2007. С. 120-121.

4. Косолапов Д.О., Гончаров С.М. Групповая мультилинейная схема электронно-цифровой подписи // XXXIII Дальневосточная математическая школа-семинар имени академика Е.В. Золотова: тезисы докладов. Владивосток: Изд-во Дальнаука, 2008. -С. 18.

5. Косолапов Д.О., Гончаров С.М., Корнюшин П.Н. Мультилинейные отображения и возможности построения новых криптосистем // Материалы 50-й Всероссийской научной конференции. Т. 2. Владивосток: ТОВМИ, 2007. - С. 39-40.

6. Косолапов Д.О., Гончаров С.М., Корнюшин П.Н. Хеш-цепи в многосторонних платежах // Материалы XLVIII Всероссийской межвузовской научно-технической конференции. Владивосток: ТОВМИ, 2005. - С. 75-76.

7. Косолапов Д.О. Многосторонние микроплатежи и ведение счета клиента в мобильной сети // Сборник докладов региональной научно-технической конференции «Знание, творчество, профессионализм». Владивосток: МГУ им. адм. Г.И. Невельского, 2005. - С. 418-422.

8. Косолапов Д.О., Харин Е.А., Гончаров С.М., Корнюшин П.Н. Генерация ключевых последовательностей на основе рисунка радужной оболочки глаза //

9. Проблемы правовой и технической защиты информации: сб. научных статей. -Барнаул: Изд-во Алт. Ун-та, 2008. С. 145-150.

10. Косолапов Д.О., Харин Е.А., Корнюшин П.Н. Мультилинейные криптосистемы шифрования, подписи и распределения ключей // Проблемы правовой и технической защиты информации: сб. научных статей. Барнаул: Изд-во Алт. Ун-та, 2008. - С. 116120.

11. A. Boldyreva. Efficient Threshold Signature, Multisignature and Blind Signature Schemes Based on the Gap-Diffie-Hellman-Group Signature Scheme. PKC 2003, LNCS 2139, pp. 31-46, Springer-Verlag, 2003.

12. A. Fiat and M. Naor. Broadcast encryption, in Proc. Crypto 1993. Lecture Notes in Computer Science 773 (1993), Springer, pp. 480^91.

13. A. J. Scholl. Classical motives, in 64] pp. 401-459.

14. A. Joux. A one round protocol for tripartite Diffie-Hellman, Proc. ANTS IV, Lecture Notes in Computer Science 1838 (2000), pp. 385-394.

15. A. Joux, K. Nguyen. Separating Decision Diffie-Hellman from Diffie-Hellman in cryptographic groups, available from eprint.iacr.org.

16. A. Lysyanskaya. Unique signatures and verifiable random functions from DH-DDH separation, in Proc. Crypto 2002, Lecture Notes in Computer Science 2442 (2002), Springer, pp. 597-612.

17. A. Menezes. Elliptic curve public key cryptosystems, Kluwer Academic Publishers, Boston, MA, 1993.

18. A. Menezes, P.C. van Oorschot, and S. Vanstone. Handbook of Applied Cryptography, CRC Press, Boca Raton, 1997.

19. A. Menezes, T. Okamoto, S. Vanstone. Reducing elliptic curve logarithms to logarithms in a finite field, IEEE Transactions on Information Theory 39 (1993), pp. 1639— 1646.

20. B. Libert, J. J. Quisquater. New Identity Based Signcryption Schemes from Pairings. Cryptology ePrint Archive, Report 2003/023, available at http://eprint.iacr.org/2003/023.

21. C. Becker and U. Willie. Communication complexity of group key distribution, ACM conference on Computer and Communication Society, 1998.

22. C. Gentry and A. Silverberg. Hierarchical ID-Based Cryptography, Proceedings of Asiacrypt 2002, Lecture Notes in Computer Science, Springer-Verlag, 2002.

23. D. Boneh and A. Silverberg. Applications of Multilinear Forms to Cryptography, 2002.

24. D. Boneh, and M. Franklin. Identity-based encryption from the Weil pairing, Crypto'2001, Lecture Notes in Computer Science, Springer-Verlag, 2001.

25. D. Boneh, B. Lynn, and H. Shacham. Short signatures from the Weil pairing, Proc. Asiacrypt 2001, Lecture Notes in Computer Science 2248 (2001), Springer, pp. 514-532.

26. D. Boneh, C. Gentry, B. Lynn and H. Shacham. Aggregate and Verifiably Encrypted Signature from Bilinear Maps. Eurocrypt 2003, LNCS 2248, pp. 514-532, Springer-Verlag, 2003.

27. D. Boneh, G. D. Crescenzo, R. Ostrovsky, G. Persiano. Searchable Public Key Encryption. Cryptology ePrint Archive, Report 2003/195, available at http://eprint.iacr.org/2003/195.

28. D. Boneh. The decision Diffie-Hellman problem, in Proc. ANTS III, Lecture Notes in Computer Science 1423 (1998), Springer, pp. 48-63.

29. D. Naor, M. Naor, J. Lotspiech. Revocation and Tracing Schemes for Stateless Receivers, in Proc. Crypto 2001, Lecture Notes in Computer Science 2139 (2001), pp. 4162.

30. E. Fujisaki, T. Okamoto. Secure Integration of Asymmetric and Symmetric Encryption Schemes. Crypto'99, Lecture Notes in Computer Science, Springer-Verlag 1999.

31. F. Zhang, R. Safavi-Naini and W. Susilo. An Efficient Signature Scheme from Bilinear Pairings and it's Applications. PKC 2004.

32. G. Atenies, M. Steiner, G. Tsudik. Authenticated group key agreement and friends, ACM Conference on Computer and Communications Security, 1998.

33. G. Ateniese, M. Steiner, and G. Tsudik. New Multiparty Authentication Services and Key Agreement Protocols, Journal of Selected Areas in Communications, 18(4): 1-13, IEEE, 2000.

34. G. Frey, Applications of arithmetical geometry to cryptographic constructions, in Finite fields and applications (Augsburg, 1999) (2001), Springer, pp. 128-161.

35. G. Frey, H. Ruck. A remark concerning m-divisibility and the discrete logarithm in the divisor class group of curves, Mathematics of Computation, 62, pp. 865-874, 1994.

36. Ho-Kyu Lee, Hyang-Sook Lee, Young-Ran Lee. Multi-party authenticated key agreement protocols from multilinear forms. Department of Mathematics, Ewha Womans University, Seoul, Korea, 2002.

37. J. Malone-Lee. Identity-Based Signcryption. Cryptology ePrint Archive, Report 2002/098, available at http://www.iacr.org/2002/098.

38. J. Milne. Motives over finite fields, in 54], pp. 401-459.

39. K. Rubin, A. Silverberg. Supersingular abelian varieties in cryptology, in Proc. Crypto 2002, Lecture Notes in Computer Science 2442 (2002), Springer, pp. 336-353.

40. L. Law, A. Menezes, M. Qu, J. Solinas, and S. Vansone. An efficient protocol for authenticated key agreement, Technical Report CORR 98-05, Department of C & O, University of Waterloo, 1998, To appear in Designs, Codes and Cryptography.

41. M. Bellare, P. Rogaway. Random oracles are practical: a paradigm for designing efficient protocols, in ACM Conference on Computers and Communication Security (1993), pp. 62-73.

42. M. Burmester and Y. Desmedt. A Secure and Efficient Conference key Distribution System, Advances in Cryptology-Eurocrypto'94, LNCS, Springer Verlag, pp. 275-286, 1995.

43. M. Stein, G. Tsudik, M. Waidner. Diffie Hellman Key Distribution Extended to Group Communication, ACM conference on computer and communication security, 1996.

44. N. Bourbaki. Elements of mathematics, Algebra II, Chapters 4, Springer, 1990.

45. P. Deligne. La conjecture de Weil. I, Inst. Hautes Etudes Sei. Publ. Math. 43 (1974), pp. 273-307.

46. R. Sakai, K. Ogishi and M. Kasahara. Cryptosystems Based on Pairing. SCIS 2000-c20, Okinawa, Japan, January 2000.

47. Ratna Dutta, Rana Barua, Palash Sarkar. Pairing-Based Cryptography: A survey. Cryptology Research Group, Stat-Math and Applied Statistics Unit 203, B. T. Road, Kolkata. India.

48. S. Goldwasser, R. Ostrovsky. Invariant signatures and non-interactive zero knowledge proofs are equivalent, in Proc. Crypto 1992, Lecture Notes in Computer Science 740 (1992), Springer, pp. 228-244.

49. S. Goldwasser, S. Micali, R. Rivest. A digital signature scheme secure against adaptive chosen message attacks, SLAM J. of Computing, 17, No. 2 (1988), pp. 281-308.

50. S. Micali, M. O. Rabin, S. P. Vadhan. Verifiable random functions, in Proc. 40th IEEE Symposium on Foundations of Computer Science (FOCS) (1999), pp. 120-130.

51. S. Pohlig, M. Hellman. An improved algorithm for computing discrete logarithms over GF(p) and its cryptographic significance, IEEE Transactions on Information Theory 24 (1978), pp. 106-110.

52. Sattam S. Al-Riyami and Kenneth G. Paterson. Authenticated Three Party Key Agreement Protocols from Pairings, Report 2002/035, http://eprint.iacr.org, 2002.

53. T. Matsumoto, Y. Takashima, and H. Imai. On seeking smart public-key-distribution systems, Trans. IECE of Japan, E69:99-106, 1986.

54. U. Jannsen, S. Kleiman, J-P. Serre (eds.). Motives, Proc. Symp. Pure Math., vol. 55, Amer. Math. Soc., 1994, part 1.

55. V. Miller. Short programs for functions on curves, unpublished manuscript.

56. W. Diffie and M. Hellman. New directions in cryptography, IEEE Transactions on Information Theory, IT-2(6): pp. 644-654, 1976.

57. Y. Kim, A. Perrig, and G. Tsudik. Simple and fault-tolerant key agreement for dynamic collaborative groups, In ACM CCS'00, pp. 235-244, ACM press, November 2000.