Криптографические протоколы

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

того, что, не зная волшебных слов, Антон может выходить только с той

стороны, с которой зашел. Следовательно, только в 50 % всех случаев Антон

сумеет обмануть Бориса, сумев выйти именно с той стороны, с которой тот

попросит. Если количество экспериментов равно n, то Антон успешно пройдет

все испытания только в одном случае из 2n. На практике можно ограничиться

n=16. Если Антон правильно исполнит приказ Бориса во всех 16 случаях,

значит, он и вправду знает волшебные слова.

Пример с пещерой является очень наглядным, но имеет существенный

изъян. Борису будет значительно проще проследить, как в точке B Антон

поворачивает в одну сторону, а потом появляется с противоположной стороны.

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

Поэтому предположим, что Антону известны не какие-то там волшебные

слова типа "Сезам, откройся". Нет, Антон владеет более интересной

информацией - он первым сумел справиться с труднорешаемой задачей. Чтобы

доказать этот факт Борису, Антону совсем не обязательно публично

демонстрировать свое решение. Ему достаточно применить следующий протокол

доказательства с нулевым разглашением конфиденциальной информации:

1. Антон использует имеющуюся у него информацию и

сгенерированное случайное число, чтобы свести труднорешаемую

задачу к другой труднорешаемой задаче, изоморфной исходной

задаче. Затем Антон решает эту новую задачу.

2. Антон задействует протокол предсказания бита для найденного

на шаге 1 решения, чтобы впоследствии, если у Бориса возникнет

необходимость ознакомиться с этим решением, Борис мог бы

достоверно убедиться, что предъявленное Антоном решение

действительно было получено им на шаге 1.

3. Антон показывает новую труднорешаемую задачу Борису.

4. Борис просит Антона

или (а) - доказать, что две труднорешаемые задачи (старая и

новая) изоморфны,

или (б) - предоставить решение, которое Антон должен был найти

на шаге 1, и доказать, что это действительно решение задачи, к

которой Антон свел исходную задачу на том же шаге.

5. Антон выполняет просьбу Бориса.

6. Антон и Борис повторяют шаги 1-6 n раз, где n - параметр

протокола.

Труднорешаемые задачи, способ сведения одной задачи к другой, а также

случайные числа должны по возможности выбираться так, чтобы у Бориса не

появилось никакой информации относительно решения исходной задачи даже

после многократного выполнения шагов протокола.

Не все труднорешаемые задачи могут быть использованы при

доказательстве с нулевым разглашением конфиденциальной информации, однако

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

отыскание в связном графе цикла Гамильтона (замкнутого пути, проходящего

через все вершины графа только один раз) и определение изоморфизма графов

(два графа изоморфны, если они отличаются только названиями своих вершин).

Параллельные доказательства с нулевым разглашением конфиденциальной

информации

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

конфиденциальной информации требует, чтобы Антон и Борис последовательно

повторили его шаги n раз. Можно попробовать выполнять действия,

предусмотренные этим протоколом, одновременно:

1. Антон использует имеющуюся у него информацию и n

сгенерированных случайных чисел, чтобы свести труднорешаемую

задачу к n другим труднорешаемым задачам, изоморфным исходной

задаче. Затем Антон решает эти n новых задач.

2. Антон задействует протокол предсказания бита для найденных на

шаге 1 n решений, чтобы впоследствии, если у Бориса возникнет

необходимость ознакомиться с этими решениями, Борис мог бы

достоверно убедиться, что предъявленные Антоном решения

действительно были получены им на шаге 1.

3. Антон показывает n новых труднорешаемых задач Борису.

4. Для каждой из n новых труднорешаемых задач Борис просит

Антона

или (а) - доказать, что она изоморфна исходной труднорешаемой

задаче,

или (б) - предоставить решение этой задачи, которое Антон должен

был найти на шаге 1, и доказать, что оно действительно является

ее решением.

5. Антон выполняет все просьбы Бориса.

На первый взгляд параллельный протокол обладает тем же свойством

нулевого разглашения конфиденциальной информации, что и обычный. Однако

строгого доказательства этого факта еще не найдено. А пока с полной

определенностью можно сказать лишь одно: некоторые интерактивные протоколы

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

параллельно, и от этого они не утрачивают свойство нулевого разглашения

конфиденциальной информации.

Неинтерактивные протоколы доказательства с нулевым разглашением

конфиденциальной информации

Постороннее лицо, не участвующее в выполнении шагов интерактивного

протокола доказательства с нулевым разглашением конфиденциальной

информации, невозможно убедить в том, в чем в ходе реализации протокола

убеждается Борис, а именно - что Антон действительно владеет

конфиденциальной информацией. Чтобы преодолеть этот недостаток, потребуется

применить неинтерактивный протокол, в котором вместо Бориса используется

однонаправленная функция:

1. Антон использует имеющуюся у него информацию и n сгенерированных

случайных чисел, чтобы свести труднорешаемую задачу к n другим

труднорешаемым задачам, изоморфным исходной задаче. Затем Антон решает

эти n новых задач.

2. Антон задействует протокол предсказания бита для найденных на шаге

1 n решений.

3. Антон подает n обязательств, полученных им на шаге 2, на вход

однонаправленной функции.

4. Для каждой i-й труднорешаемой задачи, к которой Антон свел исходную

задачу на шаге 1, он берет i-й бит значения, вычисленного с помощью

однонаправленной функции, и

(а) если этот бит равен 1, то Антон доказывает, что исходная и i-я

задачи изоморфны, или

(б) если этот бит равен 0, то Антон помещает в общедоступную базу

данных решение i-й задачи, вычисленное на шаге 1.

5. Антон передает в общедоступную базу данных все обязательства,

которые были получены им на шаге 2.

6. Борис, Владимир или любое другое заинтересованное лицо могут

проверить правильность выполнения шагов 1-5 Антоном.

Удивительно, но факт: Антон предоставляет в общее пользование

данные, которые позволяют любому убедиться в том, что он владеет некоторым

секретом, и в то же время не содержат никакой информации о сути самого

секрета.

Роль Бориса в этом протоколе исполняет однонаправленная функция. Если

Антон не знает решения труднорешаемой задачи, он все равно может выполнить

действия, предусмотренные или пунктом (а), или пунктом (б) шага 4

протокола, но отнюдь не обоими пунктами сразу. Поэтому, чтобы смошенничать,

Антону придется научиться предсказывать значения однонаправленной функции.

Однако, если функция действительно является однонаправленной, Антон не

сможет ни догадаться, какими будут ее значения, ни повлиять на нее с тем,

чтобы на ее выходе получилась нужная Антону битовая последовательность.

В отличие от интерактивного протокола, здесь требуется большее

количество итераций. Поскольку генерация случайных чисел возложена на

Антона, подбором этих чисел он может попытаться добиться, чтобы на выходе

однонаправленной функции получилась битовая последовательность нужного ему

вида. Ведь даже если Антон не знает решения исходной труднорешаемой задачи,

он всегда в состоянии выполнить требования или пункта (а), или пункта (б)

шага 4 протокола.

Тогда Антон может попытаться догадаться, на какой из этих пунктов

падет выбор, и выполнить шаги 1-3 протокола. А если его догадка неверна, он

повторит все сначала. Именно поэтому в неинтерактивных протоколах необходим

больший запас прочности, чем в интерактивных. Рекомендуется выбирать n=64

или даже n=128.

Доказано, что в общем случае любое математическое доказательство может

быть соответствующим образом преобразовано в доказательство с нулевым

разглашением конфиденциальной информации. А это означает, что теперь

математику вовсе не обязательно публиковать результаты своих научных

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15