Протокол суммирования-проверки
Протокол суммирующей проверки
История Протокол суммирующей проверки был создан Карстеном Лундом, Лэнсом Фортноу, Говардом Карлоффом и Ноамом Нисаном и формализован в 1990 году. Протокол суммирующей проверки позволяет доказывающей стороне убедить проверяющую сторону, что сумма многомерного полинома равна известному значению.
H := ∑_{b₁ ∈ {0,1}} ∑_{b₂ ∈ {0,1}} ⋯ ∑_{b_v ∈ {0,1}} g(b₁, …, b_v).
Без участия доказывающей стороны проверяющей стороне пришлось бы выполнить 2ⁿ вычислений функции g для проверки утверждения, что требует очень большого времени выполнения. С использованием протокола суммирующей проверки время выполнения проверяющей стороны составляет O(v + [стоимость вычисления g для единственного входного значения в Fᵛ]).
См. также
- Криптографический протокол
- Системы интерактивного доказательства
- Доказательство с нулевым разглашением
Внешние ссылки
Ссылки[править | править код]
- https://dl.acm.org/doi/10.1145/146585.146605
- https://cryptologie.net/posts/the-intuition-behind-the-sum-check-protocol-in-5-minutes/
- https://ieeexplore.ieee.org/document/89518/
- https://zkproof.org/2020/03/16/sum-checkprotocol/
- https://people.cs.georgetown.edu/jthaler/ProofsArgsAndZK.pdf
- https://eprint.iacr.org/2024/1046
- https://ocw.mit.edu/courses/6-5630-advanced-topics-in-cryptography-fall-2023/pages/lecture-1-interactive-proofs-and-the-sum-check-protocol/