Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
692
Часть VI. Криптографические протоколы
В некоторых приложениях требуется доказать, что секрет имеет определенную структуру. В этих случаях доказательство не обязано быть секретным (т.е. доказывающая сторона не обязана отрицать свое участие в раунде). В таких приложениях доказательство знания является вполне адекватным и очень полезным методом.
18.3.2.3 И снова об идеальных протоколах с нулевым разглашением
Рассмотрим работу исходного варианта протокола идентификации Шнорра, в котором Боб руководствуется нечестной стратегией и пытается вынудить Алису поставить подпись по схеме Шнорра.
Однако теперь для любой псевдослучайной функции prf, генерирующей log2log2p бит, уравнение (18.3.2) может эффективно создать любой пользователь, иначе говоря, любой пользователь может создать уравнение относительно стенограммы доказательства.
Предположим, что ?Q — уравнитель. Все уравнители ?Q должны генерировать случайное число Response GrjZ9 и проверять, выполняется ли равенство (18.3.2) для каждого фиксированного числа Challenge из множества {0,1}1о^2 !°g2 Р. Если нет, алгоритм ?Q просто пытается сгенерировать новое число Response G уЪч. Метод проб и ошибок приводит к успеху до полного исчерпания всех log2 log2 р бит в пространстве значений функций prf. Поскольку длина функции prf равна log2 log2 р бит, пространство ее значений можно исчерпать за log2 log2p шагов, т.е за полиномиальное время, зависящее от числа р.
Создав уравнение, алгоритм ?Q может задать число Commit, используя формулу (18.3.1). Итак, строка
Transcript = Commit, Challenge, Response
представляет собой "стенограмму доказательства", имитирующую отдельный раунд. Эту строку можно создать за logp единиц времени. Эта стенограмма удовлетворяет условиям
Challenge = prf ("Осмысленное сообщение, подписанное Алисой" || Commit)
и
Commit = 9ResponseyChallense(modp).
Однако эта строка вообще не является корректной стенограммой доказательства, и Алиса не обязана ее создавать!
Итак, длина оклика в протоколе с нулевым разглашением имеет значение!
18.3.3 Вычислительные ZK-протоколы
Как показано выше, для того, чтобы продемонстрировать, что IP-протокол ^Р, V^j является идеальным ZK-протоколом, необходимо создать уравнитель, эффективно генерирующий "стенограмму", имеющую то же распределение, что
Глава 18. Протоколы с нулевым разглашением
693
и стенограмма, порождаемая протоколом \Р, Vj. Это требование можно ослабить, используя понятие вычислительного протокола с нулевым разглашением (computational zero-knowledge protocol).
Определение 18.3. IP-протокол (Р, V) для языка L называется вычислительным протоколом с нулевым разглашением, если для любого предложения х G L стенограмму доказательства (Р, V)(x) можно подделать с помощью полиномиального алгоритма S(x), причем распределение вероятностей поддельной стенограммы полиномиально неотличимо от истинного.
Понятие полиномиальной неразличимости введено в определении 4.15.
Для иллюстрации вычислительных ZK-протоколов изменим протокол 18.1. Будем считать, что однонаправленная и гомоморфная функция / определена в пространстве неизвестного объема, т.е. теперь число п в группе Z„ не знают оба участника протокола Р и V. Рассмотрим способ, позволяющий сконструировать такую функцию /.
18.3.3.1 Создание однонаправленной и гомоморфной функции f(x)
Предположим, что участники Р и V согласовали очень большое нечетное составное целое число N, причем ни один из них не знает его разложения на простые множители. Это довольно просто сделать, если каждый из участников предложит свое случайное число, которое используется для вычисления значения N. Однако мы не будем вдаваться в излишние подробности. Будем просто считать, что пользователи согласовали некий случайный элемент а < N, удовлетворяющий условию gcd(a,N) = 1.
Поскольку случайное число N велико, то с большой вероятностью оно имеет простой множитель р, неизвестный участникам Ри V, причем число р — 1 должно иметь большой простой множитель q, также неизвестный обоим сторонам протокола. Оставим в стороне вопрос, насколько большой должна быть эта вероятность, однако напомним, что для случайного и большого составного числа N существование таких больших простых чисел р и q объясняется теми же причинами, что и сложность его факторизации (см. раздел 8.8).
Поскольку числа anN являются случайными и согласованными, то с большой вероятностью мультипликативный порядок ordjv(a) является большим и секретным целым числом. Вероятность того, что q \ ог&м(а), не может быть меньше 1 — 1/д, поскольку для любого простого числа q | <?(iV) количество элементов группы порядок которых является взаимно простым с числом q, не больше
1/Q.
Предположим, что пользователи Р и V "определили" функцию
f{x) = ax(modN)
(18.3.3)
694
Часть VI. Криптографические протоколы
для любого целого числа х €Е Zjv. Мы взяли слово "определили" в кавычки, поскольку областью определения этой функции является группа %OTuN(a)> а не ^n, т.е. для любого х € Z/v всегда выполняется условие
f(x) = Az(modordjv(a)))-
