ИНФОРМАТИКА

Затем Антон решает эту новую задачу.
2. - Антон задействует протокол предсказания бита для найденного на шаге 1 решения, чтобы впоследствии, если у Бориса возникнет необходимость ознакомиться с этим решением, Борис мог бы достоверно убедиться, что предъявленное Антоном решение действительно было получено им на шаге 1.
3. - Антон показывает новую труднорешаемую задачу Борису.
4. - Борис просит Антона или доказать, что две труднорешаемые задачи (старая и новая) изоморфны, или предоставить решение, которое Антон должен был найти на шаге 1, и доказать, что это действительно решение задачи, к которой Антон свел исходную задачу на том же шаге.
5. - Антон выполняет просьбу Бориса.
6. - Антон и Борис повторяют шаги 1—6 n раз, где n — параметр протокола.
Труднорешаемые задачи, способ сведения одной задачи к другой, а также случайные числа должны по возможности выбираться так, чтобы у Бориса не появилось никакой информации относительно решения исходной задачи даже после многократного выполнения шагов протокола.
Не все труднорешаемые задачи могут быть использованы при доказательстве с нулевым разглашением конфиденциальной информации, однако большинство из них вполне пригодны для таких целей. Примерами могут служить отыскание в связном графе цикла Гамильтона (замкнутого пути, проходящего через все вершины графа только один раз) и определение изоморфизма графов (два графа изоморфны, если они отличаются только названиями своих вершин). - Параллельные доказательства с нулевым разглашением конфиденциальной информации
Обычный протокол доказательства с нулевым разглашением конфиденциальной информации требует, чтобы Антон и Борис последовательно повторили его шаги n раз. Можно попробовать выполнять действия, предусмотренные этим протоколом, одновременно:
1. - Антон использует имеющуюся у него информацию и n сгенерированных случайных чисел, чтобы свести труднорешаемую задачу к n другим труднорешаемым задачам, изоморфным исходной задаче. Затем Антон решает эти n новых задач.