Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
Глава 18. Протоколы с нулевым разглашением
681
Очевидно, что на каждом шаге Боб может отвергнуть ложное доказательство с вероятностью 1/2. Следовательно, вероятность противоречивости (т.е. вероятность успешного обмана) равна 5 = 1/2. Если в течение т итераций Боб ни разу не отверг доказательство, вероятность успешного обмана не превосходит 2~~т. Успешный обман станет практически невозможным, если число т достаточно велико, т.е. число 2~~т является пренебрежимо малым. Например, если т = 100, обман становится крайне маловероятным. Следовательно, если Боб все же принял доказательство Алисы, значит, оно является правильным.
Позднее (в разделе 18.3.1 и в примере 18.2) мы проведем дальнейшее исследование понятия идеального нулевого разглашения (perfect zero-knowledge-ness): если функция / действительно является однонаправленной, то Боб, вынужденный применять полиномиально ограниченный алгоритм, не может выявить никакой информации о закрытых входных данных Алисы. ?
Примечание 18.1. Если функция f является гомоморфизмом, то f(x) = f(l)x для всех х € Ъп. Следовательно, в протоколе 18.1 Алиса доказывает свое знание дискретного логарифма числа X по основанию /(1). Этот протокол назван "доказательством принадлежности подгруппе", поскольку это название имеет более общий характер. Следует подчеркнуть, что ord[/(l)] является секретным делителем числа п, т.е. в общем случае элемент /(1) не порождает группу, состоящую из п элементов. Как правило. Боб не может непосредственно проверить принадлежность элемента подгруппе, не прибегая к помощи Алисы. ?
Замечание 18.1 утверждает, что решение задачи о принадлежности элемента подгруппе является трудной задачей. Приведем еще несколько свидетельств, подтверждающих сказанное. Отметим, что, хотя множество
Ln = {f(x) = f(ir\xezn}
является циклической группой (поскольку она порождается элементом /(1),
см. раздел 5.2.3), Бобу нелегко проверить условие фЬп == п. Для этого он должен разложить число п на простые множители (т.е. убедиться, что число /(1) является первообразным корнем или корнем единицы n-й степени, см. теорему 5.11 из раздела 5.4.4). Боб может ответить ДА, не вступая в контакт с Алисой, только если #Ln = п (поскольку число /(1) должно порождать все п элементов множества Ln). Таким образом, задача о принадлежности элемента подгруппе сводится к факторизации большого целого числа. Следовательно, чтобы затруднить решение этой задачи, целое число п в протоколе 18.1 должно быть достаточно большим. Именно по этой причине параметр безопасности в протоколе 18.1 должен иметь длину log п.
682
Часть VI. Криптографические протоколы
В разделе 18.3.1.1 будет показан специальный выбор общих входных данных,, при котором протокол 18.1 сводится к специальному варианту задачи о вычислении дискретного логарифма.
18.2.3 Результаты из теории вычислительной сложности
Этот материал можно пропустить без ущерба для понимания дальнейшего текста.
Докажем результат из теории вычислительной сложности, сформулированный
выражением (4.5.1). В главе 4 мы еще не могли доказать этот факт, а теперь можем.-
В прикладной криптографии нас интересуют только IP-протоколы, решающие
задачи о принадлежности предложений подклассу языков XV. Для любого языка l
¦>
из этого подкласса вопрос х € l имеет два аспекта.
1. Неизвестно, существует ли полиномиальный (по |ж|) алгоритм, детерминированный или вероятностный, позволяющий решить эту задачу. В противном случае игрок v может обойтись без помощи игрока р.
2. Задачу можно решить с помощью полиномиального (по \х\) алгоритма, еЫ ли ему доступно свидетельство, предоставляющее дополнительную инфор^ мацию.
Очевидно, что свойства 1 и 2 характеризуют класс NV (раздел 4.5). Точнее говоря, они описывают NP-задачу с немногочисленными свидетельствами. Пн скольку XV = VV (теорема 18.1), выполняется условие
NV С VV.
Следовательно, для любого языка l eNV существует IP-протокол (р, v), т.е. для' любого предложения х G l результат (р, v)(x) — Принять достигается за время полиномиально зависящее от параметра
Это свойство было конструктивно доказано несколькими авторами. Они сконструировали ZK- (IP-) протоколы для некоторых NP-полных языков (см. определение 4.11 в разделе 4.5.1) и решили задачу о раскраске графа тремя красками (Голдрайх, Микали и Уигдерсон (Wigderson) [124]), а также задачу об истинности булевского выражения (Чаум (Chaum) [71]). Сконструировав ZK-протокол (р, v\ для NP-полного языка L, задачу о принадлежности y€L' для произвольного NM языка можно решить следующим образом.
1. Игрок р сводит задачу у € l' к задаче х € l, где l — NP-полный язык (например, предложение х может представлять собой вариант задачи о раскрасив графа тремя красками или задачи об истинности булевского выражения). Поскольку игрок р знает предложение у € l', это преобразование можно
Глава 18. Протоколы с нулевым разглашением
683
выполнить за время, ограниченное полиномом, зависящим от длины предложения у. Игрок Р шифрует это преобразование и посылает зашифрованный текст игроку V.
