Zero-knowledge proof ) - это интерактивный протокол, позволяющий одной из сторон (проверяющему, verifier) убедиться в достоверности какого-либо утверждения (обычно математического), не получив при этом никакой другой информации от второй стороны (доказывающего, prover).

Доказательство с нулевым разглашением должно обладать тремя свойствами:

1. Полнота : если утверждение действительно верно, то доказывающий убедит в этом проверяющего.
2. Корректность : если утверждение неверно, то даже нечестный доказывающий не сможет убедить проверяющего за исключением пренебрежимо малой вероятности.
3. Нулевое разглашение : если утверждение верно, то любой даже нечестный проверяющий не узнает ничего кроме самого факта, что утверждение верно.

Общая структура доказательств с нулевым разглашением

Каждый раунд или аккредитация доказательства состоит из трёх этапов. Схематично их можно изобразить следующим образом:

Сначала A выбирает из заранее определенного множества некоторый элемент, который становится её секретом (закрытый ключ). На основе этого элемента вычисляется, а затем публикуется открытый ключ. Знание секрета определяет множество вопросов, на которые А всегда сможет дать правильные ответы. Затем A выбирает случайный элемент из множества, по определенным правилам (в зависимости от конкретного алгоритма) вычисляет доказательство и затем отсылает его B . После этого B выбирает из всего множества вопросов один и просит A ответить на него (вызов ). В зависимости от вопроса, А посылает B ответ . Полученной информации B достаточно, чтобы проверить действительно ли А владеет секретом. Раунды можно повторять сколько угодно раз, пока вероятность того, что A «угадывает» ответы не станет достаточно низкой.

Такая техника называется также «разрезать и выбрать» (cut-and-choose).

Пример

Назовем проверяющую сторону Петей, а доказывающую сторону Димой (в англоязычной литературе обычно используются пары Peggy (от prover ) и Victor (от verifier ). Допустим Диме известен Гамильтонов цикл в большом графе G . Пете известен граф G , но он не знает гамильтонова цикла в нём. Дима хочет доказать Пете, что он знает гамильтонов цикл, не выдавая при этом ни самого цикла, ни какой-либо информации о нём (возможно Петя хочет купить этот гамильтонов цикл у Димы, но перед этим удостовериться, что он у Димы действительно есть).

Для этого Петя и Дима совместно выполняют несколько раундов протокола:

В каждом раунде Петя выбирает новый случайный бит, который неизвестен Диме, поэтому чтобы Дима мог ответить на оба вопроса, нужно чтобы H был в самом деле изоморфен G и Дима должен знать гамильтонов цикл в H (а значит также и в G ). Поэтому после достаточного числа раундов, Петя может быть уверен в том, что у Димы действительно есть гамильтонов цикл в G . С другой стороны, Дима не раскрывает никакой информации о гамильтоновом цикле в G . Более того, Пете сложно будет доказать кому-либо ещё, что он сам или Дима знает гамильтонов цикл в G .

Предположим, что у Димы нет гамильтонова цикла в G и он хочет обмануть Петю. Тогда Диме необходим неизоморфный G граф G" , в котором он всё-таки знает гамильтонов цикл. В каждом раунде он может передавать Пете либо H" - изоморфный G" , либо H - изоморфный G . Если Петя попросит доказать изоморфизм и был передан H , то обман не вскроется. Аналогично, если он просит показать гамильтонов цикл и был передан H" . В таком случае вероятность того, что Дима все-таки обманет Петю после n раундов, равна 1/2 n , что может быть меньше любой заранее заданной величы при достаточном числе раундов.

Предположим, что Петя не узнал гамильтонов цикл, но хочет доказать Васе, что Дима его знает. Если Петя, например, заснял на видео все раунды протокола, Вася едва ли ему поверит. Вася может предположить, что Петя и Дима в сговоре и в каждом раунде Петя заранее сообщал Диме свой выбор случайного бита, чтобы Дима мог передавать ему H для проверок изоморфизма и H" для проверок гамильтонова цикла. Таким образом без участия Димы доказать, что он знает гамильтонов цикл, можно лишь доказав, что во всех раундах протокола выбирались действительно случайные биты.

Злоупотребления

Предложено несколько способов злоупотребления доказательством с нулевым разглашением:

См. также

• Протокол Гиллу-Кискатра

Литература

• A. Menezes, P.van Oorschot, S. Vanstone. Handbook of Applied Cryptography. - CRC Press, 1996. - 816 с. - ISBN 0-8493-8523-7
• Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. - М .: Триумф, 2002. - 816 с. - 3000 экз. - ISBN 5-89392-055-4

Wikimedia Foundation . 2010 .

• Фонвизина, Наталья Дмитриевна
• Чужумово

Смотреть что такое "Доказательство с нулевым разглашением" в других словарях:

доказательство с нулевым разглашением конфиденциальной информации - Непроницаемое доказательство знания; доказательство обладания какой либо информацией, без разглашения этой информации. Тематики защита информации EN zero knowledge proof …

итеративное доказательство с нулевым разглашением конфиденциальной информации - — Тематики защита информации EN zero knowledge iterative proofZKIP … Справочник технического переводчика

не итеративное доказательство с нулевым разглашением конфиденциальной информации - НДНР — [] Тематики защита информации Синонимы НДНР 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) Пусть А знает некоторый… … Википедия

Пусть задана интерактивная система доказательства (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}