Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
Является ли кортеж (р, у, cj, c^/moXmodp) четверкой Диффи-Хеллмана? Является ли кортеж (р, у, с^, c|/mi)(modp) четверкой Диффи-Хеллмана?
Иначе говоря, игра IND-CPA действительно вынуждает Злоумышленника решагЦ задачу принятия решений Диффи-Хеллмана (DDH Question) в группе G (см. опрШ деление 13.1 в разделе 13.3.4.3).
Глава 14. Определения формальной и сильной стойкости криптосистем... 531
Если Злоумышленник способен правильно решить задачу принятия решений Диффи-Хеллмана в группе G, то по заданной зашифрованной паре окликов он может восстановить исходный текст, т.е. правильно угадать результаты жеребьевки, проведенной оракулом О. В противном случае, поскольку (д, у, с*, C2/mo)(modp) и (д,у, с*, с|/т\)(modp) являются случайными кортежами, порожденными элементом д, если бы Злоумышленник был способен правильно восстановить исходный текст, он смог бы решить задачу DDH в группе G = (д). Итак, стойкость криптосистемы Эль-Гамаля, использующей открытые параметры, установленные с помощью алгоритма 14.2, к атаке IND-CPA эквивалентна сложности решения задачи DDH в группе G (теорема 14.2).
В общем случае, для абелевой группы (в том числе, и для группы G, определенной в алгоритме 14.2) ни одного эффективного алгоритма решения задачи DDH не существует. Сложность решения задачи DDH считается эталоном неразрешимости. Подробное описание этой проблемы читатели могут найти в обзорной работе Бонэ [47].
Предположение 14.2 (Предположение о неразрешимости задачи принятия решений Диффи-Хеллмана в конечных полях.) Пусть XQ — генератор целых чисел, на вход которого поступает строка lk, время работы полиномиально зависит от числа к, а результатом работы является 1) описание desc(G) абелевой группы G над конечным полем, где |#G| = к; и 2) порождающий элемент группы
geG.
Генератор XQ удовлетворяет условию о неразрешимости задачи принятия решений Диффи-Хеллмана (DDH), если для всех достаточно больших чисел к и (desc(G),g) <— XQ(\k), множества (g,ga,gb,gab) и (g,ga,gb,gc) являются полиномиально неразличимыми в смысле определения 4.14 из раздела 4.7.
Следует отметить, что предположение о неразрешимости задачи DDH касается только групп над конечными полями, а не абелевых групп вообще, поскольку задачу DDH легко решить в группах точек суперсингулярных эллиптических кривых (см. раздел 13.3.4.3).
Итак, для исправленной криптосистемы Эль-Гамаля справедлив следующий результат.
Теорема 14.2. Криптосистема Эль-Гамаля, использующая открытые параметры, установленные с помощью алгоритма 14.2, является стойкой по отношению к атаке IND-CPA тогда и только тогда, когда выполняется предположение о неразрешимости задачи DDH. ?
532
Часть V. Методы срормального доказательства стойкости
14.3.6 Семантически стойкие криптосистемы, основанные на битах Рабина
После публикации работы Голдвассера и Микали о семантически стойких криптосистемах, Блюм и Микали [46], Яо [303], а также Блюм и Голдвассеи [45] предложили несколько семантически стойких схем шифрования с открытыл! ключом и модификаций криптосистемы GM.
Основная идея этих усовершенствований заключалась в использовании генератора криптографически стойких псевдослучайных битов (cryptographicall у strong pseudo-random bits — CSPRB). Такой генератор представляет собой npoJ грамму, на вход которой поступает начальное fc-битовое число, а результатом является к1 -битовое число, где параметр t > 1 фиксирован. Считается, что генератор порождает псевдослучайные числа высокого качества, т.е. если начальной fc-битовое число совершенно неизвестно, то итоговое к1 -битовое число абсолютна невозможно отличить от истинно случайного числа, имеющего такую же длин J если проверка осуществляется с помощью статистических критериев, на выпол! нение которых тратится время, полиномиально зависящее от аргумента к.
Итак, на вход генератора CSPRB поступает fc-битовый открытый ключ шифрования s. Результатом работы генератора является строка рт, состоящая из ? бив Отправитель шифрует сообщение тп, применяя к нему и строке рт операциш исключающего ИЛИ, и отсылает получателю пару
(ci, с2) = (?pfc(s), mQps). (14.3.3)1
Подлинный получатель (т.е. владелец открытого ключа рк) может расшифро-4 вать текст с\ и получить начальное значение s. Это позволяет ему заново создага псевдослучайную ^-битовую строку рт с помощью генератора CSPRB и восстановить сообщение тп, содержащееся в тексте с2, применив к нему оператор ио| ключающего ИЛИ.
Схема шифрования, основанная на применении генератора CSPRB, намного^ повысила эффективность побитового шифрования. Теперь ^-битовый исходны! текст шифруется с помощью ? + к, а не ?к бит. Временная и пространственна! сложность схемы побитового шифрования сравнима со сложностью криптосистем RSA, Рабина и Эль-Гамаля.
14.3.6.1 Семантическая стойкость схемы шифрования с помощью CSPRB-генератора
Если начальное число s представляет собой fc-битовую строку, имеющую равномерное распределение, а детерминированный блочный алгоритм шифровании ?рк (с длиной ключа к) представляет собой перестановки в пространстве сооб-1 щений, то первый блок зашифрованного текста с\ в формуле (14.3.3) образует! ся путем перестановки битов в равномерно распределенном случайном числе и^
