Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
Криптографический протокол — это не только алгоритм, но и процедура обмена данными между разными участниками, связанная с обменом сообщениями по компьютерным сетям в соответствии с установленными правилами. Таким обра-
48
Часть I. Введение
зом, существует еще один аспект эффективности протоколов: количество сеансов связи, которые часто называют раундами (communication rounds). Обычно сеанс связи считается более дорогим, чем этап локальных вычислений (как правило, этот этап состоит из выполнения компьютерных инструкций, например, умножения двух чисел). Следовательно, было бы желательно минимизировать количество раундов в криптографическом протоколе. В соответствии со стандартным критерием качества алгоритм считается эффективным, если время его выполнения ограничено полиномом невысокой степени, зависящим от размера задачи. Аналогично протокол считается эффективным, если количество раундов связи ограничено полиномом очень малой степени: константой (степень равна 0) или линейной функцией (степень равна 1). Протокол, в котором количество раундов превышает линейную функцию, нельзя признать практически эффективным.
В разделе 18.2.3 мы рассмотрим некоторые протоколы с нулевым разглашением, в которых количество раундов оценивается нелинейными полиномами. Следует отметить, что эти протоколы непригодны для практических применений, однако они играют важную роль в теоретической криптографии и теории вычислительной сложности. В главе 18 мы опишем многочисленные исследовательские усилия, направленные на разработку практически эффективных протоколов с нулевым разглашением.
1.2.4 Использование полезных примитивов и услуг
Уровень стойкости, достаточный для одного приложения, может оказаться недостаточно высоким для другого. Вернемся к протоколу "Подбрасывание монеты по телефону". В разделе 1.2.1 мы пришли к выводу, что с помощью одной из практических однонаправленных функций Алиса и Боб могут успешно разрешить свой спор о свидании. Однако во многих криптографических приложениях такой протокол должен обеспечивать гораздо более высокую степень защиты от мошенничества. В некоторых приложениях понятие строгости используется в буквальном смысле.
Например, в главе 18 рассматриваются протоколы с нулевым разглашением, в которых на вход должна поступать случайная строка битов. Эта строка должна вызывать одобрение у обеих сторон — как доказывающей, так и проверяющей, иначе может возникнуть серьезная опасность. Если две общающиеся стороны не имеют доступа к посреднику, генерирующему случайные числа, или не доверяют ему (чтобы подчеркнуть непрактичность этой услуги, ее обычно называют "случайные числа, взятые с потолка"), они должны самостоятельно генерировать взаимно признаваемые случайные числа бит за битом (т.е. путем честной жеребьевки с помощью подбрасывания монеты), чтобы обеспечить правильность и нулевое разглашение протокола. В этом случае уровень практической стойкости
Глава 1. Защита информации в игре "орел или решка"
49
(например, присущей односторонней хэш-функции из протокола "Подбрасывание монеты по телефону") вероятнее всего окажется недостаточным.
Одна из насущных задач прикладной криптографии — создать высококачественные средства защиты информации на основе практичных и приемлемых примитивов. Разъясним эту идею на примере протокола "Подбрасывание монеты по телефону". Этот протокол представляет собой вариант протокола "подбрасывания монеты по телефону", предложенного Блюмом (Blum) [43]. Хотя этот протокол основан на использовании практически стойкой и легко реализуемой "однонаправленной" функции, он достигает весьма высокой степени стойкости.
• Во-первых, он позволяет получить количественную оценку сложности вычислений, выполняемых стороной, подбрасывающей монету (т.е. Алисой), в случае мошенничества, т.е. вычислений, необходимых для подготовки коллизии, состоящей из двух чисел, таких что если х ф у, то f(x) = /(у). В данном случае сложность вычислений сравнима со сложностью факторизации большого составного целого числа, которая представляет собой общепризнанную трудноразрешимую задачу.
• Во-вторых, угадывающая сторона абсолютно не способна выработать стратегию, вероятность успеха в которой была бы выше 50%. Это условие гарантирует полную безопасность.
Таким образом, протокол "подбрасывания монеты по телефону", предложенный Блюмом, особенно хорош для достижения высокой стойкости, обеспечиваемой лишь практичными криптографическими примитивами. Он усиливает и уточняет первый протокол, рассмотренный в книге, и станет последним протоколом, который мы рассмотрим.
Несколько лет назад была изобретена криптография с открытым ключом [97, 98, 246]. Со временем стало очевидным, что некоторые хорошо известные алгоритмы шифрования с открытым ключом (мы называем их "учебными") имеют слабые места: 1) в них существует утечка частичной информации о зашифрованном сообщении; 2) они чрезвычайно уязвимы для активных атак (см. главу 14). Это значит, что "учебная" криптография непригодна для практических целей. Первые попытки полностью устранить эти недостатки и предотвратить активные атаки неизменно сводились к побитовому шифрованию и даже к применению способов доказательства с нулевым разглашением на уровне битов. Кроме того, для их защиты использовались средства аутентификации. Эти результаты были весьма ценными для дальнейшего развития гарантированно стойких алгоритмов шифрования с открытым ключом, однако оставались непригодными для практического применения, поскольку требование нулевого разглашения или применение средств аутентификации являются непрактичными по отношению к алгоритмам шифрования.
