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

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


Предположим, что Алиса знает доказательство некоторой теоремы и желает убедить Боба в том, что теорема верна. Конечно, Алиса может просто передать доказательство Бобу на проверку. Но тогда впоследствии Боб сможет сам, без помощи Алисы, доказывать третьим лицам эту теорему. А может ли Алиса убедить Боба так, чтобы он не получил при этом никакой информации, которая помогла бы ему восстановить доказательство теоремы? Этим двум, казалось бы взаимно исключающим требованиям, удовлетворяют протоколы доказательства с нулевым разглашением. Последнее понятие было введено Гольдвассер, Микали и Ракоффом в 1985 г. [].

Рассматривается следующая модель протокола. В распоряжении Алисы и Боба имеются вероятностные машины Тьюринга P

и V

соответственно. Вычислительные ресурсы, которые может использовать Алиса, неограничены, в то время как машина V

работает за полиномиальное время. Машины P и V имеют общую коммуникационную ленту для обмена сообщениями. После записи сообщения на коммуникационную ленту машина переходит в состояние ожидания и выходит из него, как только на ленту будет записано ответное сообщение. Машины P и V имеют также общую входную ленту, на которую записано входное слово . Утверждение, которое доказывает Алиса, суть ``'', где - некоторый фиксированный (известный и Алисе, и Бобу) язык. Чтобы избежать тривиальности, язык должен быть трудным (например, NP-полным), иначе Боб сможет самостоятельно проверить, что . По существу, протокол доказательства состоит в том, что Боб, используя случайность, выбирает некоторые вопросы, задает их Алисе и проверяет правильность ответов. Выполнение протокола завершается, когда машина V останавливается, при этом она выдает 1, если доказательство принято, и 0 - в противном случае.

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




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


[an error occurred while processing this directive]