Введение в криптографию
[an error occurred while processing this directive]

Доказательства с нулевым разглашением - часть 4


Доказательство свойства нулевого разглашения значительно сложнее. Поэтому мы воспроизводим только основную идею. Прежде всего, заметим, что основная задача машины - получить максимально возможную информацию об изоморфизме между и . Естественно предположить, что она, в отличие от V, будет выдавать в качестве выходного слова не один бит, а всю полученную в результате выполнения протокола информацию, включая содержимое своей случайной ленты, графы и перестановки, полученные соответственно на шагах 1 и 3 протокола IG. Моделирующая машина должна уметь строить такие же случайные строки, графы и перестановки, не зная при этом изоморфизм ! Поэтому пытается угадать тот бит , который будет запросом машины на шаге 2. Для этого выбирает случайный бит , случайную перестановку и вычисляет . Далее запоминает состояние машины (включая содержимое случайной ленты) и вызывает ее как подпрограмму, подавая ей на вход граф . Ответом машины будет некоторый бит . Если , то моделирование в данном цикле завершено успешно, поскольку может продемонстрировать требуемый изоморфизм. Если же , то

восстанавливает ранее сохраненное состояние машины и повторяет попытку.

Если в определении свойства нулевого разглашения заменить равенство случайных величин и

требованием, чтобы их распределения вероятностей ``почти не отличались'', то получится другая разновидность доказательств - доказательства со статистически нулевым разглашением.

Еще один тип - доказательства с вычислительно нулевым разглашением. В этом случае требуется, чтобы моделирующая машина создавала распределение вероятностей, которое неотличимо от никаким полиномиальным вероятностным алгоритмом (неотличимость здесь определяется аналогично тому, как это делалось в определении псевдослучайного генератора).

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

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




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


[an error occurred while processing this directive]