ИНФОРМАТИКА

4. - Для каждой i-й труднорешаемой задачи, к которой Антон свел исходную задачу на шаге 1, он берет i-й бит значения, вычисленного с помощью однонаправленной функции, и (а) если этот бит равен 1, то Антон доказывает, что исходная и i-я задачи изоморфны, или (б) если этот бит равен 0, то Антон помещает в общедоступную базу данных решение i-й задачи, вычисленное на шаге 1.
5. - Антон передает в общедоступную базу данных все обязательства, которые были получены им на шаге 2.
6. - Борис, Владимир или любое другое заинтересованное лицо могут проверить правильность выполнения Антоном шагов 1—5.
Удивительно, но факт: Антон предоставляет в общее пользование данные, которые позволяют любому убедиться в том, что он владеет некоторым секретом, и которые одновременно с этим не содержат никакой информации о сути самого секрета.
Роль Бориса в этом протоколе исполняет однонаправленная функция. Если Антон не знает решения труднорешаемой задачи, он все равно может выполнить действия, предусмотренные или пунктом (а), или пунктом (б) шага 4 протокола, но отнюдь не обоими пунктами сразу. Поэтому, чтобы смошенничать, Антону придется научиться предсказывать значения однонаправленной функции. Однако если функция действительно является однонаправленной, Антон не сможет ни догадаться, какими будут ее значения, ни повлиять на нее с тем, чтобы на ее выходе получилась нужная Антону битовая последовательность.
В отличие от интерактивного протокола, здесь требуется большее количество итераций. Поскольку генерация случайных чисел возложена на Антона, подбором этих чисел он может попытаться добиться, чтобы на выходе однонаправленной функции получилась битовая последовательность нужного ему вида. Ведь даже если Антон не знает решения исходной труднорешаемой задачи, он всегда в состоянии выполнить требования или пункта (а), или пункта (б) шага 4 протокола. Тогда Антон может попытается догадаться, на какой из этих пунктов падет выбор, и выполнить шаги 1—3 протокола. А если его догадка неверна, он повторит все сначала.