<< Предыдущая

стр. 53
(из 82 стр.)

ОГЛАВЛЕНИЕ

Следующая >>

вающая (если отправитель не знает дискретного логарифма В по
основанию G), но теоретико-информационно скрывающая.
Доказательство. Предположим, что Алиса, передав обязатель­
ство М = Da{x) = B^G^^ хочет изменить х на у. Ц,ля этого ей
достаточно найти
г. М
F= —
ВУ'
после чего она может вычислить дискретный логарифм а' = log^^ F
и утверждать, что она посылала пару {а\у), а не (а, ж). Отсюда
следует, что схема вычислительно связывающая.
Допустим, получатель собирается восстановить переданный ему
ж, не дожидаясь стадии раскрытия. Поскольку для данного значения
М и каждого X существует лишь одно а, при котором М = B^G^., то
даже обладая неограниченными вычислительными возможностями,
получатель не в состоянии восстановить а; из М. •
Закончим параграф замечанием, что обе представленные выше
схемы обязательств, основанные на дискретном логарифмировании,
обладают свойством гомоморфности:
D{xi) • D{x2) = G^^ • G^2 = G^^+^2 = D{xi + ^2),
ОагЫ) ' Da2{x2) = B^^ • G^' • B^^ . ^«2 ^
= B^i+^2 . Gf«i-fa2 ^ Da,+a2{xi + X2).
Это свойство нам потребуется при обсуждении протокола голосо­
вания в конце главы.


13.3. Доказательства с нулевым разглашением
Допустим, что Алиса пытается убедить Боба в обладании какой-то
информацией, не сообщая в точности, какими конкретно сведени­
ями она располагает. Именно с таким очевидным противоречием
имеют дело доказательства с нулевым разглашением. В литерату­
ре по доказательствам с нулевым разглашением Алису называют
Глава 13. Протоколы

доказывающей стороной, т.к. именно она хочет что-то доказать,
а Боба — проверяющей стороной (или проверяющим), поскольку в
его намерения входит проверить, действительно ли доказывающий
что-то знает. Мы тоже будем следовать установившейся традиции,
именуя доказывающего Пегги (от англ. prover), а проверяющего —
Виктором (от англ. verifier).
Классический пример доказательств с нулевым разглашением
связан с проблемой изоморфизма графов. Два графа Gi и G2 с одним
и тем же количеством вершин называются изоморфными, если вер­
шины одного из них можно перенумеровать так, чтобы получился
второй. Такая перенумерация ^р называется изоморфизмом графов
и обозначается
(f : Gi • G2.
Поиск изоморфизма между двумя графами — трудная вычислитель­
ная проблема.
Предположим, что Пегги знает какой-то изоморфизм ср между
двумя общеизвестными графами Gi и G2. Назовем (р секретными
исходными данными доказывающей стороны, а графы Gi и G2 —
открытыми, или общими исходными данными. Пегги хочет дока­
зать Виктору, что ей известен изоморфизм указанных графов, ни­
чего не сообщая ему о точной природе изоморфизма. Это делается
с помощью следующего доказательства с нулевым разглашением.
Пегги применяет секретную случайную перестановку ф к вер­
шинам графа G2, получает другой граф i / , изоморфный обоим ис­
ходным, и публикует Н как обязательство. При этом она, есте­
ственно, знает в чем состоит секрет:
(р : Gi » G2,
-
ф : G2 Я,
ф о ip : Gi • Н,
Виктор делает запрос, выбирая число Б G {1,2} и спрашивая об
изоморфизме графов Н и GB- Пегги выдает свой ответ на запрос,
пересылая Виктору либо X — Ф^ либо X — Ф ^^- Протокол выглядит
как
Р V : Я,
V Р : Я,
Р -V: х-
Исследуем вопрос о возможности жульничества со стороны Пегги.
Если Пегги реально не знает изоморфизма (р^ то для корректного
13.S. Доказательства с нулевым разглашением

ответа ей необходимо заранее узнать, какой именно граф Оъ Вик­
тор собирается ей послать. Следовательно, если Пегги пытается об­
мануть проверяющего, она способна дать правильный ответ на за­
прос лишь в 50% случаев. Поэтому повторяя протокол несколько
раз, честная Пегги сможет убедить Виктора в том, что она дей­
ствительно знает упомянутый изоморфизм с малой вероятностью
ошибки.
Теперь стоит выяснить: извлекает ли Виктор какую-либо полез­
ную информацию из протокола, т. е. действительно ли доказатель­
ство Пегги ничего не разглашает? Прежде всего заметим, что Пегги
следует в каждом раунде обмена сообш;ениями в протоколе генери­
ровать новый граф Н. В противном случае у Виктора появляется
возможность тривиального жульничества. Будем считать, что та­
кого не происходит.
Чтобы увидеть, получил ли Виктор скрываемую информацию
в результате работы протокола, нужно посмотреть на его запись и
понять, можно ли что-либо полезное из нее извлечь. Чтобы убедить­
ся, что Виктор реально ничем не пополнил свои знания, достаточно
заметить, что он не смог бы выступать в этом протоколе в качестве
Пегги. Следовательно, Виктор не сможет убедить кого-то другого в
своем знании изоморфизма. Тем самым можно сделать вывод: Пегги
своим доказательством не открыла тайны изоморфизма.
Виктор может сделать правдоподобные записи протокола без
участия Пегги, используя следуюп];ую имитацию:
- выбрать В G {0,1},
- переставив произвольным образом вершины графа G^, полу­
чить изоморфный граф Н и соответствуюп1;ий изоморфизм х?
- сфабриковать запись протокола:
Р V : Я,
V - Р : В,
Р ^ : X.

Таким образом, диалоговая природа протокола показывает, что он
осуш;ествляет доказательство с нулевым разглашением. Отметим,
что три фазы
обязательство • запрос • ответ
являются характерной чертой таких протоколов.
Протоколы доказательств тоже можно разделить на типы по
степени криптостойкости. К одному типу отнести доказательства,
Глава 13. Протоколы

стойкие относительно противника с ограниченными вычислитель­
ными возможностями, а к другому — с неограниченными. Ясно, что
к основным свойствам систем интерактивных доказательств отно­
сятся
- Полнота: если Пегги действительно знает то, что собирает­
ся доказать, то Виктор должен принять ее доказательство с
вероятностью 1.
- Корректность: если Пегги не знает, что доказывает, то веро­
ятность убеждения Виктора должна быть крайне мала.
Будем считать, что Виктор имеет вычислительные средства, огра­
ниченные полиномиальным временем, а Пегги обладает неограни­
ченными вычислительными возможностями.
Как мы уже отметили, свойство нулевого разглашения связа­
но с концепцией имитации. Предположим, что справедливые записи
протокола (которые действительно получились в результате работы
протокола, осуществившего доказательство) обозначаются через V,
а возможные имитации — через S. Надежность протокола, таким
образом, связана с тем, насколько S похоже на V.
Говорят, что доказательство обладает абсолютно нулевым раз­
глашением, если нападаюш;ий, обладая неограниченными вычисли­
тельными возможностями, не может отличить V от S. Если же от­
личить их друг от друга не в состоянии лишь противник с огра­
ниченными вычислительными возможностями, будем говорить, что
доказательство имеет вычислительно нулевое разглашение.
Обладая неким секретом, можно использовать доказательство
с нулевым разглашением как схему идентификации. Недостаток пре­
ды душ;его примера с изоморфизмом графов заключается в его не­
практичности. Данные, которые при этом передаются, занимают
большой объем, причем протокол необходимо повторять несколько
раз, чтобы абсолютно убедить Виктора в знании секрета.
К счастью, при обсуждении подписи Шнорра в главе 10 мы уже
видели протокол, имеюш;ий более высокую пропускную способность.
Предположим, что Пегги знает х — \O%Q Y В конечной абелевой груп­
пе А простого порядка Q. Протокол, доказываюш;ий это знание, мо­
жет выполняться следуюш;им образом:
Р • V : R — G^ ]\j{Si случайного А;,
V Р : Е,
Р V : S = k + xE (modQ).
Виктор убеждается в том, что Пегги знает дискретный логарифм
13.3, Доказательства с нулевым разглашением 345

ж, проверяя, что
R = G^Y-^.
Рассмотрим протокол более детально. Если Пегги не знает дискрет­
ного логарифма д;, то она может попытаться обмануть Виктора. Ей
удастся это сделать с вероятностью l / Q , что существенно меньше
1/2, которая присутствовала в протоколе, основанном на изомор­
физме графов.
Действительно ли Виктор не получает полезной информации из
протокола? Ответ отрицателен, поскольку Виктор может имитиро­
вать записи протокола следующим образом:
- генерировать случайное число Е по модулю Q;
- вычислить R = G^Y˜^,
- выдать записи:
Р V : Д,
V Р : Е,
Р V : S,

Эта имитация приобретет важное значение при изучении стойкости
подписи Шнорра в главе 17.
Проблема, связанная с доказательствами с нулевым разглашени­
ем, состоит в их интерактивной природе:
Р V : СО,
V Р : СН,
Р V : RE,
где СО — обязательство, СН — запрос и RE — ответ. Их лег­
ко можно сделать и не интерактивными (автономными), если заме­
нить запрос вычислением криптографической хэш-функции, приме­
ненной к обязательству: СН = Н{СО). Идея здесь состоит в том,
что доказывающий не может угадать запрос перед отправкой обя­
зательства, поскольку А^ля этого нужно было бы инвертировать хэш-
функцию. Автономный протокол теряет свойство нулевого разгла­
шения, поскольку его нельзя имитировать. Кроме того, обладающая
неограниченными вычислительными ресурсами Пегги способна ин­
вертировать хэш-функцию. Поэтому нужно ограничить возможно­
сти вычислений доказывающей стороны. Как только мы это сде­
лаем, то будем говорить, что доказывающий приводит аргумент
с нулевым разглашением (в отличие от термина «доказательство с
нулевым разглашением»).
Глава 13, Протоколы

К аргументу хэш-функции можно добавить и другие данные,
например, сообщение. Таким способом мы превращаем диалоговое
доказательство какого-то знания в схему цифровой подписи:
СН - Я ( С О | | СООБЩЕНИЕ).
Заметьте, что при использовании в доказательстве знания дискрет­
ного логарифма, хэш-значения обязательства и сообщения в каче­
стве запроса, мы получаем в точности схему подписи Шамира.
Закончим параграф рассказом о протоколе, являющемся аргу­
ментом с нулевым разглашением, который потребуется при обсу­
ждении схемы электронного голосования. Рассмотрим схему обяза­
тельств
Da{x) = B'^G^
где А = {G) — конечная абелева группа простого порядка Q^ В —
элемент в Л, чей дискретный логарифм по основанию G неизвестен,
X — обязательство, а — случайное уникальное число. Нас интересу­
ет случай, когда обязательство принимает значение плюс или минус
единица, т.е. a;G{ — 1,1}. Нри реализации этой схемы в протоколе
голосования нам будет важно доказать, что переданное число дей­
ствительно лежит в указанном множестве, не раскрывая его истин­
ного значения. С этой целью осуществляется следующий протокол:
- Вместе с публикацией обязательства Da{x) Пегги выбирает
случайные числа d, г и г^; по модулю Q и публикует Ai и А2,
где

G''{Da{x)B)-'^, еслид: = 1,
Ai =
G^, если X = —1;
G^, если ж = 1,
А2-
G^(Da(a;)B-i)-^ если а; = - 1 .

Виктор высылает Пегги случайный запрос С.
Пегги отвечает
d! = С -d, г' = w + ad',
и выводит значения

г (d,d',r,r'), если ж = 1,
I id',d,r',r), если X = —1.
13.4- Система электронного голосования

- Виктор проверяет истинность равенств:
C = Di= D2,


G''' = A2{Da{x)B-Y'-
Дабы убедиться в работоспособности протокола, нам надо пока­
зать, что
1. Если Пегги отвечает правдиво, то Виктор сможет убедиться
в истинности трех равенств.
2. Если Пегги передала число, отличное от ± 1 , то ей будет за­
труднительно выдать правильный ответ на запрос Виктора.
3. Протокол не дает Виктору никакой информации относитель­
но переданного значения, кроме того, что оно принадлежит
множеству {—1,1}.
Оставим проверку перечисленных пунктов читателю. Заметим, что
этот протокол можно выполнять и в автономном режиме, если опре­
делить С как
С = H{Ai\\A2\\Da{x)).

13.4. Система электронного голосования
Здесь представлена система электронного голосования, использую­
щая достижения, описанные как в этой, так и в предыдущих главах.
При этом мы хотим показать, как основные теоретические разра­
ботки комбинируются в сложном приложении, имеющем практиче­
ское значение. Будем предполагать, что в голосовании участвуют т
лиц с правом голоса и п счетных комиссий. Использование большо­
го числа счетных комиссий обеспечивает анонимность голосующего
и предотвращает возможность фальсификации результатов голосо­
вания. Будем также считать, что избиратели могут отдать свой
голос только за одного из кандидатов, например, демократа или
республиканца.
Система голосования, с которой мы собираемся познакомиться,
обладает следующими семью свойствами:

<< Предыдущая

стр. 53
(из 82 стр.)

ОГЛАВЛЕНИЕ

Следующая >>