Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
2. Игрок Р проводит ZK-доказательство, предоставляя игроку V возможность проверить корректность шифрования. В разделе 18.4.2 будет убедительно показано, что ZK-доказательство корректности шифрования строки нетрудно провести, если шифрование проводилось по вероятностной схеме Голд-вассера-Микали.
Очевидно, что эти два этапа образуют ZK-протокол для доказательства принадлежности х ? L, т.е. корректное доказательство принадлежности у € L'. Заметим, что в этом доказательстве нет никаких ограничений на язык V, кроме его принадлежности классу MV.
Кроме того, легко видеть, что на практике такое общее доказательство является неэффективным. В разделе 18.6 будет показано, что в эффективном ZK- (и IP-) протоколе количество раундов должно быть ограничено линейной функцией, зависящей от параметра безопасности. Маловероятно, чтобы это ограничение было справедливым для общего протокола, поскольку в настоящее время не существует ни одного линейного метода редукции NP-задачи к NP-полной задаче. Все известные редукции являются полиномиальными, причем имеют высокую степень. Вот почему мы утверждаем, что ZK-решение задачи о принадлежности предложения произвольному NP-языку носит чисто теоретический характер, хотя и является довольно важным. Оно представляет собой конструктивное свидетельство включения MV С W.
Равенство MV = VV остается нерешенной задачей из теории вычислительной сложности.
18.3 Нулевое разглашение
Предположим, что на вопрос 1 (раздел 18.1) существует идеальный ответ (Р, V) — протокол с нулевым разглашением, т.е. пользователь V (или V) убеждается в корректности утверждения пользователя Р, не узнав ничего нового о его закрытых входных данных.
Для того чтобы протокол (Р, V) обладал этим свойством, необходимо ограничить вычислительную мощь пользователя V (или V) полиномом, зависящим от размера его входной информации. Очевидно, что без этого ограничения нельзя гарантировать нулевое разглашение, поскольку пользователь V, обладающий неограниченными вычислительными ресурсами может самостоятельно раскрыть секретные входные данные пользователя Р.
В дальнейших разделах мы рассмотрим несколько аспектов нулевого разглашения.
684
Часть VI. Криптографические протоколы
• Идеальное нулевое разглашение (perfect ZK) (раздел 18.3.1).
• Честная проверка (раздел 18.3.2).
• Вычислительные ZK-протоколы (раздел 18.3.3).
• Статистические ZK-протоколы (раздел 18.3.4).
18.3.1 Идеальное нулевое разглашение
Пусть (р, v) — IP-протокол для языка l. Для любого предложения х е l выполнение протокола (p,v)(x) приводит не только к выводу результата ПриЧ нять, но и порождает стенограмму доказательства, в котором чередуются элемен^ ты стенограмм доказывающей и проверяющей стороны. Элементы стенограммьц доказательства являются случайными величинами, зависящими от всех входных^ данных, включая случайные входные данные протокола (Р, v).
Очевидно, что доказательство (Р, V)(a;) раскрывает любую информацию о закрытых входных данных пользователя Р только в том случае, если стенограмма| доказательства допускает утечку информации.
Однако, если случайные величины в стенограмме доказательства являются равномерно распределенными (uniformly random) по соответствующему вероят^ ностному пространству и не зависят от общих входных данных, то бессмыс-J ленно утверждать, будто они допускают утечку информации. Будем считать, чтя в этой ситуации (т.е. когда стенограмма доказательства состоит из равномерна распределенных случайных величин, не зависящих от общих входных данных! доказывающая сторона общается с проверяющей стороной на языке, не обладакж щем свойством избыточности (redundancy), т.е. имеющем наибольшую энтропинй (highest possible entropy) (см. раздел 3.7.1). Следовательно, не имеет значения, нал сколько умным (или мощным) является проверяющий пользователь. Даже изучав этот язык очень долгое время, он не сможет извлечь никакой дополнительной] информации!
Докажем теперь, что протокол 18.1 представляет собой идеальный ZK-npo-токол.
Пример 18.2. Проанализируем протокол 18.1. Стенограмма доказательства, со! зданная при выполнении протокола (Алиса, Боб)(Х), выглядит следующим образом.
Commiti, Challenge!, Response!,..., Commit™, Challengem, Responsem,
где для i = 1,2,...,m выполняются следующие условия.
• Commit* = f(h), где ki E цЪп.
Очевидно, поскольку Алиса извлекает числа ki из равномерно распределенной генеральной совокупности, величины Commit^ также равномерно
Глава 18. Протоколы с нулевым разглашением
685
распределены по пространству значений функции / и не зависят от общих входных данных X.
• Challenge, е {0,1).
Боб должен извлекать бит оклика из генеральной совокупности равномерно распределенных величин, но это требование можно снять.
• Response j = ki + z - Challenge^modn).
Очевидно, что благодаря равномерному распределению чисел кг величина Response^ равномерно распределена по группе Zn при всех значениях Challenge, е {0,1} (даже если Challenge не является равномерно распределенной случайной величиной) и не зависит от общих входных данных X.
