Надежность (интерактивное доказательство)

редактировать

Надежность - это свойство интерактивных систем доказательства, которое требует, чтобы ни один доказывающий не мог проверяющий принимает за неправильное утверждение $y ∉ L {\ displaystyle y \ not \ in L}$ $y \ not \ in L$ за исключением некоторой небольшой вероятности. Верхняя граница этой вероятности называется ошибкой надежности системы доказательств.

Более формально, для каждого доказывающего $(P ~) {\ displaystyle ({\ tilde {\ mathcal {P}}})}$ ${\ displaystyle ({\ tilde {\ mathcal {P}}})}$ и каждого $y ∉ L {\ displaystyle y \ not \ in L}$ $y \ not \ in L$ :

Pr [(⊥, (accept)) ← (P ~) (y) ↔ (V) (y)] < ϵ. {\displaystyle \Pr[(\perp,({\text{accept}}))\gets ({\tilde {\mathcal {P}}})(y)\leftrightarrow ({\mathcal {V}})(y)]<\epsilon.}

{\ displaystyle \ Pr [(\ perp, ({\ text {accept}})) \ получает ({\ тильда {\ mathcal { P}}}) (y) \ leftrightarrow ({\ mathcal {V}}) (y)] <\ epsilon.}

для некоторых $ϵ ≪ 1 {\ Displaystyle \ epsilon \ ll 1}$ ${\ displaystyle \ epsilon \ ll 1}$ . Пока ошибка корректности ограничена полиномиальной долей потенциального времени работы верификатора (т.е. $ϵ ≤ 1 / poly (| y |) {\ displaystyle \ epsilon \ leq 1 / \ mathrm {poly} ( | y |)}$ ${\ displaystyle \ epsilon \ leq 1 / \ mathrm {poly} (| y |)}$ ), всегда можно усилить корректность, пока ошибка корректности не станет незначительной функцией относительно времени работы верификатора. Это достигается путем повторения доказательства и принятия, только если все доказательства подтвердятся. После $ℓ {\ displaystyle \ ell}$ $\ ell$ повторов ошибка правильности $ϵ {\ displaystyle \ epsilon}$ $\ epsilon$ будет уменьшена до $ϵ ℓ {\ displaystyle \ epsilon ^ {\ ell}}$ ${\ displaystyle \ epsilon ^ {\ ell}}$ .

См. также

Ссылки

^Goldreich, Oded (2002), Zero -Знание через двадцать лет после его изобретения, ECCC TR02-063.