Прочность (интерактивное доказательство) - Soundness (interactive proof)

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

Более формально, для каждого испытателя и каждого : ${\ Displaystyle ({\ тильда {\ mathcal {P}}})}$${\ displaystyle y \ not \ in L}$

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

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

Смотрите также

• Интерактивная система доказательств
• Доказательство знаний
• Доказательство с нулевым разглашением

Ссылки

Эта статья о криптографии незавершена . Вы можете помочь Википедии, расширив ее . v т е