1.3.2. Доказательства с нулевым разглашением знания
В определении интерактивной системы доказательства ранее не предполагалось, что 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< p(jw|). В силу этого он са-мостоятельно, без помощи Р, не способен распознать истинность высказывания S.
Вычислительные возможности Р никак не ограни-чиваются.Рассмотрим теперь примеры протоколов доказательства с нулевым разглашением знания.
1. «Задача о пещере Али-Бабы». Имеется пещера, план которой показан на рис. 1.2. Пещера имрет дверь с секретом между точками С и D. Каждый, кто знает волшебные слова, может открыть эту дверь и пройти из С в D или наоборот. Для всех остальных оба хода пещеры ведут в тупик.
Пусть Р знает секрет пещеры. Он хочет доказать V знание этого секрета, не разглашая волшебные слова. Вот протокол их общения:
V находится в точке А;
Р заходит в пещеру и добирается либо до точки С, либо до точки D\
После того как Р исчезает в пещере, V приходит в точку В, не зная, в какую сторону пошел Р\
V зовет Р и просит его выйти либо из левого, либо из правого коридора пещеры согласно желанию V;
Р выполняет это, открывая при необходимости дверь, если, конечно, он знает волшебные слова;
Р и V повторяют шаги (1) - (5) п раз.
Если Р не знает секрета двери, вероятность того, что V попросит его выйти из того же коридора, в который он вошел, равна 1/2.
После п раундов протокола вероятность сократится до 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 <г а = {0,1}- случ. 3 Посылает преобразование V}/, такое, что
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<=Zq% gx = X , знание которой он должен доказать V, не разглашая самой секретной величины. В табл. 1.5 показано решение этой задачи.
Таблица 1.5. Протокол доказательства знания дискретного логарифма
Р V
I r&RZ М = g (mod р)
2 <г
3 /?7 = /- +xfl(modg)
4 g'^X*-M(modp)
А. Доказательство знания представления числа у в базисе (zero- knowledge proof of knowledge of у representation). Перед началом работы протокола задаются открытые величины, известные всем уча-стникам: простые числа р, q, элементы y,gvg2,..., gk Є Gq. = 8і' ' 8г1"'> знание которых он должен доказать V, не разгла-шая самих этих величин. Протокол представлен в табл. 1.6. Таблица 1.6. Протокол доказательства знания представления числа в базисе
Р V
1 rl.r2,...,rk. ЄІ{ Zq,
2 <-
3 /77,. = /;. +a}R, i=l,k
4
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/ у^ = = ( знание которых он должен доказать 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 <-
3 y-d+bR, z-x + aR, w = s + bR, w, = J, + aR, w2 = s2 + (c - ab^j R
4 gy-hw = BR-M, g? - A"'1 =Ar -M,, B:-hw> =CK-M2
разглашением знания Таблица 1.9. с = ЛМ
Обобщим рассмотренные примеры и сформулируем ряд определений. В общем виде протокол интерактивного доказательства с ну-левым разглашением знания (табл. 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[x,h) - это ансамбль случайных величин протокола, на-блюдаемых извне (внешним наблюдателем), [x,/z,rv«,{;«p},{wzv}} = = MV. (x,h)~ это ансамбль случайных величин, получаемых в ре-зультате работы полиномиального моделирующего алгоритма (simu-lator), который выполняется внешним наблюдателем (противником) самостоятельно. с Если величины viewp v(x>h)~Mу>(х,}г) вычислительно-неразли-чимы за полиномиальное время (т. х h Рис. 1.3. Случайные величины, наблюдаемые в протоколе доказательства с нулевым разглашением знания: а - противник наблюдает протокол извне; б - противник самостоятельно моделирует протокол Если величины viewpv{x,h)~ Mv>(x,h) одинаково распределены над множеством случайных величин, то говорят, что протокол обеспечивает абсолютно нулевое разглашение знания (perfect zero- knowledge ). Система (P,V,S) называется интерактивной системой дока-зательства с нулевым разглашением знания для языка L, если она: является интерактивной системой доказательства для языка L (т. е. обладает свойствами полноты и корректности); обладает свойством нулевого разглашения знания. Пусть S - утверждение вида we L, где w - слово, L - язык в двоичном алфавите. Язык L имеет интерактивную систему дока-зательства с абсолютно нулевым (вычислительно нулевым) разгла-шением знания,если: 1) существует интерактивная система доказательства для языка L; Запечников С. В. Криптографические протоколы и их применение 2) для любого полиномиально ограниченного участника V' ин-терактивный протокол (P,V\S) является интерактивной системой доказательства с абсолютно нулевым (вычислительно нулевым) раз-глашением знания для языка L. Класс языков, обладающих доказательствами с абсолютно нуле-вым разглашением знания, обозначается PZK, с вычислительно-ну-левым - ZK. Справедливо следующее соотношение: BPP^PZK^ZK^IP. Доказаны следующие основные теоремы о доказательствах с нулевым разглашением знания: Теорема 1 (Goldreich О., Krawchyk Н.). Последовательное вы-полнение двух протоколов с нулевым разглашением знания является протоколом с нулевым разглашением знания. Теорема 2 (Goldreich О., Krawchyk Н.). Параллельное выполне-ние протоколов с нулевым разглашением знания не обязательно приводит к протоколу с нулевым разглашением знания. Среди всех протоколов доказательства с нулевым разглашением знания выделяют класс протоколов доказательства знания (proof of knowledge). Например, доказательство знания чисел р, q, таких, что pq — n есть доказательство знания, но доказательство того, что п - составное число, доказательством знания не является - это так называемое доказательство обладания (proof of possession). Но доказательство знания не обязательно должно быть доказа-тельством с нулевым разглашением знания, так как можно просто сообщить секрет другой стороне протокола: при этом сообщивший докажет знание секрета, но тем самым разгласит секрет. Далее в различных приложениях криптографии, в частности в протоколах аутентификации и в схемах электронных платежей, будут встречаться протоколы доказательства знания с нулевым разглашением зна-ния (zero-knowledge proof of knowledge - ZKPK). Существуют специ-альные разновидности протоколов доказательства знания с нулевым разглашением знания: протоколы группового и «скрытого» доказа-тельства знания и др.
