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

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

Гончаров Сергей Михайлович

ПОСТРОЕНИЕ ПРОТОКОЛОВ КЛЮЧЕВОГО СОГЛАШЕНИЯ КРИПТОКОНФЕРЕНЦИИ НА ОСНОВЕ К-МУЛЬТИЛИНЕЙНЫХ ОТОБРАЖЕНИЙ

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

Автореферат

диссертации на соискание ученой степени кандидата физико-математических наук

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

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

Научный руководитель доктор физико-математических наук,

профессор Корнюшин Павел Николаевич

Официальные оппоненты доктор физико-математических наук,

профессор Катрахов Валерий Вячеславович

кандидат технических наук Волошина Виктория Николаевна

Ведущая организация: Томский государственный университет

систем управления и радиоэлектроники

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

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

Автореферат разослан « 6 » 2006 г.

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

диссертационного совета Д 005.007.01 Pfirt^y А.В.Лебедев

А-

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

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

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

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

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

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

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

РОС. НАЦИОНАЛЬНАЯ БИБЛИОТЕКА С.-Пегербург

ОЭ 20П6.1К1 УЛС.

В протоколе Джо используются билинейные отображения. Наличие практических алгоритмов для построения п-мультилинейных форм позволило бы построить однораундовый протокол (п+1)-стороннего ключевого соглашения. В 2002 году Боне и Сильверберг описали такой протокол, а несколько позже корейские авторы предложили первую аутентифицированную версию такого протокола.

Однораундовый протокол многостороннего ключевого соглашения Боне-Силверберг, основан на существовании п-мультилинейных отображений для больших значений «п» («п» определяется размером группы и может достигать нескольких тысяч). Предполагается маловероятным появление алгоритмов генерации п-мультилинейных отображений для таких значений п в ближайшие годы. В тоже время представляется вполне реальным появление эффективно-вычислимых п-мультилинейных преобразований для малых значений п (п=3,4,5). В связи с этим возникает задача разработки протоколов Мультилинейного Группового Ключевого Соглашения со Структурой Дерева (МГКССД), использующих преимущества к-мультилинейных отображений для малых значений к.

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

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

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

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

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

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

5. Исследование эффективности разработанных протоколов и их сравнение с протоколами, известными ранее.

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

Научная новизна работы состоит в следующем:

1. Разработан оригинальный протокол Мультилинейного Группового Ключевого Соглашения со Структурой Дерева (МГКССД), использующий преимущества Л-мультилинейных отображений для малых значений к и

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

2. Разработаны для случая к-мультилинейных отображений: схемы мультиподписи и объединенной подписи, криптосистемы на основе идентификационных данных (КСОИД), обобщения протокола Ченга-Лиу-Кима.

3. Разработана аутентифицированная версия протокола МГКССД с использованием впервые описанной мультилинейной КСОИД.

4. Разработана доказуемо безопасная в условиях стандартной модели безопасности версия протокола МГКССД с использованием описанной схемы мультилинейной объединенной подписи.

Научная и практическая ценность. В диссертации разработан необходимый аппарат, позволяющий реализовывать преимущества к-мультилинейных отображений для малых значений к при обеспечении безопасности конференцсвязи Описанный в диссертации протокол МГКССД имеет преимущества в связной эффективности по сравнению с известными протоколами ключевого соглашения со структурой дерева. Для частного случая к=2 протокол МГКССД дает сокращение до 40 % от суммарного объема передаваемой по каналам связи информации и проводимых экспоненциирований по сравнению с единственным описанным на настоящий момент протоколом конференцсвязи, использующим билинейные спаривания (протокол Баруа-Дутта-Саркара -«ЕЮ8»). Эффективность протокола МГКССД при к>2 определяется сложностью вычисления конкретных реализаций к-мультилинейного отображения. С учетом предложенной процедуры действий участников при динамическом изменении состава группы, а также возможностей, которые дает структура (к+1)-ичного дерева, протокол МГКССД может дать преимущества в сравнении с любым известным протоколом группового ключевого соглашения. Разработанный в диссертации аппарат, касающийся использования мультилинейных отображений в области информационной безопасности, имеет самостоятельное значение и может быть использован для дальнейших разработок в области информационной безопасности. Часть материалов использована при разработке учебной программы по курсу «Дополнительные главы криптографических протоколов» на кафедре информационной безопасности ДВГУ.

Апробация работы. Основные результаты работы докладывались на Всероссийских межвузовских научно-технических конференциях (Владивосток, 2003-2005гг.), региональных конференциях студентов, аспирантов и молодых ученых (Владивосток, 2003-2004гг.), Всероссийской научной конференции «Проблемы информационной безопасности в системе высшей школы» (Москва, 2006), а также на объединенном семинаре отдела Интеллектуальных систем ИАПУ ДВО РАН и базовой кафедры по ЭВМ ИМКН ДВГУ в ИАПУ ДВО РАН.

Публикация результатов работы. По материалам диссертации опубликовано 14 печатных работ.

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения и списка использованной литературы. Работа изложена на 113 страницах машинописного текста, содержит 10 рисунков и 3 таблицы. Список литературы содержит 74 наименования.

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

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

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

Во второй главе приводится описание базового протокола МГКССД -неаутентифицированной версии Протокола Мультилинейного Группового Ключевого Соглашения со Структурой (к+1)-ичного Дерева. Обсуждаются вопросы безопасности протокола МГКССД против пассивного противника.

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

Основу протокола МГКССД составляют 2 подпротокола (к+1)-стороннего и /-стороннего (/<к+1) ключевого соглашения. Данные подпротоколы разработаны на базе протокола Боне-Сильверберг (к+1) -стороннего ключевого соглашения на основе к-мультилинейного отображения.

/-сторонний вариант протокола позволяет вырабатывать общий ключ между / пользователями на основе к-мультилинейного отображения. При этом первые с2= к+1-с¡1 (с/=|_(£ + 1)//_|) пользователей вырабатывают и рассылают дополнительные ключи g¡= , g,^гgHÍ°'\ ■■■ > я,«,, =gиC'<°'), выступая в роли недостающих виртуальных наборов пользователей с номерами /+/,..., /+С//, а последние 1-с2 пользователей вырабатывают и

рассылают дополнительные ключи g„ g,,/,,.., gl+i4_X)I (на один ключ меньше).

Уровни R

I 2 к+1

k*l I 2 k+l

12 3 ... Мл 1 2

Мс 12 kH I 2 k+l

J 4-

М„ - участников частников Мп- полных наборов пользователей

(левая подгруппа) (средняя подгруппа) (правая подгруппа)

Рис.1 Схема ключевого дерева на основе k-мультилинейного отображения

Ключевое дерево состоит из нескольких уровней, начиная с уровня 0. На каждом уровне располагаются наборы пользователей (НП), которые имеют (или собираются выработать) общий секретный ключ. Наверху (на уровне R) находится единственный общий ключ конференцсвязи. Уровнем ниже находятся к+1 ключей наборов пользователей уровня R-1. И так далее, при понижении уровня количество ключей (и соответственно количество наборов пользователей увеличивается в (к+1) раз). Исключение составляет нулевой уровень. В нем находится m ключей (ш -количество участников конференцсвязи). При этом разбиение на наборы пользователей на нулевом уровне происходит особым образом.

Все участники делятся на 3 подгруппы Л (левая), С (средняя) и П (правая). Некоторые подгруппы могут быть пустыми. Каждый из участников, входящих в левую подгруппу, сам формирует набор пользователей (т.е. набор состоит лишь из одного пользователя). Участники, входящие в правую подгруппу формируют лишь полные наборы пользователей (т.е. наборы, состоящие ровно из к+1 пользователей). Участники, входящие в среднюю подгруппу, формируют неполный набор пользователей (т.е. количество участников в этом наборе 1<Мс<к+1).

Количество уровней (раундов алгоритма) R(m)=[\ogttl т\.

Утверждение 2.1 Для окончательного общего ключа KEY группы из ш участников в протоколе МГКССД справедливо следующее равенство

KEY=s!"> = S=ff(e(g,g, ,gy!""''"" •'""), где R=R(m), m>k+l. При этом все пользователи могут вычислить общий ключ KEY=il"".

Решающая мультилинейная проблема Диффи-Хеллмана для случая хеширования в {С,,С2,е) (DHMDH'):

Для g,g"\ ,g"-*' e Gi (ah...,an,¡g Z'4), односторонней хэш-функции H G2-yZ'4 и re Z* проверить равенство r=H(e(g, ..,g)"' "••') modq.

Сформулирована Проблема решения группового ■ ключевого соглашения на основе (к+ 1)-ичного дерева (ПРГКСОД) для протокола МГКССД и показано, что эта проблема сложна для пассивного противника, сведением сложности этой проблемы к сложности DHMDH-проблемы.

Решающая групповая хешированная мультилинейная проблема Диффи-Хеллмана на основе дерева в (Gt,G1,e): Определить, является ли данное число общим ключом криптоконференции, вычисляемым по протоколу МГКССД.

Теорема 2.2 Если DHMDH проблема в (G,,G2,e) - сложна, тогда общий ключ криптоконференции, сгенерированный в процессе выполнения неаутентифицированного протокола МГКССД, невозможно отличить от случайного числа полиномиальным алгоритмом.

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

Утверждение 2.3 Пусть ключ криптоконференции для т пользователей вычисляется по (к+1)-ичному ключевому дереву с количеством уровней R(m). При добавлении участника необходимо вычислить новые общие ключи лишь для R наборов пользователей в случае ш < (k+l)R, или для R+1 НП в случае m = (k+l)R. ( Заметим, что общее количество НП в ключевом дереве Nnn >2(k+l)R"').

Следствие 2.4 При добавлении нового участника доля НП, для которых необходимо произвести вычисления общего ключа заново, не превышает (R+l)/2(k+l)R"'.

Утверждение 2.5 В протоколе МГКССД операция удаления участника требует проведения до 2 раз большего обьема вычислений по сравнению с операцией добавления участника.

В третьей главе описаны следующие схемы:

- k-мультилинейной мультиподписи;

- к-мультилинейной объединенной подписи

Показано, что эффективно вычисляемое к-мультилинейное отображение е предоставляет алгоритм для решения Ш)#-проблемы

Утверждение 3.1 Если существует ¿-мультилинейное отображение е С" -> 02 , то для кортежа (а, о?, (3, (?) имеем: а=Ь тойц о еф, о?, g, ., g)= е($, а, g,..., ¿), где ц - порядок группы С,, g - генератор группы С/

Следствие 3.2 Если существует А>мультилинейное отображение е- С" -», то £>ЛЯ-проблема в С; - легка.

Следствие 3.3 Если существует А-мультилинейное отображение е в" -> , то С/ - вОН-группа.

Следствие 3 3 позволяет использовать безопасную схему мультиподписи для ООН-групп, предложенную Болдыревой в протоколе МГКССД.

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

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

Подпись Каждый участник данной схемы по имеемому секретному ключу х и сообщению Л/е {0,1} , вычисляет И^Н(М) и Подписью

является ое О/

Проверка По имеемому открытому ключу пользователя рк, сообщению М и подписи а, вычисляется И=Н(М) Подпись считается истинной, если выполняется равенство ^ ^ , g)=e(h, рк, g, , g)

Объединение Для подмножества пользователей ¿с С/, участвующих в генерации объединенной подписи, каждому участнику приписывается индекс / из диапазона 1 <1 </, где 1=\Ц. Каждый пользователь 1!,е /. генерирует подпись а,еСу для сообщения {0,1 }* по своему выбору. Сообщения М, должны быть попарно различны. Вычисляется

Объединенной подписью является сгеСл

Проверка объединения Даны: объединенная подпись о е С( для объединяемого подмножества пользователей £ , проиндексированных, как указано выше, набор подписываемых сообщений {0,1} и открытые ключи рк, еС/ для всех участников и,еЬ

Для проверки подписи выполняются следующие действия: 1. Убедиться, что сообщения М, все различны, отвергнуть подпись в противном случае.

2 Вычислить И,=П(М,) для /<г </, где 1=\Ц. Подпись считается истинной, если выполняется равенство & . = & ■ 8)

Вкратце, суть мультилинейных объединенных подписей следующая. Каждый участник и, вычисляет секретный ключ х, е 2\ и открытый ключ рк,= Подпись пользователя 11, есть о,=И, где И, - хеш-функция от сообщения М,, выбранного пользователем. Объединенная подпись -

о = ]~[ с, = ]~[ А*' Используя свойства мультилинейного отображения,

левосторонней проверкой объединенной подписи является следующая процедура (представлено в развернутом виде):

Ф. 8,8.-. 8)= еЩ А*' ' 8) = П Ф, 8. -.8)х' =Ц Ф» 8* > 8. . 8) = = П, Ф,.рК8. -,8)-

Следующее утверждение свидетельствует о безопасности схемы мультилинейной объединенной подписи.

Утверждение 3.4 Пусть дано мультилинейное отображение е: О" -> О", и для группы в] не существует алгоритма решающего вычислительную проблему Диффи-Хеллмана за время I' с вероятностью не менее £'. Тогда схема мультилинейной объединенной подписи (^Чн,Я8,М,е)-безопасна против существенной подделки в условиях модели с выбранным ключом для всех I и е, удовлетворяющих условиям: £ >е(я5+1Ч)«' и 1<1'-С01(Чн+2Чз+Ы+4) -(N+1),

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

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

Описана аутентифицированная схема ключевого соглашения для мультилинейных криптосистем на основе идентификационных данных. Введено понятие Мультилинейной КриптоСистемы на Основе Идентификационных Данных (МКСОИД). Приведено описание построения и функционирования МКСОИД.

МКСОИД отличается от КСОИД Боне-Франклина использованием:

- мультипликативной группы (общий случай) вместо аддитивной;

- мультилинейного отображения вместо билинейного спаривания;

- генератора группы g на добавляемых координатах мультилинейного отображения.

Проведено обобщение протокола Ченга-Лиу-Кима (использующего билинейные спаривания на эллиптических кривых) на случай мультилинейных КСОИД.

Пусть 1]={1]и. ,1/к+1} - группа из (к+1) участника, которая собирается выработать общий ключ конференцсвязи. Идентификаторы обозначим через ГО/,. ..ГО*., соответственно. В соответствии с

инфраструктурой мультилинейной КСОИД открытыми ключами участников будут Ql=H| (Ю1),..., Q|¡<|= II] (Юкц), а секретными-5/= <2?, ..., •

Пары (<2„ 5,) (где ¡=1,...,к+1) служат долговременными ключами (открытыми и секретными соответственно) участников.

Протокол выработки общего ключа:

1. Каждый участник С/, (¡=1,...,к+1 ) случайным образом вырабатывает кратковременный секретный ключ а,е У.'ч

2. Каждый и, (/=/,...,к+1 ) широковещательно рассылает остальным участникам конференцсвязи : g,= '/', g¡''

3. Каждый и, (/=/,....к+1) проверяет

- £....., g. & & -'¿)

¡м ,„

Вычисляет.....ш,.^,.!,.... gk)a'.

Общим ключом криптоконференции является

Утверждение 3.5. В схеме мультилинейного варианта протокола

Ченга-Лиу-Кима для вычисления произведения (&> •8)

требуется вычислить лишь два мультилинейных отображения.

В аутентифицированной версии протокола МГКССД для мультилинейных КСОИД процедура построения ключевого дерева и вычисления общего ключа остается такой же, как в неаутентифицированной версии протокола. Для аутентификации в процедурах выработки общего ключа для т сторон и (к+1) сторон используется мультилинейный вариант протокола Ченга-Лиу-Кима.

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

- неявная ключевая аутентификация;

- безопасность при скомпрометированном сеансовом ключе;

- (совершенная) безопасность «будущего»-,

- отсутствие деперсонализации ключевой компрометации;

- отсутствие ключевого контроля

Приведено описание доказуемо безопасной схемы ключевого соглашения со структурой дерева на основе к-мультилинейных отображений. Данная версия протокола (МГКССДА2) использует объединенные подписи всех участников набора пользователей под их краткосрочными открытыми ключами.

Общая структура данного протокола совпадает со структурой неаутентифицированной версии протокола UP. Добавления и изменения касаются процедур Key и КеуТ, а также форматов сообщений. Производятся следующие изменения.

Пусть П\, - /-ое выполнение протокола пользователем U j-oe сообщение М, отравляемое для случая П'и имеет вид (У|у[А/|НПу|МНП(Л где 11П,; обозначает набор пользователей с представителем U, который отправляет сообщение М в качестве своего j-го сообщения, а МНП,/ обозначает множество наборов пользователей, которым U отправляет свое j-ое сообщения М.

Участники группы выполняют неаутентифицированную версию протокола со следующими добавлениями:

- Предположим, что в случае я; сообщение Щ\ М] НП(; |МНП;у (где ü - это представитель набора пользователей НП(/ для случая П'и ) посылается как часть протокола неаутентифицированного ключевого соглашения. В аутентифицированной версии это действие заменяется следующими операции:

- каждый пользователь U¡ НП(/ вычисляет au¡-S(SKui, l\j\ M\ru¡);

- каждый пользователь f/в НП^ посылает U¡\ Ощ\ гщ\ {Ui}\{U}\j\M, где М есть j-ое сообщение пользователя U;

- пользователь U (представитель) вычисляет объединенную подпись a=AS{{?Ku„ 1\]\М\Ги„ аи(У/еППу}) и посылает ЩМ\о\\ти ¡МНПу!/)-^ :

НП,/}. Подпись от пользователей IJ¡* U не проверяется пользователем U Если такая подпись неверна, это выяснится во время проверки объединенной подписи. Заметим, что сообщение, подписанное пользователем U¡ е НПу , есть 1[]\М\гиг Следовательно, для l¡ * 12, сообщения, подписанные l¡i¡ и U¡2 - различны.

Когда П\ (Те МНП,у) получает сообщение í/l/'¡M|ff|Hnw ¡МНПу|{/•[/,: С/,еНПу}, он проверяет:

- £/е pid'¡,;

- j есть следующий по порядку ожидаемый номер (в неаутентифицированной версии протокола) для сообщения от U,

-АЩ РК,У/: С//6 НП„}, {l\)\M\rlH : и^Ши},о)=\.

П[ прерывает выполнение протокола, если хотя бы одно из этих требований не выполняется. Для каждого непрерванного случая n'¡, вычисляется общий ключ криптоконференции, также как и в неаутентифицированной версии.

Показано, что неаутентифицированный протокол МГКССД безопасный против пассивного противника может быть преобразован в протокол группового ключевого соглашения безопасный по отношению к

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

Теорема 3.6. Протокол МГКССДА2 с использованием объединенной подписи является протоколом группового ключевого соглашения безопасным против активного противника. При этом справедливы следующие неравенства: Успеху {X,Кв,К0) <

С2

&сиех£(Ь-Н2, Кв+Ко/2)+ |Р ¡Успех\ Успех^Ь)

где /;+<2<1+(|Р | Кв+ К0) 1ар, 1А/' - время необходимое для выполнения протокола АР произвольным пользователем, Кв, Ко - количество запросов к оракулам «Выполнить» и «Отправить» соответственно

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

Пусть Щт) обозначает общее количество раундов, М(т) - общее количество вычисляемых к-мультилинейных отображений; В(т) -суммарный объем, передаваемой по каналам связи, информации; Е(т) -общее количество экспоненциирований в группе О,. Если пользователь открыто посылает элемент С/ всем или некоторым пользователям, то это засчитывается как единица информации в суммарном объеме В(т) Таким образом, В(т) - общее количество таких групповых элементов.

Утверждение 4.1 Для т>к справедливы следующие соотношения и границы для Щт), В(т), Е(т), Р(т)

1. Щт)=\\о%^т\

2. В(т)=I; В0>(т) , В0)(т)= (кг!)"'1 для 1=1,...,Я-1,

В<0>(т)=

т-(к +1)"

(к+1),

к

Для ключевого дерева высоты 11(т)=\\о^^1 т~\

, . т-1 (£ + 1)

к+- <В(т)< ---т

к к

3. Е(т)= В(т) , к+— < Е(т)<

к к

4 М(т)=£ ^(т); М(0(т)=т для 1=1, ,/?-/, 1-0

М<0>(т)= М,7 (к+1) + Мс,

ГДС Мп = -Ь-

к

М(т) <m\\ogttim\

, Mc=m-kM„-(k+l)R''.

Пусть Rai(m), Ва1(т), Еа1(т) и Paj(m) обозначения аналогичные неаутентифицированой версии, используемые для случая МКСОИД.

Утверждение 4.2 Для т>к справедливы следующие соотношения и

границы для Rai(m), Ва/(т), Еа1(т) и Ма/(т) I Ra,(m) = R(m)=\\ogbl т\

2. Ва](т) = 2В(т) Следовательно

Для ключевого дерева высоты R(m)=[\ogltl т~\

2[k+^fl] <Ва,(т) < 2тМ к к

3. Количество различных жепоненциирований Е'а,(т)=4 Е(т)

Для количества жепоненциирований с учетом повторяемых вычислений различными пользователями справедливо следующее: Еа/т)< m(k\logitl т}+4+ l/k)+const(k)

При т»к асимптотической границей сверху для Е а](т) является

km(logk ,т)

4 Ма,(т) = £ Ма®(т),

Ма'°(т)=5 М0>(т)=5т для i=l, .,R-1, Ма<щ(т)-- MainW) (k+l)+ Ма/п>, М1Ч(т) <5 mfiogM m~\+const, СопЫ= Mainm(k+l)^Malcm-5m При m-'-'k асимптотической границей сверху для Ма/(т) является 5m(logk+,m)

При анализе эффективности протокола МГКССДА2 ограничимся подсчетом количества специальных подписей, так как конкретное число экспоненциирований, мультилинейных отображений и других операций определяется конкретной схемой реализации объединенной подписи.

Утверждение 4.3 Для доказуемо безопасной аутентифицированной версии Сслучай использования объединенной подписи) справедливо следующее

1 Количество раундов в протоколе равно Ra2 (т) = 2R(m)-\- 2|~1ogw m]-l.

2. В данном протоколе дополнительно (по сравнению с неаутентифицированной версией) передаются n[R(m)-l] подписей под соответствующими сообщениями, содержащими общий открытый ключ

НП. Из них [-----1] являются мультилинейными объединенными

к

подписями, остальные \тЩт) - ^ + ^—- ] являются индивидуальными

к

подписями

Производится сравнение версий протокола МГКССД с известными протоколами выработки общего секретного ключа группы участников по открытым каналам связи.

Таблица 1: Сравнение протоколов (неаутентифицированные версии)

Жп) В(п) Е(п) М(п),Р(п) 1пу

ВО 2 2п п(п+1) - п

оон-з п+1 3(п-1) 5п-6 - -

тсон Г1оё2 «1 пГ'оёз "1 пГ'оёг"! - -

ВОБ Г'°Вз "1 <5/2(п-1) <5/2(п-1) -

МГКССД к (¿ + 1) <---п к ^Г'оё».. «1

Замечания по поводу неаутентифицированных протоколов Связная (коммуникационная) сложность измеряется посредством Щп) и В(п), и протокол МГКССД достигает минимума для обеих функций среди всех известных протоколов, кроме ЕЮ протокола. Вычислительная сложность протокола МГКССД состоит из двух частей экспоненцирования и к-мультилинейного отображения. Количество экспоненциирований меньше, чем в других протоколах, но требуется дополнительно п п\ к-мультилинейных отображений. В значительной степени вычислительная сложность МГКССД определяется сложностью вычисления к-мультилинейных отображений.

Для частного случая к=2 протокол МГКССД дает сокращение до 40 % от суммарного объема передаваемой по каналам связи информации и проводимых экспоненциирований по сравнению с единственным протоколом конференцсвязи, использующим билинейные спаривания (протокол Баруа-Дутта-Саркара - «ВББ»).

Таблица 2. Сравнение аутентифицированных версий протоколов

В(п) Е(п) М(п)Дп) 1пу Ми1

БА-вОШ п п2 п2 - п 2 п2- 2п

ГО-АСКА пГ1оёг«1 2п[1оё2я] - -

ВОБа <5(п-1) <9(п-1) - -

МГКССДа, <2„(* + 1) к к - -

Замечания по поводу аутентифицированных протоколов: Количество раундов и суммарный объем сообщений в протоколе МГКССДд] меньше в сравнении с другими протоколами. Количество экспоненциирований (и скалярных умножений на эллиптических кривых для соответствующих протоколов) в МГКССДм также меньше, чем в других протоколах. При этом требуется вычисление «5n[logt+1 п\ к-муль-тилинейных отображений, что для существенно меньше количества спариваний необходимых для протоколов ID-AGKA и BDSA.

В отношении вычислительной сложности доказуемо безопасных версий протоколов заметим' BD требует от каждого участника выполнения 0(n\ogri) модульных умножений и проверки O(ri) подписей, В05д требует от каждого участника вычисления flog, п\ подписей, МГКССДдгтребует от каждого участника вычисления [log,,, т~\ подписей.

Таблица 3. Сравнение протоколов по связной сложности для доказуемо безопасных в стандартной модели версий (СТ-стандартная передача, ШВ-широковещательная передача)

R(n) Объем в сообщениях Объем в битах

(на пользователя) (на пользователя)

Г CT шв CT шв

BD 3 О(п) 3 О(п) O(l)

ВОБд 2 [log, «1-1 0(nlog3n) О flogen ) 0(nlog3n) О (logЗп)

МГКССДдг 2P°gM m]-1 0(nlogk ,n) 0{logk4 n) 0(nlogk4 n) 0(logk+! п)

Как видим, протокол МГКССД и для доказуемо безопасных версий выглядит весьма конкурентоспособно, потенциально имея минимальную вычислительную сложность среди рассматриваемой группы протоколов. Окончательная эффективность протокола МГКССДА2, как и других версий, определяется сложностью вычисления к-мультилинейных отображений.

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

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

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

противника при условии сложности ОНМО /У- п р о б л е м ы в используемой структуре.

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

- схема мультиподписи;

- схема объединенной подписи;

- криптосистемы на основе идентификационных данных (КСОИД);

- обобщение протокола Ченга-Лиу-Кима;

3. Разработана аутентифицированная версия протокола МГКССД с использованием мультилинейной объединенной подписи. Доказана безопасность данного протокола в условиях стандартной модели безопасности.

4. Разработана аутентифицированная версия протокола МГКССД в условиях мультилинейной КСОИД. Показано, что данная версия протокола удовлетворяет всем основным свойствам безопасного протокола группового ключевого соглашения.

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

1. Гончаров С.М., Корнюшин П.Н. О методах асимметричного шифрования перспективных для малоресурсной криптографии // Материалы ХЬУ1 Всероссийской межвузовской научно-технической конференции. Владивосток, ТОВМИ, 2003.-Т.1.- С.51-54.

2. Гончаров С.М., Корнюшин П.Н. О перспективах криптосистемы «ШТШ» // Материалы ХЬУ1 Всероссийской межвузовской научно-технической конференции. Владивосток, ТОВМИ, 2003.-Т.1.- С 55-57.

3. Гончаров С.М., Корнюшин П.Н. О преимуществах криптосистемы «ХТ1Ъ> // Материалы ХЬУ1 Всероссийской межвузовской научно-технической конференции. Владивосток, ТОВМИ, 2003.-Т. 1.- С 61-62

4. Гончаров С.М., Корнюшин П.Н. Алгоритмы решения проблемы дискретного логарифмирования на эллиптической кривой // Материалы ХЬУ1 Всероссийской межвузовской научно-технической конференции Владивосток, ТОВМИ, 2003.-Т. 1,- С.58-59.

5. Гончаров М.С., Гончаров С.М. Криптосистемы на основе идентификационных данных// Региональная конференция студентов, аспирантов и молодых ученых по физике. Тезисы докладов. Владивосток, 2003,- С.62.

6. Гончаров М.С., Гончаров С.М. Мультилинейные криптосистемы на основе идентификационных данных// Региональная конференция студентов, аспирантов и молодых ученых по физике. Тезисы докладов Владивосток, 2004,- С. 109.

7. Гончаров С.М., Корнюшин П.Н. Совместная выработка ключа криптоконференции на основе к-мультилинейных отображений //

Материалы XLVII Всероссийской межвузовской научно-технической конференции. Владивосток, ТОВМИ, 2004.-Т.1,- С.43-45.

8. Гончаров С.М., Корнюшин П.Н. Динамическое изменение состава группы для протокола МГКССД // Материалы XLVII Всероссийской межвузовской научно-технической конференции. Владивосток, ТОВМИ, 2004.-Т.1.- С.46-47

9. Гончаров С.М., Корнюшин П.Н. Доказуемо безопасный протокол мультилинейного группового ключевого соглашения со структурой дерева// Материалы XLVII Всероссийской межвузовской научно-технической конференции. Владивосток, ТОВМИ, 2004.-Т.1.- С.48-49.

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

11 Гончаров С М. Мультиподпись на основе к-мультилинейных отображений. // XIII Всероссийская научная конференция «Проблемы информационной безопасности в системе высшей школы». Сборник научных трудов. М: МИФИ, 2006., стр.40-42.

12 Гончаров С.М. О перспективах развития асимметричных криптосистем с упрощенной инфраструктурой. // XIII Всероссийская научная конференция «Проблемы информационной безопасности в системе высшей школы». Сборник научных трудов. М: МИФИ, 2006., стр.43-44.

1 З.Гончаров С.М., Корнюшин П.Н. Вычисление общего группового ключа с использованием n-мультилинейного отображения./ Системная интеграция и безопасность. Выпуск 1/ Под ред. A.A. Шелупанова,-Томск Издательство Института оптики атмосферы СО РАН, 2006.- С. 113-115.

14 Гончаров СМ., Корнюшин ПН. Объединенная подпись на основе п-мультилинейных отображений /Интеллектуальные системы в управлении, проектировании и образовании:Сб. статей. Выпуск 5 / Под ред А.А.Шелупанова. - Томск: Изд-во Института оптики атмосферы СО РАН, 2006,-С.119-121.

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

Гончаров Сергей Михайлович

ПОСТРОЕНИЕ ПРОТОКОЛОВ КЛЮЧЕВОГО СОГЛАШЕНИЯ КРИПТОКОНФЕРЕНЦИИ НА ОСНОВЕ К-МУЛЬТИЛИНЕЙНЫХ ОТОБРАЖЕНИЙ

Автореферат

Подписано к печати 02.05.06 Усл. печ. л. 1 Уч.-изд. л. 0,8

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

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

Введение

ГЛАВА 1 Проблема многостороннего ключевого соглашения и мультнлинейные отображения

1.1 Понятия и определения.

1.2 Предположения Диффи-Хэллмана

1.3 Однораундовый (п+1)-сторонний обмен ключами но Диффи-Хеллману

ГЛАВА 2 Неаутентифицированный Протокол Мультилинейного Группового Ключевого Соглашения со Структурой (к+1)-ичного Дерева (МГКССД)

2.1 Описание протокола МГКССД

2.2 Безопасность против пассивного противника

2.3 Операции динамического изменения членства группы

ГЛАВА 3 Аутентифицированные версии протокола МГКССД

3.1 Понятия и определения, необходимые для аутентифицированного протокола.

3.2 Аутентифицированная версия протокола с использованием мультиподписи.

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

3.4 Доказуемо безопасная схема ключевого соглашения

ГЛАВА 4 Обсуждение эффективности протокола МГКССД

4.1 Эффективность МГКССД

4.2 Сравнение с известными протоколами 101 Заключение 105 Список использованных источников

ПЕРЕЧЕНЬ СОКРАЩЕНИЙ, УСЛОВНЫХ ОБОЗНАЧЕНИЙ, СИМВОЛОВ, ЕДИНИЦ И ТЕРМИНОВ

0,1 }* - набор всех битовых строк конечной длины.

0,1 }т - набор всех битовых строк конечной длины ш. е\ G" ->G2- n-мультилинейное отображение.

P[D], Prob[D] - вероятность события D.

МГКССД - мультилинейное групповое ключевое соглашение со структурой дерева.

КСОИД - криптосистема на основе идентификационных данных.

ПДЛ - проблема дискретного логарифмирования.

CDH (Computational Dijjie-Hellman) Problem - вычислительная проблема Диффи-Хеллмана.

DDH (Decisional Diffie-Hellman) Problem - решающая проблема Диффи-Хеллмана.

DHMDH-проблема - решающая мультилинейная проблема Диффи-Хэллмана для случая хеширования.

НП - наборы пользователей.

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

TREE KEY - процедура вычисления общего ключа группы участников для протокола МГКССД.

КеуТ, KEY - процедуры вычисления общего ключа для (к+1) участника и I (/<к+1) участников соответственно, используемые в TREE KEY.

ЦСК - Центр Сертификации Ключей.

R(m) - общее количество раундов протокола с т участниками.

М(т) - общее количество вычисляемых k-мультилинейных отображений для протокола с т участниками.

В(т) - суммарный объем информации, передаваемой по каналам связи, для протокола с т участниками.

Е(т) - общее количество экспоненциирований для протокола с т участниками.

Постоянно растущая информатизация и компьютеризация общества приводят к необходимости совершенствования криптографических методов и средств защиты информации. В условиях взаимного недоверия субъектов информационной системы защита обеспечивается на основе методов асимметричной криптографии [2, 3, 4, 6].

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

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

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

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

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

- обоюдная неявная ключевая аутентификация;

- известная ключевая безопасность;

- «безопасность будущего»;

- отсутствие деперсонализации ключевой компрометации;

- ключевой контроль.

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

Предыдущие результаты: как упоминалось ранее, первый двусторонний протокол неаутентифицированного ключевого соглашения был предложен Диффи-Хеллманом в их оригинальной работе [41]. Он был модифицирован в протокол аутентифицированного ключевого соглашения в работе Мацумото, Такшима и Имаи [61]. Позже, в [57] показано, что некоторые из протоколов, описанных в [61], небезопасны и предложен новый протокол аутентифицированного ключевого соглашения. В дальнейшем последовал ряд предложений для аутентифицированного и неаутентифицированного ключевого соглашения [64, 73, 36].

Среди известных многосторонних протоколов ключевого соглашения только два протокола имеют количество раундов меньшее, чем у предлагаемого в диссертации протокола. Боне и Силверберг [29], предложили однораундовый протокол многостороннего ключевого соглашения. Этот протокол основан на существовании п-мультилинейных отображений для больших значений «п» («п» определяется размером группы и может достигать до нескольких тысяч). Предполагается маловероятным появление алгоритмов генерации п-мультилинейных отображений для таких значений п в ближайшие годы. Другой протокол, требующий меньшее количество раундов, предложен Бурмейстером и Десмедтом [34]. Это неаутентифицированный протокол, требующий два раунда. Однако, его вычислительная сложность высока и общее количество возведений в степень составляет порядка п2. Также авторы указывают, что техника доказательства нулевого разглашения требует преобразования этого протокола в аутентифицированный протокол. В 2003 году Кац и Юнг разработали 3-раундовую версию протокола Бурмейстера-Десмедта и доказали ее безопасность [52]. Поэтому на данный момент протокол Бурмейстера-Десмедта (в дальнейшем будем обозначать его протокол ВО) может считаться полноценным лидером по связной эффективности.

Одним из важных направлений развития теории протоколов группового ключевого соглашения является разработка протоколов со структурой дерева. Первоначально разрабатывались протоколы группового ключевого соглашения на основе двоичного дерева с использованием в качестве базового подпротокола модификаций протокола Диффи-Хеллмана [54, 55, 56].

В 2000 году Джо предложил однораундовый трехсторонний протокол ключевого соглашения [50]. Естественным развитием этого революционного результата являются следующие 2 направления.

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

2. В протоколе Джо используются билинейные отображения. Наличие практических алгоритмов для построения п-мультилинейных форм позволило бы построить однораундовый протокол (п+1)-стороннего ключевого соглашения. В 2002 году Боне и Сильверберг [29] описали такой протокол, а несколько позже корейские авторы [58] предложили аутентифицированную версию такого протокола.

Однако задача построения п-мультилинейных отображений в настоящий момент является открытой проблемой. Предполагается маловероятным появление таких алгоритмов для больших значений п в ближайшие годы (напомним, что в нашем случае значение п определяется размером группы, а группы могут быть значительных размеров). В тоже время представляется вполне реальным появление конкретных п-мультилинейных преобразований для малых значений п (п=3,4,5),

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

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

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

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

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

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

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

5. Исследование эффективности разработанных протоколов и их сравнение с протоколами, известными ранее.

На защиту выносятся следующие положения.

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

2. Элементы теории мультилинейной криптографии (с использованием к-мультилинейных отображений), включающие:

- схему мультиподписи;

- схему объединенной подписи;

- криптосистему на основе идентификационных данных (КСОИД);

- обобщение протокола Ченга-Лиу-Кима.

3. Доказуемо безопасная в условиях стандартной модели безопасности аутентифицированная версия протокола МГКССД с использованием мультилинейной объединенной подписи.

4. Аутентифицированная версия протокола МГКССД в условиях мультилинейной криптосистемы на основе идентификационных данных.

Научная новизна работы

1. Разработан оригинальный протокол Мультилинейного Группового Ключевого Соглашения со Структурой Дерева (МГКССД), использующий преимущества к-мультилинейных отображений для малых значений к и обладающий более высокой связной эффективностью по сравнению с протоколами соответствующего класса.

2. Разработаны для случая к-мультилинейных отображений: схемы мультиподписи и объединенной подписи, криптосистемы на основе идентификационных данных (КСОИД), обобщения протокола Ченга-Лиу-Кима.

3. Разработана аутентифицированная версия протокола МГКССД с использованием описанной мультилинейной КСОИД.

4. Разработана доказуемо безопасная в условиях стандартной модели безопасности версия протокола МГКССД с использованием описанной схемы мультилинейной объединенной подписи.

ЗАКЛЮЧЕНИЕ

В диссертации разработан необходимый аппарат, позволяющий реализовывать преимущества А-мультилинейных отображений для малых значений к при обеспечении безопасности конференцсвязи. Описан неаутентифицированный протокол многостороннего ключевого соглашения на основе (к+1)-ичного дерева (МГКССД) с использованием к-мультилинейцого отображения, а также его аутентифицироваиные версии. Протокол МГКССД имеет преимущества в связной эффективности по сравнению с известными протоколами ключевого соглашения со структурой дерева. Для частного случая к=2 протокол МГКССД дает сокращение до

40 % от суммарного объема передаваемой по каналам связи информации и проводимых экспоненциирований по сравнению с единственным описанным на настоящий момент протоколом конференцсвязи, использующим билинейные спаривания (протокол Баруа-Дутта-Саркара - «БОБ»), Эффективность протокола МГКССД при к>2 определяется сложностью вычисления конкретных реализаций к-мультилинейного отображения. С учетом предложенной процедуры действий участников при динамическом изменении состава группы, а также возможностей, которые дает структура (к+1)-ичного дерева, протокол МГКССД может дать преимущества в сравнении с любым известным протоколом группового ключевого соглашения. Разработанный в диссертации аппарат, касающийся использования мультилинейных отображений в криитографии, имеет самостоятельное значение и может быть использован для дальнейших разработок в области информационной безопасности. Ниже перечислены основные результаты диссертационной работы:

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

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

- схема мультиподписи;

- схема объединенной подписи;

- криптосистемы на основе идентификационных данных (КСОИД);

- обобщение протокола Ченга-Лиу-Кима;

3.Разработана аутентифицированная версия протокола МГКССД с использованием мультилинейной объединенной подписи. Доказана безопасность данного протокола в условиях стандартной модели безопасности.

4. Разработана аутентифицированная версия протокола МГКССД в условиях мультилинейной КСОИД. Показано, что данная версия протокола удовлетворяет всем основным свойствам безопасного протокола группового ключевого соглашения.

На момент завершения исследований описанный в диссертации протокол МГКССД может быть реализован при разработке систем закрытой конференцсвязи лишь в частном случае при к=2 с использованием билинейных спариваний на эллиптических кривых. При этом протокол МГКССД дает увеличение связной и вычислительной эффективности до 40 % по сравнению с другими протоколами аналогичного класса. При появлении эффективно вычислимых к-мультилинейных отображений для к>2 протокол МГКССД может быть использован на практике в общем случае, позволяя реализовывать преимущества протокола МГКССД в полном объеме. В наибольшей степени преимущества протокола МГКССД проявляются при создании систем конференцсвязи для больших (>100 участников) групп с динамически изменяемым составом.

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

1. Алферов А.П., Зубов А.10.,Кузьмин А.С.,Черемушкин A.B. Основы криптографии. М.: Гелиос АРВ, 2001.

2. Гончаров С.М., Коршошин П.Н. О методах асимметричного шифрования перспективных для малоресурсной криптографии // Материалы XLVI Всероссийской межвузовской научно-технической конференции. Владивосток, ТОВМИ, 2003.-Т. 1.-С.51-54.

3. Гончаров С.М., Коршошин П.Н. О перспективах криптосистемы «NTRU» // Материалы XLVI Всероссийской межвузовской научно-технической конференции. Владивосток, ТОВМИ, 2003.-Т.1.- С.55-57.

4. Гончаров С.М., Корнюшин П.Н. О преимуществах криптосистемы «XTR» // Материалы XLVI Всероссийской межвузовской научно-технической конференции. Владивосток, ТОВМИ, 2003.-Т. 1,- С.61-62.

5. Гончаров С.М., Корнюшин П.Н. Алгоритмы решения проблемы дискретного логарифмирования на эллиптической кривой // Материалы XLVI Всероссийской межвузовской научно-технической конференции. Владивосток, ТОВМИ, 2003.-Т.1.-С.58-59.

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

7. Гончаров М.С., Гончаров С.М. Криптосистемы на основе идентификационных данных// Региональная конференция студентов, аспирантов и молодых ученых по физике. Тезисы докладов. Владивосток, 2003.- С.62.

8. Гончаров М.С., Гончаров С.М. Мультилинейные криптосистемы на основе идентификационных данных// Региональная конференция студентов, аспирантов и молодых ученых по физике. Тезисы докладов. Владивосток, 2004.- С. 109.

9. Гончаров С.М., Корнюшин П.Н. Совместная выработка ключа криптоконференции на основе k-мультилинейных отображений // Материалы XLVI1 Всероссийской межвузовской научно-технической конференции. Владивосток, ТОВМИ, 2004.-Т.1,- С.43-45.

10. Гончаров С.М., Корнюшин П.Н. Динамическое изменение состава группы для протокола МГКССД // Материалы XLVII Всероссийской межвузовской научно-технической конференции. Владивосток, ТОВМИ, 2004.-Т.1.- С.46-47.

11. И. Гончаров С.М., Корнюшин П.Н. Доказуемо безопасный протокол мультилинейного группового ключевого соглашения со структурой дерева// Материалы XLVII Всероссийской межвузовской научно-технической конференции. Владивосток, ТОВМИ, 2004.-Т.1.- С.48-49.

12. Гончаров С.М. Мультиподпись на основе к-мультилинейных отображений. // XIII Всероссийская научная конференция «Проблемы информационной безопасности в системе высшей школы». Сборник научных трудов. М: МИФИ, 2006., стр.40-42.

13. Гончаров С.М. О перспективах развития асимметричных криптосистем с упрощенной инфраструктурой. // XIII Всероссийская научная конференция

14. Проблемы информационной безопасности в системе высшей школы». Сборник научных трудов. М: МИФИ, 2006., стр.43-44.

15. М. Abdalla, М. Bellare and P. Rogaway. DHIES: An encryption scheme based on the Diffie-Hellman problem, CT-RSA 2001, p. 143-158.

16. G. Ateniese, M. Steiner, and G. Tsudik. New Multiparty Authenticated Services and Key Agreement Protocols, Journal of Selected Areas in Communications, 2000, p. 1-13.

17. R. Barua, R. Dutta, P. Sarkar. Extending Joux's Protocol to Multi Party Key Agreement. Report 2003/062, http://eprint.iacr.org, 2003

18. R. Barua, R. Dutta, P. Sarkar. Pairing-Based Cryptography: A Survey, available at http://eprint.iacr.org/2004/064.

19. R. Barua, R. Dutta, P. Sarkar. Provably Secure Authenticated Tree Based Group Key Agreement Protocol using Pairing . available at http://eprint.iacr.org/2004/090.

20. M. Bellare and P. Rogaway. Entity Authentication and Key Distribution. Advances in Cryptology CRYPTO '93, LNCS Vol. 773, Springer-Verlag, 1994, pp. 231-249.

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

22. A. Boldyreva. Efficient threshold signature, multisignature and blind signature schemes based on the Gap-Difile-Hellman-group signature scheme Report 2002/118, http://eprint.iacr.org, 2002

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

24. D. Boneh and M. Franklin. Identity-Based Encryption from the Weil Pairing. In Advances in Cryptology- CRYPTO '01, LNCS 2139, pages 213-229, Springer, 2001.

25. 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.(TaioKe http://eprint.iacr.org, 2002/175)

26. D. Boneh, B. Lynn, and H. Shacham. Short Signature from Weil Pairing, Proc. of Asiacrypt 2001, LNCS, Springer, pp. 213-229, 2001.

27. D. Boneh and A. Silverberg. Applications of Multilinear forms to Cryptography, Report 2002/080, http://eprint.iacr.org, 2002.

28. B] C. Boyd. Digital multisignatures, Cryptography and Coding, 1986

29. E. Bresson, O. Chevassut, and D. Pointcheval. Provably Authenticated Group Diffie-Hellman Key Exchange The Dynamic Case. Advances in Cryptology - Asiacrypt 2001, LNCS vol. 2248, Springer-Verlag, 2001, pp. 290-309.

30. E. Bresson, O. Chevassut, D. Pointcheval, and J. J. Quisquater. Provably Authenticated Group Diffie-Hellman Key Exchange. Proc. 8th Annual ACM Conference on Computer and Communications Security, ACM, 2001, pp. 255-264.

31. E. Bresson, O. Chevassut, and D. Pointcheval. Dynamic Group Diffie-Hellman Key Exchange under Standerd Assumptions. Advances in Cryptology Eurocrypt '02, LNCS 2332, L. Knudsen ed., Springer-Verlag, 2002, pp. 321-336.

32. M. Burmester and Y. Desmedt. A Secure and Efficient Conference Key Distribution System. Advances in Cryptology EUROCRYPT '94, LNCS 950, pp. 275-286, SpringerVerlag, 1995.

33. J. C. Cha, J.H.Cheon. An Identity-Based Signature from Gap Diffie-Hellman Groups. Report 2002/018, http://eprint.iacr.org, 2002

34. L. Chen, C. Kudla. Identity Based Authenticated Key Agreement from Pairings Report 2002/184, http://eprint.iacr.org, 2002

35. J.H. Cheon, D.H. Lee. Diffie-Hellman Problems and Bilinear Maps. Report 2002/117, http://eprint.iacr.org, 2002

36. K. Y. Choi, J. Y. Hwang and D. H. Lee. Efficient ID-based Group Key Agreement with Bilinear Maps, 2004 International Workshop on Practice and Theory in Public Key Cryptography (PKC2004, IACR).

37. C. Cocks. An Identity Based Encryption Schcme based on Quadratic Residues. In Cryptography and Coding, LNCS 2260, pp. 360-363, Springer-Verlag, 2001.

38. R.Cramer , V. Shoup. A practical public key cryptosystem provably secure against adaptive chjsen ciphertext attack. Advances in Cryptology, Crypto '98, LNCS Vol. 1462, Springer-Verlag, 1998.

39. W. Diffie and M. Hellman. New Directions In Cryptography. IEEE Transactions on Information Theory, IT-22(6): 644-654, November 1976.

40. I. Duursma, H. S. Lee. Tate-pairing implementations for tripartite key agreement. Report 2003/053, http://eprint.iacr.org, 2003

41. X. Du, Y. Wang, J. Ge, Y. Wang. An Improved ID-based Authenticated Group Key Agreement Scheme. Report 2003/260, http://eprint.iacr.org, 2003

42. X. Du, Y. Wang, J. Ge, Yumin Wan. ID-based Authenticated Two Round MultiParty Key Agreement. Report 2003/247, http://eprint.iacr.org, 2003

43. G. Frey, H-G. Ruck. A remark concerning m-divisibility and the discrete logarithm in the divisor class group of curves, Math. Comp. 62 (1994), 865-874.

44. S. Galbraith, K. Harrison and D. Soldera. Implementing the Tate Pairing. Algorithm Number Theory Symposium ANTS V, LNCS 2369, Springer- Verlag (2002), pp. 324-337.

45. C. Gentry, A. Silverberg. Hierarchical ID-Based Cryptography. Report 2002/056, http://eprint.iacr.org, 2002

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

47. K. Itakura and K. Nakamura, A public key cryptosystem suitable for digital multisignatures, NEC Research & Development, 71:1-8, 1983.

48. A. Joux. A One Round Protocol for Tripartite Diffie-Hcllman. ANTS IV, LNCS 1838, pp. 385-394, Springer-Verlag, 2000.

49. A. Joux and K. Nguyen. Separating Decision Diffie-Hellman from Diffie-Hellman in cryptographic groups. Report 2001/003, http://eprint.iacr.org, 2001.

50. J. Katz, M. Yung. Scalable protocols for authenticated group key exchange. Report 2003/171, http://eprint.iacr.org, 2003

51. K. Kim, S. Liu , F. Zhang. ID-Based One Round Authenticated Tripartite Key Agreement Protocol with Pairings. Report 2002/122, http://eprint.iacr.org, 2002

52. Y. Kim, A. Perrig, and G. Tsudik. Simple and Fault-tolerant Key Agreement for Dynamic Collaborative Groups. 7th ACM Conference on Computation and Communication Security, pages 235-244, Athens, Greece, Nov. 2000, ACM press.

53. Y. Kim, A. Perrig, and G. Tsudik. Tree based Group Key Agreement. Report 2002/009, http://eprint.iacr.org, 2002.

54. Y. Kim, A. Perrig, and G. Tsudik. Communication-efficient Group Key Agreement. In information systems security, Proceedings of the 17th International Information Security Conference, IFIP SEC '01, 2001.

55. L. Law, A. Menezes, M. Qu, J. Solinas, S. Vanstone. An efficient protocol for authenticated key agreement. Tec. Report CORR 98-05, Department of C&O, University of Waterloo, 1998. Avalable at citeseer.nj.nec.com/law98efficient.

56. H. K. Lee and H. S. Lee and Y. R. Lee. Multi-Party Authenticated Key Agreement Protocols from Multilinear Forms. Report 2002/166, http://eprint.iacr.org, 2002

57. C.Y. Lin, T.C. Wu, F. Zhang. A Structured Multisignature Scheme from the Gap Diffie-Hellman Group. Report 2003/090, http://eprint.iacr.org, 2003

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

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

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

61. A. Menezes, T. Okamoto, S. Vanstone. Reducing elliptic curve logarithms to logarithms in a finite field, IEEE Transactions on Information Theory 39 (1993), 16391646.

62. A. Menezes, P. van Oorschot, S. Vanstone. Handbook of Applied Cryptography. -CRC Press, Boca Raton, 1997

63. S. Micali, K. Ohta and L. Rcyzin, Accountable-subgroup multisignatures, ACM Conference on Computer and Communications Security, 2001.

64. D.Nalla, K.C.Reddy. ID-based tripartite Authenticated Key Agreement Protocols from pairings. Report 2003/004, http://eprint.iacr.org, 2003

65. T. Okamoto. A digital multisignature schema using bijective public-key cryptosystems, ACM Transaction on Computer Systems, 6(4): 432-441, 1988.

66. K. Ohta and T. Okamoto. A digital multisignature scheme based on the Fiat-Shamir scheme, Advances in Cryptology, ASIACRYPT '91, LNCS Vol. 739, H. Imai, R. Rivest and T. Matsumoto ed., Springer-Verlag, 1991.

67. K. Ohta and T. Okamoto. Multi-signature scheme secure against active insider attacks, IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences, E82-A(l):21-31, 1999.

68. T. Okamoto and D. Pointcheval. The gap problem: A new class of problem for the security of cryptographic primitives. In Proc. PKC 2001, LNCS Vol. 1992, pages 104-118, Springer-Verlag, 2001.

69. 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), 106-110.

70. A. Shamir. Identity-based Cryptosystems and Signature Schemes. In Advances in Cryptology CRYPTO '84, LNCS 196, pages 47-53, Springer-Verlag, 1984.

71. N.P. Smart. An identity based authenticated key agreement protocol based on the Weil pairing. Electronic letters, 38 : 630-632, 2002.

72. M. Steiner, G. Tsudik, M. Waidner. Diffie-IIellman key distribution extended to group communication, in Proc. 3rd ACM Conference on Communications Security (1996), 31-37.