Перейти к содержанию

Протокол суммирования-проверки

Статья из Авикипедии. Энциклопедии

Протокол суммирующей проверки

История Протокол суммирующей проверки был создан Карстеном Лундом, Лэнсом Фортноу, Говардом Карлоффом и Ноамом Нисаном и формализован в 1990 году. Протокол суммирующей проверки позволяет доказывающей стороне убедить проверяющую сторону, что сумма многомерного полинома равна известному значению.

H := ∑_{b₁ ∈ {0,1}} ∑_{b₂ ∈ {0,1}} ⋯ ∑_{b_v ∈ {0,1}} g(b₁, …, b_v).

Без участия доказывающей стороны проверяющей стороне пришлось бы выполнить 2ⁿ вычислений функции g для проверки утверждения, что требует очень большого времени выполнения. С использованием протокола суммирующей проверки время выполнения проверяющей стороны составляет O(v + [стоимость вычисления g для единственного входного значения в Fᵛ]).

См. также

  • Криптографический протокол
  • Системы интерактивного доказательства
  • Доказательство с нулевым разглашением

Внешние ссылки

Ссылки[править | править код]