Содержание к диссертации
Введение
ГЛАВА 1 Проблема многостороннего ключевого соглашения и мультилинейные отображения
1.1 Понятия и определения. 9
1.2 Предположения Диффи-Хэллмана 13
1.3 Однораундовый (п+1)-сторонний обмен ключами но Диффи-Хеллману 18
ГЛАВА 2 Неаутентифицировапный Протокол Мультилинейного Группового Ключевого Соглашения со Структурой (к+1)-ичного Дерева (МГКССД)
2.1 Описание протокола МГКССД 20
2.2 Безопасность против пассивного противника 31
2.3 Операции динамического изменения членства группы 40
ГЛАВА 3 Аутентифицированиые версии протокола МГКССД
3.1 Понятия и определения, необходимые для аутентифицированного протокола. 47
3.2 Аутентифицированная версия протокола с использованием мультиподписи . 61
3.3 Аутентифицированная схема ключевого соглашения для мультилинейных криптосистем на основе идентификационных данных. 66
3.4 Доказуемо безопасная схема ключевого соглашения 78
ГЛАВА 4 Обсуждение эффективности протокола МГКССД
4.1 Эффективность МГКССД 90
4.2 Сравнение с известными протоколами 101
Заключение 105
Список использованных источников
- Предположения Диффи-Хэллмана
- Безопасность против пассивного противника
- Аутентифицированная версия протокола с использованием мультиподписи
- Сравнение с известными протоколами
Введение к работе
Постоянно растущая информатизация и компьютеризация общества приводят к необходимости совершенствования криптографических методов и средств защиты информации. В условиях взаимного недоверия субъектов информационной системы защита обеспечивается на основе методов асимметричной криптографии [2, 3, 4, 6].
Последнее время получили широкое распространения системы группового обмена информацией: аудио- и видеоконференции, текстовые конференции с большим количеством участников и другие. В основном такой информационный обмен происходит по открытым каналам связи. Вопрос об обеспечении безопасности информационного обмена такого рода стоит достаточно остро.
Ситуацию, когда три или более сторон совместно вырабатывают секретный ключ, используя несекретные каналы связи, часто называют ключевым соглашением конференцсвязи. В этой ситуации стороны получают возможность безопасного обмена информацией в небезопасной среде. Противник, не имеющий доступа к секретному ключу, не сможет расшифровать сообщения. Ключевое соглашение -один из фундаментальных криптографических примитивов после шифрования и цифровой подписи. Оно требуется в ситуациях, когда две или более сторон хотят обеспечить безопасную связь друг с другом.
С развитием глобальных компьютерных сетей возникла необходимость обеспечения безопасности конференцсвязи для динамически изменяющихся групп с большим количеством участников. Все вышесказанное потребовало развития теории и практики протоколов группового ключевого соглашения [1].
Протоколы ключевого соглашения делятся на два класса - с аутентификацией и без. Впервые протокол двустороннего ключевого соглашения был введен Диффи и Хеллманом в их оригинальной работе [41]. Это неаутентифицированный протокол в том смысле, что противник, который контролирует канал связи, может использовать атаку «человек в середине» для выработки двух раздельных ключей для двух пользователей, и пользователи не будут осведомлены об этом. Эта ситуация обычно исправляется добавлением в протокол какого либо механизма аутентификации.
Протоколы нсаутентифицированного ключевого соглашения предполагают, что противник пассивен, то есть противник может осуществлять перехват трафика сети, но не может изменять его. С другой стороны, протокол аутентифицированного
5 ключевого соглашения предполагает активного противника, то есть противник может изменять и перемещать сообщения в сети. Таким образом, требования к безопасности для аутентифицированного ключевого соглашения более строги. Вот некоторые из желаемых свойств в аутентифицированном ключевом соглашении:
обоюдная неявная ключевая аутентификация;
известная ключевая безопасность;
«безопасность будущего»;
отсутствие деперсонализации ключевой компрометации;
ключевой контроль.
Помимо аутентификации другими аспектами протоколов ключевого соглашения являются вычислительная и связная эффективность. Когда количество сторон больше двух, протокол обычно является многораундовым. В каждом раунде все или некоторые пользователи посылают сообщения другим пользователям и в конце всех раундов все пользователи должны совместно выработать общий ключ. Общее количество бит, обмениваемых в протоколе, является критическим параметром и позволяет судить об эффективности протокола.
Предыдущие результаты: как упоминалось ранее, первый двусторонний протокол неаутентифицированного ключевого соглашения был предложен Диффи-Хеллманом в их оригинальной работе [41]. Он был модифицирован в протокол аутентифицированного ключевого соглашения в работе Мацумото, Такшима и Имаи [61]. Позже, в [57] показано, что некоторые из протоколов, описанных в [61], небезопасны и предложен новый протокол аутентифицированного ключевого соглашения. В дальнейшем последовал ряд предложений для аутентифицированного и неаутентифицированного ключевого соглашения [64, 73, 36].
Среди известных многосторонних протоколов ключевого соглашения только два протокола имеют количество раундов меньшее, чем у предлагаемого в диссертации протокола. Боне и Силверберг [29], предложили однораундовый протокол многостороннего ключевого соглашения. Этот протокол основан на существовании n-мультилинейных отображений для больших значений «п» («п» определяется размером группы и может достигать до нескольких тысяч). Предполагается маловероятным появление алгоритмов генерации п-мультилинейных
отображений для таких значений п в ближайшие годы. Другой протокол, требующий меньшее количество раундов, предложен Бурмейстером и Десмедтом [34]. Это неаутентифицированный протокол, требующий два раунда. Однако, его вычислительная сложность высока и общее количество возведений в степень составляет порядка п2. Также авторы указывают, что техника доказательства нулевого разглашения требует преобразования этого протокола в аутентифицированный протокол. В 2003 году Кац и Юнг разработали 3-раундовую версию протокола Бурмейстера-Десмедта и доказали ее безопасность [52]. Поэтому на данный момент протокол Бурмейстера-Десмедта (в дальнейшем будем обозначать его протокол BD) может считаться полноценным лидером по связной эффективности.
Одним из важных направлений развития теории протоколов группового ключевого соглашения является разработка протоколов со структурой дерева. Первоначально разрабатывались протоколы группового ключевого соглашения на основе двоичного дерева с использованием в качестве базового подпротокола модификаций протокола Диффи-Хеллмана [54, 55, 56].
В 2000 году Джо предложил однораундовый трехсторонний протокол ключевого соглашения [50]. Естественным развитием этого революционного результата являются следующие 2 направления.
Протокол Джо - аналог протокола Диффи-Хеллмана, но вычисляет общий ключ не для двух, а для трех корреспондентов. Использование этого преимущества при построении протокола многостороннего ключевого соглашения - первое направление. В 2003 представлен первый вариант такого протокола - протокол группового ключевого соглашения на основе троичного дерева [18].
В протоколе Джо используются билинейные отображения. Наличие практических алгоритмов для построения n-мультилинейных форм позволило бы построить однораундовый протокол (п+1)-стороннего ключевого соглашения. В 2002 году Боне и Сильверберг [29] описали такой протокол, а несколько позже корейские авторы [58] предложили аутентифицированную версию такого протокола.
Однако задача построения n-мультилинейных отображений в настоящий момент является открытой проблемой. Предполагается маловероятным появление таких алгоритмов для больших значений п в ближайшие годы (напомним, что в
7 нашем случае значение п определяется размером группы, а группы могут быть значительных размеров). В тоже время представляется вполне реальным появление конкретных n-мультилинейных преобразований для малых значений п (п=3,4,5).
В связи с этим возникает задача разработки протоколов Мультилинейного Группового Ключевого Соглашения со Структурой Дерева (МГКССД), реализующих преимущества k-мультилииейных отображений для малых значений к, которая и решается в данной диссертационной работе.
Целью диссертационной работы является разработка семейства протоколов группового ключевого соглашения с использованием преимуществ, которые дает существование k-мультилинейного отображения для малых значений к. Для достижения поставленной цели решались следующие задачи.
Разработка базового алгоритма со структурой дерева, обеспечивающего неаутентифицированное ключевое соглашение с использованием к-мультилинейного отображения.
Разработка аутентифицированных версий базового протокола различного уровня сложности и, соответственно, обеспечивающих безопасность для различных условий и требований.
Разработка необходимых понятий, схем и протоколов для случая к-мультилинейных отображений.
Доказательство безопасности всех версий разработанного протокола в условиях различных моделей противника.
Исследование эффективности разработанных протоколов и их сравнение с протоколами, известными ранее.
На защиту выносятся следующие положения. 1. Алгоритм базового неаутентифицированного протокола группового соглашения со структурой дерева (МГКССД), реализующий преимущества использования k-мультилинейных отображений и безопасный по отношению к атакам пассивного противника.
2. Элементы теории мультилипейной криптографии (с использованием к-
мультилинейных отображений), включающие:
схему мультиподписи;
схему объединенной подписи;
криптосистему на основе идентификационных данных (КСОИД);
обобщение протокола Ченга-Лиу-Кима.
Доказуемо безопасная в условиях стандартной модели безопасности аутентифицированная версия протокола МГКССД с использованием мультилипейной объединенной подписи.
Аутентифицированная версия протокола МГКССД в условиях мультилипейной криптосистемы на основе идентификационных данных.
Научная новизна работы
Разработан оригинальный протокол Мультилинейного Группового Ключевого Соглашения со Структурой Дерева (МГКССД), использующий преимущества к-мультилинейных отображений для малых значений к и обладающий более высокой связной эффективностью по сравнению с протоколами соответствующего класса.
Разработаны для случая k-мультилинейных отображений: схемы мультиподписи и объединенной подписи, криптосистемы на основе идентификационных данных (КСОИД), обобщения протокола Ченга-Лиу-Кима.
Разработана аутентифицированная версия протокола МГКССД с использованием описанной мультилинейной КСОИД.
Разработана доказуемо безопасная в условиях стандартной модели безопасности версия протокола МГКССД с использованием описанной схемы мультилинейной объединенной подписи.
Предположения Диффи-Хэллмана
В этом подразделе мы сначала напомним некоторые известные версии проблемы Диффи-Хэллмана, а затем расширим их на случай мультилинейных отображений. Сформулируем стандартные проблемы Диффи-Хэллмана [25, 51], с которых собственно и берет начало асимметричная криптография. Для простоты будем рассматривать группу G простого порядка q.
1. (Вычислительная) проблемаДиффи-Хеллмана (Computational Diffie-Hellman Problem (CDH)) Дано: Три элемента группы G (g, ga, gb) для некоторых a,b e Z . Задача: найти элемент Ііє G, h=gab (Или что тоже самое найти се Z ,такое что c=ab modq.)
2. Решающая проблема Диффи-Хеллмана (Decisional Diffie-Hellman Problem (DDH)) Дано: Четверка элементов группы G (g, ga, gb, gc) для некоторых a,b, с є Z . Задача: проверить равенство c=ab mod q. Теперь рассмотрим известные проблемы Диффи-Хэллмана, связанные с билинейным спариванием [19, 37]. Пусть (G},G2,e) , где Gi,G2 - две циклические подгруппы большого простого порядка q и е: G,2 -»G2 - криптографическое билинейное отображение. Будем рассматривать Gj как аддитивную группу, a G2 - как мультипликативную группу.
3. Решающая проблема Диффи-Хеллмана в Gj (Decisional Diffie-Hellman Problem (DDH)) Дано: (P,aP,bP,cP) для некоторых a,b,ce Z . Задача: проверить равенство c=ab mod q. DDH-проблема в G/ - легка: Ю#-проблема в G; может быть решена за полиномиальное время проверкой e(aP,bP) = е(Р,сР). Это хорошо известное MOV-сокращение [26]: ДЛП в G/ не сложнее, чем ДЛП в G2. DDH-предположение: не существует полиномиальных алгоритмов, которые могут решить DDH-проблему в G2 с вероятностью успеха отличной от ничтожно малой. Для деталей смотри [40].
4. Решающая проблема Диффи-Хеллмана для случая хеширования в Gi ( Hash Decisional Diffie-Hellman problem (HDH)): Дано: (P,aP,bP,r) для некоторых a,b,r є Z и односторонняя хэш-функция Н: Задача: проверить равенство r=H(abP) mod q. Выход: 1 - верное равенство, О-в противном случае. Эта проблема была введена Абдаллой, Белларом и Рогевеем в [16]. Единственная разница в том, что набор значений, использовавшийся ими в хэш-функции, был строками фиксированной длины, а здесь значения берутся из набора Z q. HDH-предположение: не существует полиномиальных алгоритмов, которые могут решить HDH-проблему в G/ с вероятностью успеха, отличной от ничтожно малой.
5. Билинейная проблема Диффи-Хеллмана в (G, ,G2,e) (Bilinear Diffie-Hellman problem (BDH)) : Дано: (P,aP,bP,cP) для некоторых а,Ь,сє 2 . Найти: е(Р,Р)аЬс
BDH-предполооісение: не существует полиномиальных алгоритмов, которые могут решить BDH-проблему в (G,,G2,e) с вероятностью успеха отличной от ничтожно малой. 6. Решающая билинейная проблема Диффи-Хеллмана для случая хеширования (Decisional Hash Bilinear Diffie-Hellman problem (DHBDH)) в (G,,G2,e): Дано: (P,aP,bP,Cp,r) для некоторых a,b,c,re Z q и односторонняя хэш-функция H: G2 z;r Задача: проверить равенство r=H(e(P,P)ahc) mod q. ( Т. е. предложить алгоритм, для которого выход «1» - верное равенство, «О» - в противном случае.) DHBDH-предположение: не существует полиномиальных алгоритмов, которые могут решить DHBDH-проблему с вероятностью успеха отличной от ничтожно малой.
Исследования в данной работе связаны с мультилинейными отображениями. Для доказательства безопасности описываемых протоколов не достаточно невычислимости дискретного логарифма и стандартных предположений Диффи-Хеллмана. Мы нуждаемся в специфических предположениях, связанных с мультилинейными отображениями. Ниже перечислим эти предположения[29].
Для оставшейся части раздела зафиксируем генератор мультилинейного отображения G (вместе с такими параметрами как: q порядок групп G и G2; g -некоторый генератор Gi и е: G" - G2 - n-мультилинейное отображение). 7. (Вычислительная) п-мулыттииейпая проблема Диффи-Хеллмана в (G,,G2,e) (Multilinear Diffie-Hellman problem (MDH)) : Дано: g,g\...,g"n,i eGi для некоторых al,...,an+ie Z .
Задача : вычислить e(g,...,g)ai "" MDH-предположение: не существует полиномиальных алгоритмов, которые могут решить MDH-проблему в (G,,G2,c) с вероятностью успеха отличной от ничтожно малой.
Для более точной формулировки, определим успех рандомизированного алгоритма А в решении мультилипейпой проблемы Диффи-Хеллмана, как вероятность того, что А может вычислить e(g,...,g)","M" ! ИЗ g,ga ,...,""" , ТО ССТЬ,
Успех DHmGAlXO = P[A(r, g,ga\...,g" ) = e(g,...,gr"- : (f,g,q) G(t,n),(a,,...,an,d r- (Z/qZfl\.
Определение 1.5 Будем говорить генератор мультилинейных отображений G удовлетворяет мулыпилинейному предположению Диффи-Хеллмана, если для всех полиномиальных алгоритмов А (полиномиальных от /) и для всех п 1, функция Успех DHmGAn{t) ничтожно мала.
8. Решающая п-мультилипейпая проблема Диффи-Хеллмана в (G,,G2,e) (Decisional Multilinear Diffie-Hellmanproblem (DMDH)): Дано: g,ga,,...,g"" eGi для некоторых о/,...,а„+/є Z q и re G2 Задача: проверить равенство r=e(g,...,g)" " . DMDH-предположение: не существует полиномиальных алгоритмов, которые могут решить DMDH-проблему в (G,,G2,e) с вероятностью успеха отличной от ничтожно малой.
Безопасность против пассивного противника
Для окончательного общего ключа KEY для m участников в процедуре TREE KEY справедливо следующее , „. с(«-1„(«-1) ,(И-11 KEY=s\R) = S=H(e(g,g,...,gY где R -R(m), т к+1. Утверждение 2.3 Каждый член /7) может вычислить .у ." для 7 У Ш/ , i R), где R=R(m). Следовательно, все пользователи могут вычислить общий ключ KEY=.y,w.
Доказательство: Докажем утверждение индукцией по і.
Докажем для і=0. Первоначально Uf =j и закрытый ключ .у}0) вырабатывается каждым пользователем для J j т . Поэтому каждый член Ulu, l j т/ может вычислить s{p.
Индукционный шаг: Пусть 1 і R, l j mt.\ , каждый член набора пользователей С/] "0 вычислил s 0 в (і-І)-ом раунде. Заметим, что TREE KEY никогда не
вызывает процедуру Key (m, U[l,2,...,m], a[l,2,...,m]) для раунда і 2. Теперь на і-ом раунде, для у-/,..., ш, , TREE KEY вызывает КеуТ, в котором набор пользователей Uf вычисляет л , используя соответствующие л /(М) (і-І)-го раунда.
Набор пользователей Uf состоит из всех членов ((ГЛ мн Кіннг -мОД .,, ,, все из которых знают соответствующее s по индукционному предположению. Поэтому каждый член U(p может вычислить требуемое slp . Следовательно, утверждение доказано.
Поднимем один вопрос: Как пользователь и (/ и т) в определенном раунде i 1 определяет, какому пользовательскому набору он принадлежит, и является ли он представителем данного набора? Используя правила алгоритма, пользователь и может легко вычислить все пользовательские наборы Ulp ( l j irij ) этого раунда и может эффективно проверить их расположение. Заметим, что каждый и) ] есть поднабор {1,2,...,п}, состоящий из последовательных целых чисел, что значительно упрощает вычисления. Определение представителей каждого НП задействовано в алгоритме TREE KEY.
Безопасный протокол ключевого соглашения должен противостоять и пассивным и активным атакам. В этом подразделе мы определим Проблему решения группового ключевого соглашения на основе (к+1)-ичного дерева (ПРГКСОД) для нашего неаутентифицированного протокола и покажем, что эта проблема сложна для пассивного противника, сведением сложности этой проблемы к сложности DHMDH проблемы, следуя технике используемой в [54], [74]. Аутентификация вводится в наш неаутентифицированный протокол для достижения безопасности против активного противника. При этом используются дополнительные понятия (мультилинейная мультиподпись, мультилинейная объединенная подпись, мультилинейные криптосистемы на основе идентификационных данных), которые будут рассмотрены далее.
Для заданного (+7)-ичного дерева Т высоты не более Ren узлами (п к) и Х= (sj, s2,...i s„) для Sj Z 4,(i=l,...,n) открытые значения и секретный ключ определяются совместно следующим образом: -p(R, X, Т) : = { Pj \ гдеу и / определены в соответсвии с Т} „(Л-0 (Л-1) (К-1) - K(R, Х,Т):= KEY = Н(е(Р,Р) s "л ) p(R, X, Т) - это в точности та информация, которую может получить пассивный противник в (+/)-ичном дереве Т, где окончательный ключ - K(R, X, Т) . Назовем ключ K(R, X, Т) - DHMDH ключ. Наша цель показать, что этот DHMDH ключ, сгенерированный в процессе неаутентифицировапного протокола, не может быть отличен от случайного числа полиномиальным алгоритмом, если все передаваемые в протоколе значения известны.
Предположим TR - это набор всех (к+1)-ичных деревьев высоты R, имеющих структуру TREE KEY. Пусть дерево Т высоты R выбрано случайно из TR. Пусть Xe(Z q)m {m (k+l)R) , будут случайно выбираемые метки (краткосрочные ключи) узлов нулевого уровня дерева Т. R - число раундов протокола ключевого соглашения конференцсвязи с m пользователями. Определим две случайных переменных Ан , А и следующим образом: - АК: = (p(R, X, Т), у), - это набор случайных данных, располагаемых вдоль дуг дерева Т (ye Z - случайное число); - AR: = (p(R, X, 7), K(R, X, Т)), р и К - открытые данные и секретный ключ случайно выбираемого дерева Т.
Пусть SR ={{Т,Х): TZTR И Xe(Z 4)m, где m - количество узлов нулевого уровня в дереве Т }. Пусть Вт - количество ребер в (к+1)-ичном дереве Т. Для (Т,Х) є 5Л определим Г(Т,Х) как все возможные упорядоченные наборы открытой информации вдоль дуг Т. Ясно, что Г(ГД)с (G,) . Тогда случайная переменная AR принимает значения из пространства (G,)" х Z в соответствии со случайным вероятностным распределением, и AR принимает значения из пространства Г(Т,Х) х Z с (G,)" х Z также со случайным вероятностным распределением. Определение2.1 Рассмотрим (G,,G2,e). Пусть ш & положительное целое, Х= (sj, 5-2,..., 5Ш) для 5-,-є Z . Г - (к-И)-ичное дерево высоты R с m узлами нулевого уровня, помеченными X, AR и А1{ определены , как указано выше. Решающий алгоритм F ключевого соглашения на основе (к+1)-ичного дерева для (G,,G2,e) есть вероятностный полиномиальный алгоритм (с выходом 0 или 1), удовлетворяющий для некоторого фиксированного / 0 и достаточно большого с неравенству; \Prob[F(AR)= l]-Prob[F(AR)=l]\ —, (для любых значений А1{ и AR). с
Будем называть алгоритм F полиномиально различающим, если он различает А1{ и AR , как определено выше. Проблему отличия истинного общего ключа конференцсвязи для нашего протокола от случайного числа сформулируем следующим образом.
11. Решающая групповая хешироваппая мульпшлипейпая проблема Дшрфи Хеллмапа на основе дерева в (G,,G2,e) (Decisional Tree Group Hash Multilinear Diffie Hellman problem (DTGHMDH)) заключается в нахождении полиномиального различающего алгоритма F для AR и Ан, определенных выше.
Аутентифицированная версия протокола с использованием мультиподписи
Для данной аутентифицированноїі версии ключевого соглашения будем дополнительно требовать следующее:
1. Существование одного или нескольких Центров Сертификации Ключей.
2. Существование хэш-функции #// {0,1 } - G,\ которая отображает битовые строки произвольной длины в элементы G\{1}, где 1 обозначает нейтральный элемент группы G (это необходимо для генерации подписей).
3. Каждый пользователь системы связи имеет долговременный секретный ключ дг/є Z и соответствующий ему долговременный открытый ключ gx е G. Центр Сертификации Ключей (ЦСК) снабжает пользователей системы сертификатами ключей, при регистрации в системе связи. Сертификат пользователя А-, в упрощенном варианте имеет следующую форму: Серт,,, ={ U-P SUCK(U-P )} Здесь \Лі - обозначает идентификатор пользователя А„ \\ - знак конкатенации, Р Ai = gx , где Xj є Z секретный ключ пользователя At, g - генератор группы G]. SIICK обозначает подпись Центра Сертификации Ключей. 4. Ключи ai,a2,...,a„ - кратковременные закрытые ключи. Системные параметры для аутентифицированного протокола params=(G],G2,e,q,g,H,H,Hl,KUCK). (КцСк ключ Центра Сертификации Ключей.)
Для простоты восприятия здесь используется упрощештя модель связи. На практике необходимо использовать модель связи, используемую при обсуждении доказуемо безопасной версии МГКССД. Аутентифицировашшя схема ключевого соглашения с использованием мулътиподписи
Данная версия нашего протокола использует мультиподписи представителей наборов пользователей под общими ключами, которые они вырабатывают. Процедура построения ключевого дерева и вычисления общего ключа остается такой же, как в неаутентифицироваиной версии протокола. Добавляются элементы аутентификации лишь в процедуры выработки общего ключа m сторон Key (m, U[l,2,...,m], д[1,2,...,т]) и для (к+1) сторон KeyT(U[l,2,...,(k+l)],a[l,2, ...,(к+1)]).
Рассмотрим процедуру выработки общего ключа для (к+1) сторон. Заметим, что получение сертификатов открытых ключей пользователей и проверки подписей ЦСК подразумеваются, хотя для краткости в процедуры не включены. Procedure КеуТ ( U[l,2,...,(k+1)], a[l,2, ...,(k+1)]) i=l to (k+1) do rip(Ui) вычисляетgr g" (а,--общий ключ набора Uj) np(Uj) посылает (g,- , Jlodn(gi)) всем членам U,- , (для любого j Ф І). IJodn(g,) - это мультиподпись (k+1) стороны под сообщением g"1. end do i=l to (k+1) do
Каждый член Uj проверяет k мультиподписей [Jodn(gj), которые он получил. Если проверка прошла неуспешно, протокол прекращается. Если все проверки прошли успешно, продолжается выполнение протокола. Каждый член Ц вычисляет общий ключ S=H(e{g,g,...,gr- )=H(e(g,,...,gi gl+v..,gkJV end do (k+1) представителей совместно генерируют мультиподпись под сообщением M=gs, где S - вычисленный общий ключ. Один из (k+1) представителя, выбранный представителем объединенного НП, широковещательно рассылает мультиподпись всем пользователям объединенного НП. i=l to (k+1) do Каждый член U; проверяет мультиподпись, которую он получил. Если проверка прошла неуспешно, протокол прекращается. Если все проверки прошли успешно, продолжается выполнение протокола. end do End КеуТ
Остановимся подробнее на генерации мультиподписи. Для определенности будем считать, что np(Ui ) выбирается представителем для объединенного НП. Каждый из оставшихся к представителей посылают ему свою GDH-подпись под сообщением М=/ , где S= Н (e(g,g,...,g)a,"I-"ktl).
Пр(иО широковещательно рассылает мультиподпись всем пользователям объединенного НП. Эта же подпись будет использована в процедуре КеуТ на следующем уровне ключевого дерева при рассылке Tlodn(gi).
Процедура выработки общего ключа m сторон Key (m, U[l,2,...,m], а[1,2,...,т\) для аутентифицированного варианта протокола остается почти без изменений. Добавляется лишь рассылка сертификатов для долговременных открытых ключей m пользователей. Напомним, что данная процедура, используется лишь для средней подгруппы нулевого уровня. Каждая из m сторон состоит лишь из одного пользователя. Поэтому генерация мультиподписи не требуется, а используются индивидуальные подписи пользователей.
Сравнение с известными протоколами
В этом разделе протокол МГКССД сравнивается с известными протоколами выработки общего секретного ключа по открытым каналам связи участниками криптоконференции. Бурмейстер и Десмедт представили в [34] эффективный многосторонний протокол, который может быть выполнен всего за два раунда. Класс общих п-сторонних протоколов Диффи-Хеллмана (п 2) определен в [74]. Показано, что весь этот класс протоколов является безопасным против пассивного противника, в предположении невычислимости DDH-проблемы. Одним из протоколов распределения группового ключа является GDH-3 [74]. Протокол группового ключевого соглашения на основе дерева TGDH предложен в [54]. Показано, что этот протокол безопасен против пассивного противника. Заметим, что предположения, требуемые для безопасности рассматриваемых протоколов, различны, и, следовательно, в строгом смысле сравнение эффективности может быть некорректно. Однако, рассуждения, приведенные ниже, все же позволяют судить об относительной эффективности различных протоколов.
Ниже приводится сравнение неаутентифицироваиной версии протокола МГКССД с другими протоколами. (Inv - общее количество модульных инверсий).
Замечания по поводу неаутептифицированных протоколов:
1.Используемая группа в GDH-3 и BD протоколах - это мультипликативная подгруппа Z p порядка q, где q и р - простые.
2. Связная (коммуникационная) сложность измеряется посредством R(n) и В(п), и протокол МГКССД достигает минимума для обеих функций среди всех известных протоколов, кроме BD протокола. Вычислительная сложность нашего протокола состоит из двух частей - экспоненцирования и к-мультилинейного отображения. Количество экспопепциирований меньше, чем в других протоколах, но требуется дополнительно n [logi+l п ] к-мультилинейных отображений. В значительной степени вычислительная сложность МГКССД определяется сложностью вычисления к-мультилинейных отображений. По вычислительной сложности МГКССД достигает: - уровня BD при вычислительной сложности к-мультилинейных отображений приблизительно равной СЛМо n/flog .+, /7] экспоненциированиям, что вполне достижимо при больших п; - уровня TGDII при СЛМ0 "log2 w]/"logA+1 п\ экспоненциированиям; - уровня GDH-3 при СЛмо 4 экспоненциированиям; - уровня BDS при СЛмо=П8.і «1/Пё + "1 билинейным спариваниям.
Таким образом, МГКССД дает значительный выигрыш в связной эффективности по сравнению с протоколами TGDH и GDII-3, за счет увеличения вычислительной сложности, что в ряде случаев бывает оправдано. По сравнению с BDS протокол МГКССД дает уверенный выигрыш в связной эффективности, и ожидаемо сравним по вычислительной сложности. Заметим, что использование протокола МГКССД для случая билинейного спаривания дает протокол более эффективный, чем протокол BDS, специально созданный для этого случая. Количество сообщений и количество вычисляемых экспопепциирований при этом 5/2(п-1) в BDS и 3/2п в нашем протоколе. В сравнении с протоколом BD протокол МГКССД дает выигрыш в вычислительной сложности (для больших п) при незначительном увеличении связной сложности. При этом вычислительная сложность МГКССД в значительной мере определяется сложностью вычисления к-мультилинейных отображений.
На протоколе BD (Burmester и Dcsmedt) остановимся более подробно, как на лидере по связной эффективности. До недавнего времени протокол BD имел серьезный недостаток. Не существовало удобной аутентифицированной версии этого протокола. Без возможностей аутентификации (с доказанной безопасностью) ни один протокол не может рассчитывать на серьезное практическое внедрение. Ситуация изменилась в 2003 году. Кац и Юнг разработали 3-раундовую версию протокола BD и доказали ее безопасность [52]. Поэтому на данный момент протокол BD может считаться полноценным лидером по связной эффективности и одним из лидеров по общей эффективности (хотя его вычислительная эффективность весьма слаба). В [52] также упоминается о возможностях эффективного использования протокола BD для групп с динамическим изменением состава участников. Однако протокол МГКССД за счет использования структуры дерева может давать следующие преимущества: возможно построение сети копференцсвязи, в которой основные вычислительные и связные нагрузки принимают на себя специально выбранные стороны; - упрощается процедура выявления умышленного противодействия выработке общего ключа криптоконференции со стороны участников.
Далее сравним аутентифицированную версию нашего протокола МГКССДді (ДЛЯ КСОИД) С существующими протоколами аутентифицированного группового ключевого соглашения на основе протокола Диффи-Хеллмана SA-GDH-2 [17], ID-AGKA [66] HBDSA[18] в таблице 2. (Inv -общее количество модульных инверсий, Mul - общее количество модульных умножений).
