211
правок
Изменения
м
Нет описания правки
{{В разработке}}
{{Определение
|definition=
:'''Шаг m'''
: <tex>P(A_{m-1}(r_m) \ne \tilde{A}_{m-1}(r_m)) \ge 1 - \frac d p</tex>. Значит с такой вероятностью ''Verifier'' получит <tex>\tilde{A}_m</tex> вместо <tex>A_m</tex>. Но так как на шаге <tex>m</tex> ''Verifier'' вычисляет <tex>A_m</tex> и сравнивает его с полученным от ''Prover'' 'а, то в этом случае ''Verifier'' вернет ''false''.
:
:Заметим, что если на каком-то шаге <tex>P(A_{i-1}(r_i) = \tilde{A}_{i-1}(r_i))</tex>, то начиная со следующего шага ''Prover'' может посылать истинные значения <tex>A_i</tex> и в итоге ''Verifier'' вернёт '''true'''.
:Из описанного процесса видно, что с вероятностью большей либо равной <tex>(1 - \frac d p) ^ m</tex> мы дойдем до последнего шага и будем имееть <tex>\tilde{A}_n</tex> вместо <tex>A_n</tex>. Так как на шаге <tex>m</tex> ''Verifier'' вычисляет <tex>A_n</tex> и проверяет значение, то ''Verifier'' вернет ''false''.
:Оценим вероятность возврата ''Verifier'' 'ом ответа '''false'''.
:<tex>(1 - \frac d p) ^ m \ge (1 - \frac d {3dm})^m = (1 - \frac 1 {3m})^m = 1 - \frac 1 3 + \frac{m(m - 1)}{2 (3m)^2} - \frac{m(m-1)(m-2)}{6 (3m)^3} + \ldots \ge \frac 2 3</tex>.
Таким образом, построенный нами ''Verifier'' корректен, а значит лемма доказана.
}}
