Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
Рассматривая IP-протоколы, необходимо изучить два вопроса. Вопрос 1. Сколько информации получит проверяющая сторона в ходе интерактивного доказательства? Вопрос 2. Сколько раундов должна выполнить доказывающая сторона, чтобы убедить проверяющего?
Идеальным ответом на первый вопрос был бы "нисколько", или "нуль". IP-протокол, обладающий таким свойством, называется протоколом с нулевым разглашением или ZK-протоколом (zero-knowledge — ZK). Второй вопрос важен не только для практических приложений, но и для теории вычислительной сложности, поскольку решение этой проблемы связано с получением более низкой оценки сложности.
Глава содержит систематическое введение в теорию протоколов с нулевым разглашением (включая ответы на поставленные выше вопросы) и описание связанных с этим понятий. Эти понятия весьма важны, однако многие из них являются результатом многолетних исследований и не опубликованы в учебниках. Чтобы упростить изложение, для их иллюстрации используются конкретные протоколы.
18.1.1 Структурная схема главы
В разделе 18.2 изложены основные понятия, связанные с IP-протоколами.* В разделе 18.3 описываются разнообразные ZK-свойства IP-протоколов. В разделе 18.4 проводится дифференциация между ZK-доказательством и ZK-apry-ментацией. Оценки вероятностей ошибок в двусторонних протоколах приводятся в разделе 18.5. Раздел 18.6 посвящен проблеме эффективности ZK-протоколов, а раздел 18.7 — неинтерактивным ZK-протоколам.
18.2 Основные определения
Протоколы с нулевым разглашением имеют не только огромное прикладное! значение в криптографии, но и лежат в основе IP-протоколов, играющих важную роль в теории вычислительной сложности. В результате эти протоколы имеют большое количество определений. Приведем определения, имеющие отношение к прикладной криптографии.
Глава 18. Протоколы с нулевым разглашением
677
18.2.1 Вычислительная модель
Отвлечемся пока от вопросов, связанных с эффективностью и возможностью раскрытия информации.
Рассмотрим вычислительную модель интерактивной системы доказательства (interactive proof system), которую предложили Голдвассер, Микали и Раков [126]. Обозначим основную модель протокола интерактивных доказательств через (Р, V), где Р — доказывающая (prover), а V — проверяющая сторона (verifi-cator). Как правило, протокол (Р, V) предназначен для проверки принадлежности определенного предложения языку, заданному над ачфавитом {0,1}*. Общее определение языка приведено в разделе 18.2.2, а более узкое определение, связанное с криптографическими приложениями, формулируется в разделе 18.2.3.
Пусть L—язык над алфавитом {0,1}*. Стороны Ри V получают образец хЕ L, представляющий собой общие входные данные (common input). Доказательство принадлежности образца обозначается как (Р, V)(x). Обе стороны протокола связаны каналом связи, через который они обмениваются информацией.
ai,bi,a2,b2,...,ae,be. (18.2.1)
Эта последовательность сообщений называется стенограммой доказательства (proof transcript). В стенограмме доказательства данные, передаваемые пользователем Р, называются стенограммой доказывающей стороны (prover's transcript). Они чередуются с данными, передаваемыми пользователем V, которые называются стенограммой проверяющей стороны (verifier's transcript). Как общая длина стенограммы доказательства ?, так и длина каждой стенограммы |foj|(z = = 1,2,...,?) ограничена полиномом, зависящим от параметра |ж|. Доказательство принадлежности образца (Р, V) (х) языку L также должно быть ограничено полиномом, зависящим от объема входных данных |ж|. Результат работы протокола записывается в виде
(Р, V){x) е {Принять, Отклонить}.
Эти два значения означают, что проверяющая сторона либо подтверждает, либо опровергает утверждение хеЬ, высказанное доказьшающей стороной Р. Поскольку система (Р, V) является вероятностной, при каждом х результат (Р, V)(x) является случайной величиной, зависящей от обших входных данных х, закрытых входных данных (private input) пользователя Р и некоторых случайных входных данных (random input), общих для пользователей Р и q. Более того, элементы стенограммы доказательства (18.2.1) также являются случайными величинами.
Поскольку протокол (Р, V) является двусторонней игрой, естественно предположить, что каждая сторона стремится получить дополнительное преимущество. С одной стороны, доказывающая сторона Р должна быть заинтересована
678
Часть VI. Криптографические протоколы
в результате (Р, V)(x) = Принять, даже если х ф L. Доказывающая сторона, руководствующаяся такой жульнической стратегией (cheating prover), обозначается как Р. С другой стороны, проверяющая сторона V должна быть заинтересована в раскрытии информации о закрытых входных данных игрока Р. Проверяющая сторона, следующая такой нечестной стратегии (dishonest verifier), обозначается как V.
18.2.2 Формальное определение протоколов интерактивного доказательства
Дадим определение протокола интерактивного доказательства.
Определение 18.1. Пусть L — язык, заданный над алфавитом {О,1}*. IP-npomo- j кол (Р, V) называется системой интерактивного доказательства для языка L, если
