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

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


Определение 4. Интерактивным доказательством для языка

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

1. (Полнота). Для всех

2. (Корректность). Для любой машины Тьюринга , для любого полинома и для всех достаточно большой длины

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

Определение 5. Интерактивный протокол доказательства для языка называется доказательством с абсолютно нулевым разглашением, если, кроме условий 1 и 2, выполнено еще и следующее условие.

3. (Свойство нулевого разглашения). Для любой полиномиальной вероятностной машины Тьюринга

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

Машина

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

, когда на входе она получает слово .

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




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


[an error occurred while processing this directive]