Теория и практика защиты программ


Интерактивные системы доказательств


Пусть А и В

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

Интерактивным доказательством для языка L называется пара интерактивных машин Тьюринга (P,V) такая, что выполняются следующие два условия.

1.     (Полнота). Для всех хÎL вероятность Prob{[P(x),V(x)]=1}=1.

2.     (Корректность). Для любой машины Тьюринга Р*, для любого полинома р и для всех хÎL достаточно большой длины Prob{[P*(x),V(x)]=1}<l/p(|x|).

Формальные определения интерактивных систем доказательств и интерактивных систем доказательств с нулевым разглашением даны в приложении.




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