МЕНЮ

Каталог

ЗАДАЧА О КУБИКЕ РУБИКА Протокол RC
Протокол интерактивного доказательства Протокол доказательства с нулевым разглашением

 

Постановка задачи

Пусть $ P$ знает как решить Кубик Рубика из какой-то позиции (назовем ее исходной) и хочет доказать это $ V$, при этом $ P$ не хочет чтобы $ V$ также научился складывать кубик из данной позиции. 
Описание протокола

1) $ P$ выбирает произвольную другую позицию кубика и показывает ее $ V$.

2) $ V$ просит сделать одно из следующих действий:

(a) показать как из выбранной позиция собрать исходную либо

(b) показать как решить выбранную позицию.

3) $ P$ выполняет просьбу $ V$.

4) $ P$ и $ V$ повторяют шаги 1) - 3) $ n$ раз. 

Очевидно $ P$ всегда сможет доказать $ V$ умение решать исходную позицию, если она действительно таким умением обладает. В противном же случае она не всегда сможет выполнить пункт 3). Так же любое количество итераций никаким образом не поможет $ V$выяснить как решается исходная позиция.