Пост-квантовые доказательства с нулевым разглашением. Доказательства с нулевым разглашением: иллюстрированный пример

Пусть задана интерактивная система доказательства (P,V,S).
В определении интерактивной системы доказательства ранее не предполагалось, что V может быть противником (предполагалась только возможность существования нечестного участника Р"). Но V может оказаться противником, который хочет выведать у Р какую- либо новую полезную информацию об утверждении S. В этом слу-чае Р может не хотеть, чтобы это случилось в результате работы
протокола интерактивной системы доказательства. Таким
28 Запечников С. В. Криптографические протоколы и их прішеиеиие
образом приходим к идее протокола доказательства с нулевым раз-глашением знания (zero-knowledge proof). Нулевое разглашение зна-ния подразумевает, что в результате работы протокола интерактивной системы доказательства V не увеличит свои знания об утвер-ждении S, или, другими словами, не сможет извлечь никакой информации о том, почему S истинно.
Как и ранее, в протоколе предварительно формулируется неко-торое утверждение S, например о том, что некоторый объект w об-ладает свойством L: we L. В ходе протокола Р и V обмениваются сообщениями. Каждый из них может генерировать случайные числа и использовать их в своих вычислениях. В конце протокола V дол-жен вынести свое окончательное решение о том, является ли S ис-тинным или ложным.
Цель Р всегда состоит в том, чтобы убедить V в том, что S ис-тинно, независимо от того, истинно ли оно на самом деле или нет, т. е. Р может быть активным противником, а задача V - проверять аргументы Р. Цель участника V заключается в том, чтобы вынести решение, является ли S истинным или ложным. Как и ранее, V имеет полиномиально ограниченные вычислительные возможности, а именно время его работы ограничено некоторым полиномом от
длины доказываемого утверждения: tРассмотрим теперь примеры протоколов доказательства с нулевым разглашением знания.
1. «Задача о пещере Али-Бабы». Имеется пещера, план которой показан на рис. 1.2. Пещера имрет дверь с секретом между точками С и D. Каждый, кто знает волшебные слова, может открыть эту дверь и пройти из С в D или наоборот. Для всех остальных оба хода пещеры ведут в тупик.
Пусть Р знает секрет пещеры. Он хочет доказать V знание этого секрета, не разглашая волшебные слова. Вот протокол их общения:
V находится в точке А;
Р заходит в пещеру и добирается либо до точки С, либо до точки D\
После того как Р исчезает в пещере, V приходит в точку В, не зная, в какую сторону пошел Р\
V зовет Р и просит его выйти либо из левого, либо из правого коридора пещеры согласно желанию V;
Р выполняет это, открывая при необходимости дверь, если, конечно, он знает волшебные слова;
Р и V повторяют шаги (1) - (5) п раз.

После п раундов протокола вероятность сократится до 1/2".
2. Доказательство изоморфизма графов. Р хочет доказать V изо-морфизм графов Go и Gb ПустьG, = (p(G0):G0 = G, где ф - пре-образование изоморфизма; т - мощность множества N вершин графов. В табл. 1.4 приведен протокол доказательства данного утвер-ждения.
Поясним строение этого протокола. На шаге (1) участник Р создает случайный граф Я, изоморфный G\. На шаге (2) участник V, выбирая случайный бит а = {0Д}, тем самым просит доказать, что
Н ~G0 либо что Н « Gj. На шаге (3) участник Р посылает участни-ку V преобразование \|/, которое он строит таким образом, что при а = 1 в результате применения этого преобразования к графу Gu по-лучается граф F1 = TtG, = Н. а при а = 0 в результате применения этого преобразования к графу Ga получается граф F0 =
зо Запечников С. В. Криптографические протоколы и их применение
= 7i((p(G0))~7iG] = #, На шаге (4) участник V, выполняя проверку равенства графов, тем самым определяет, выполнено ли условие
Н = Fa. Шаги (1) - (4) повторяются т раз. Если во всех т раундах этого протокола результат проверки оказывается положительным, V принимает доказательство.
Таблица 1.4. Протокол доказательства изоморфизма графов Р V 1 % - случайная перестановка вершин, вычисляет H = nGl 2 f п, если (а -1),
V = 1 / ч 1 л о ф, если (а = 0) -> т раз 4 Вычисляет граф \j/Ga и сравнивает: Н =\jfGa 5 Принимает доказательство тогда и только тогда, когда для Vm
Этот протокол действительно является протоколом с нулевым разглашением знаний, так как в случае изоморфных G0 ~ Gx участ-ник V не получает никакой информации, кроме изоморфизмов гра-фов G0 и G\ с какими-то их случайными перенумерациями, которые он мог бы получить и самостоятельно, выбирая случайный бит а и перенумеровывая случайным образом граф Ga .
3. Доказательство знания дискретного логарифма х числа X. Перед началом работы протокола задаются открытые величины: р,
q - простые числа, такие, что q\(p -1), элемент g е Z*, число X. До- ]. Базовые криптографические протоколы 31
называющему Р известна секретная величина x\xТаблица 1.5. Протокол доказательства знания дискретного логарифма Р V I r&RZ
М = g (mod р) 2 А. Доказательство знания представления числа у в базисе (zero- knowledge proof of knowledge of у representation). Перед началом работы протокола задаются открытые величины, известные всем уча-стникам: простые числа р, q, элементы y,gvg2,..., gk Є Gq. Доказы-вающему P известны секретные величины ара 2,...,ake ZQ: у =
= 8і" " 8г1""> знание которых он должен доказать V, не разгла-шая самих этих величин. Протокол представлен в табл. 1.6.
Таблица 1.6. Протокол доказательства знания представления
числа в базисе Р V 1 rl.r2,...,rk. ЄІ{ Zq, 2 5. Доказательство знания представления множества чисел в соответствующих базисах (zero-knowledge proof of knowledge of equality of representation of all y(j) in the respective bases). Перед началом работы протокола задаются открытые величины, извест-
W I >\
ные всем участникам: простые числа р, q, элементы у, 82^є для некоторых (/). Доказывающему Р известны сек-ретные величины 0С[,а2,...,а,. є Zq, такие, что для V/ у^ =
= (і^) " 1 > знание которых он должен доказать V,
не разглашая самих этих величин. В табл. 1.7 приведен протокол, который решает эту задачу.
Таблица 1.7. Протокол доказательства знания множества чисел
в соответствующих базисах Р V 1 rvr21...lrkeR ля У/ 2 (АиП«іТ-(ьТ-
6. Доказательство знания мультипликативной связи «депониро-ванных» величин (zero-knowledge proof of knowledge of multiplicative rela-tion between committed values). Элемент X = gx циклической подгруп-пы простого порядка, в которой задача дискретного логарифмирования считается вычислительно-сложной, называется депонированной вели-чиной (committed value), представляющей секретную величину х. Пусть
d - неизвестный элемент, такой, что h = gd . Перед началом работы протокола задаются открытые величины: простые числа р, q, элементы А, В, С Є Gq . Доказывающему Р известны секретные величины
a, a, b, Ь, с, с, такие, что с = ab, A = gah"\ В = gbhb, С = gche. Знание их он и должен доказать V, не разглашая самих величин. В табл. 1.8 при-веден протокол такого доказательства.
Таблица 1.8. Протокол доказательства знания мультипликативной связи депонированных величин Р V 1 М=і">/Ї, j Mt = gx-h*\ ¦ M2= Bx ¦ h"1 2 =CK-M2
разглашением знания
Таблица 1.9. Структура протоколов доказательства с нулевым P S: x є L- доказываемое утверждение, h - dp, общедоступные параметры и величины, s - секретные данные дока-зывающего о том, почему S истинно, г- случайное число V 1 rp- случ., 2 rv - случай-ное число,
с = ЛМ Обобщим рассмотренные примеры и сформулируем ряд определений. В общем виде протокол интерактивного доказательства с ну-левым разглашением знания (табл. 1.9) состоит из четырех шагов:
Окончание табл. 1.9 Р S: хе L- доказываемое утверждение, h - др. общедоступные параметры и величины, s - секретные данные дока-зывающего о том, почему S истинно, г - случайное число V 3 R = f3(C,x) 4
доказывающий передает проверяющему так называемое сви-детельство (witness -W)- результат вычисления однонаправленной функции от секретной величины, знание которой он доказывает;
проверяющий посылает ему случайный запрос;
доказывающий отвечает на этот запрос, причем ответ зависит как от случайного запроса, так и от секретной величины, но из него вычислительно невозможно получить эту секретную величину;
получая ответ, V проверяет его соответствие «свидетельству», переданному на первом шаге.
Рассмотрим основные принципы построения доказательств с ну-левым разглашением знания: что подразумевает свойство нулевого разглашения знания.
В теории доказательств с нулевым разглашением знания Р и V рассматриваются как «черные ящики» (рис. 1.3).
Пусть \тр }, \}Пу } - совокупность всех сообщений, передаваемых от Р к V (соответственно от У к Р), каждое из которых является слу-чайной величиной, и, таким образом, {x,h,rv,{mp},{mv}} = = viewpy Тематики защита информации Синонимы НДНР EN non iterative zero knowledge proofNIZK … Справочник технического переводчика

Криптография - Немецкая криптомашина Lorenz использовалась во время Второй мировой войны для шифрования самых секретных сообщений Криптография (от др. греч … Википедия

Список алгоритмов - Эта страница информационный список. Основная статья: Алгоритм Ниже приводится список алгоритмов, группированный по категориям. Более детальные сведения приводятся в списке структур данных и … Википедия

Криптограф - Немецкая криптомашина Lorenz, использовалась во время Второй мировой войны для шифрования самых секретных сообщений Криптография (от греч. κρυπτός скрытый и γράφω пишу) наука о математических методах обеспечения конфиденциальности… … Википедия

Программируемые алгоритмы - Служебный список статей, созданный для координации работ по развитию темы. Данное предупреждение не устанавл … Википедия

SRP - Secure Remote Password Protocol (SRPP) протокол парольной аутентификации, устойчивый к прослушиванию и MITM атаке и не требующий третьей доверенной стороны. SRP содержит некоторые элементы из других протоколов обмена ключами и идентификации … Википедия

Протокол Фиата - Протокол Фиата Шамира это один из наиболее известных протоколов идентификации с нулевым разглашением (Zero knowledge protocol). Протокол был предложен Амосом Фиатом (англ. Amos Fiat) и Ади Шамиром (англ. Adi Shamir) Пусть А… … Википедия

Протокол Фиата-Шамира - Протокол Фиата Шамира это один из наиболее известных протоколов идентификации с нулевым разглашением (Zero knowledge protocol). Протокол был предложен Амосом Фиатом(англ. Amos Fiat) и Ади Шамиром(англ. Adi Shamir) Пусть А знает некоторый… … Википедия

Одна из основных задач криптографии представляет собой двустороннюю интерактивную игру, в которой один участник (доказывающая сторона) доказывает другому участнику (проверяющей стороне) истинность утверждения, не раскрывая сущности доказательства. В этом случае проверяющий не может самостоятельно оценить истинность утверждения, поскольку ему неизвестна информация, доступная доказывающему. Эта игра называется протоколом (системой) интерактивного доказательства или IP-протоколом (interactive proof - IP). Доказательство, осуществляемое IP-протоколом, можно назвать “секретным доказательством” (“proof in the dark”). Секретность этого доказательства состоит в том, что, во-первых, проверяющая сторона, убедившись в истинности доказываемого утверждения, не способна самостоятельно повторить доказательство, и, во-вторых, после завершения протокола никто из посторонних не способен понять ни одного сообщения, которыми обменивались доказывающая и проверяющая стороны.
Представим себе, что утверждение, которое необходимо доказать, не раскрывая сущности доказательства, является решением какой-либо знаменитой нерешенной математической задачи. В этом случае доказывающая сторона, опасающаяся плагиата, может пожелать скрыть технические детали доказательства от потенциально нечестного рецензента. Для этого она должна провести “секретное” доказательство, убедив рецензента (играющего роль проверяющей стороны в IP-протоколе) в корректности выводов, не давая никакой дополнительной информации.
Во многих реальных приложениях существуют намного более серьезные основания для проведения “секретных” доказательств. Как правило, IP-протоколы применяются для аутентификации сущностей. В отличие от обычных протоколов аутентификации , в которых пользователи ставят цифровые подписи, в IР-протоколе доказывающая сторона, подлежащая аутентификации , не желает, чтобы сообщения стали доступными кому-либо, кроме проверяющей стороны, и выполняет “секретную” аутентификацию . Кроме того, IP-протоколы часто применяются для того, чтобы доказать, что часть скрытой информации имеет определенную структуру. Это необходимо в некоторых секретных приложениях (например, при проведении электронных аукционов), в которых скрытый номер (лот) должен находиться в допустимом диапазоне (например, необходимо доказать, что х > у без раскрытия значений и , представляющих собой предложения цены).
Рассматривая IP-протоколы, необходимо изучить два вопроса.

• Вопрос 1. Сколько информации получит проверяющая сторона в ходе интерактивного доказательства ?
• Вопрос 2. Сколько раундов должна выполнить доказывающая сторона, чтобы убедить проверяющего?

Идеальным ответом на первый вопрос был бы “нисколько”, или “нуль”. IP- протокол, обладающий таким свойством, называется протоколом с нулевым разглашением или ZK-протоколом (zero-knowledge - ZK). Второй вопрос важен не только для практических приложений, но и для теории вычислительной сложности, поскольку решение этой проблемы связано с получением более низкой оценки сложности.

История развития

Доказательство нулевым разглашением был придумано и разработано следующими учеными: Шафи Гольдвассером, Сильвио Микалием и Чарльз Реккофом, и опубликовано ими в статье «Знание и сложность интерактивной системы с доказательством» в 1985 году. Эта работа представила иерархию интерактивных систем с доказательством, основываясь на объеме информации о доказательстве, которой необходимо передать от доказывающего до проверяющего. Ими так же было предложено первое доказательство конкретно поставленного доказательства с нулевым разглашением - квадратичного вычета по модулю m. Впоследствии, дополнив свою работу, они выиграли первую премию Геделя в 1993 году.
Продолжение...

Нулевое разглашение

Вычислительная модель

Обозначим основную модель протокола интерактивных доказательств через (Р,V), где Р - доказывающая (prover), а V - проверяющая сторона (verifier). Как правило, протокол (Р,V) предназначен для проверки принадлежности определенного предложения языку, заданному над алфавитом {0,1}*.
Пусть L - язык над алфавитом {0,1}*. Стороны Р и V получают образец хϵL, представляющий собой общие входные данные (common input). Доказательство принадлежности образца обозначается как (Р,V)(x). Обе стороны протокола связаны каналом связи, через который они обмениваются информацией.
Результат работы протокола записывается в следующем виде: (Р,V)(x) ϵ {Принять, Отклонить}.
Эти два значения означают, что проверяющая сторона либо подтверждает, либо опровергает утверждение хϵL, высказанное доказывающей стороной Р. Поскольку система (Р,V) является вероятностной, при каждом х результат (Р,V)(x) является случайной величиной, зависящей от общих входных данных х, закрытых входных данных (private input) пользователя Р и некоторых случайных входных данных (random input), общих для пользователей Р и Q.
Поскольку протокол (Р,V) является двусторонней игрой, естественно предположить, что каждая сторона стремится получить дополнительное преимущество. С одной стороны, доказывающая сторона Р должна быть заинтересована в результате принятия x, даже если оно не принадлежит L. Доказывающая сторона, руководствующаяся такой жульнической стратегией (cheating prover), обозначается как Р’. С другой стороны, проверяющая сторона V должна быть заинтересована в раскрытии информации о закрытых входных данных игрока Р. Проверяющая сторона, следующая такой нечестной стратегии (dishonest verifier), обозначается как V’.
Предположим, что на вопрос 1 существует идеальный ответ (Р,V) - протокол с нулевым разглашением, т.е. пользователь V (или V’) убеждается в корректности утверждения пользователя Р, не узнав ничего нового о его закрытых входных данных.
Для того чтобы протокол (Р,V) обладал этим свойством, необходимо ограничить вычислительную мощь пользователя V (или V’) полиномом, зависящим от размера его входной информации. Очевидно, что без этого ограничения нельзя гарантировать нулевое разглашение, поскольку пользователь V, обладающий неограниченными вычислительными ресурсами может самостоятельно раскрыть секретные входные данные пользователя Р.

Формальное определение протоколов интерактивного доказательства

Дадим определение протокола интерактивного доказательства . Пусть L - язык, заданный над алфавитом (0,1}*. IР-протокол (Р,V) называется системой интерактивного доказательства для языка L, если

и

где числа Ɛ и ϐ являются константами, удовлетворяющими условиям Ɛϵ(1/2;1], ϐϵ}