Системы защиты компьютера


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


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

4. Борис просит Антона или доказать, что две трудно решаемые задачи (старая и новая) изоморфны, или предоставить решение, которое Антон должен был найти на шаге 1, и доказать, что это действительно решение задачи, к которой Антон свел исходную задачу на том же шаге.

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

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

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

Не все трудно решаемые задачи могут быть использованы при доказательстве с нулевым разглашением конфиденциальной информации, однако большинство из них вполне пригодны для таких целей. Примерами могут служить отыскание в связном графе цикла Гамильтона (замкнутого пути, проходящего через все вершины графа только один раз) и определение изоморфизма графов (два графа изоморфны, если они отличаются только названиями своих вершин).




Начало  Назад  Вперед



Книжный магазин