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

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

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.

Доказано, что в общем случае любое математическое доказательство может быть соответствующим образом преобразовано в доказательство с пулевым разглашением конфиденциальной информации. А это означает, что теперь математику вовсе не обязательно публиковать результаты своих научных исследований. Он может доказать своим коллегам, что нашел решение каком-то математической проблемы, не раскрывая перед ними сути найденного решения.

Содержание раздела