Доказательство с нулевым разглашением
В криптографии Доказательство с нулевым разглашением (информации) (англ. Zero-knowledge proof) — это интерактивный протокол, позволяющий одной из сторон (проверяющему, verifier) убедиться в достоверности какого-либо утверждения (обычно математического), не получив при этом никакой другой информации от второй стороны (доказывающего, prover).
Доказательство с нулевым разглашением должно обладать тремя свойствами:
- Полнота: если утверждение действительно верно, то доказывающий убедит в этом проверяющего.
- Корректность: если утверждение неверно, то даже нечестный доказывающий не сможет убедить проверяющего за исключением пренебрежимо малой вероятности.
- Нулевое разглашение: если утверждение верно, то любой даже нечестный проверяющий не узнает ничего кроме самого факта, что утверждение верно.
Доказательства с нулевым разглашением нашли применение в криптографических протоколах чтобы убедиться в том, что другая сторона следует протоколу честно. На практике доказательства с нулевым разглашением также используются в протоколах конфиденциального вычисления.
Пример
Назовем проверяющую сторону Петей, а доказывающую сторону Димой (в англоязычной литературе обычно используются пары Alice и Bob). Допустим Диме известен Гамильтонов цикл в большом графе G. Пете известен граф G, но он не знает гамильтонова цикла в нем. Дима хочет доказать Пете, что он знает гамильтонов цикл, не выдавая при этом ни самого цикла, ни какой-либо информации о нем (возможно Петя хочет купить этот гамильтонов цикл у Димы, но перед этим удостовериться, что он у Димы действительно есть).
Для этого Петя и Дима совместно выполняют несколько раундов протокола:
- Вначала Дима создает граф H, изоморфный G. Преобразовывание гамильтонов цикла между изоморфными графами - тривиальная задача, поэтому если Диме известен гамильтонов цикл в G, то он также знает гамильтонов цикл в H.
...