Доказательство с нулевым разглашением

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

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

1. Полнота: если утверждение действительно верно, то доказывающий убедит в этом проверяющего.
2. Корректность: если утверждение неверно, то даже нечестный доказывающий не сможет убедить проверяющего за исключением пренебрежимо малой вероятности.
3. Нулевое разглашение: если утверждение верно, то любой даже нечестный проверяющий не узнает ничего кроме самого факта, что утверждение верно.

Доказательства с нулевым разглашением нашли применение в криптографических протоколах чтобы убедиться в том, что другая сторона следует протоколу честно. На практике доказательства с нулевым разглашением также используются в протоколах конфиденциального вычисления.

Пример

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

Для этого Петя и Дима совместно выполняют несколько раундов протокола:

• Вначале Дима создает граф H, изоморфный G. Преобразовывание гамильтонова цикла между изоморфными графами - тривиальная задача, поэтому если Диме известен гамильтонов цикл в G, то он также знает гамильтонов цикл в H.
• Дима передает граф H Пете.
• Петя выбирает случайный бит b ← {0,1}
  • Если b=0, то Петя просит Диму доказать изоморфизм G u H, то есть предоставить соответствие вершин этих двух графов. Петя может проверить, действительно ли G u H изоморфны.
  • Если b=1, то Петя просит Диму показать гамильтонов цикл в H. Изоморфизм графов - NP-полная задача, поэтому будем здесь считать, что невозможно из гамильтонова цикла в H вычислить гамильтонов цикл в G.

В каждом раунде Петя выбирает новый случайный бит, который неизвестен Диме, поэтому чтобы Дима мог ответить на оба вопроса, нужно чтобы H был в самом деле изоморфен G и Дима должен знать гамильтонов цикл в H (а значит также и в G). Поэтому после достаточного числа раундов, Петя может быть уверен в том, что у Димы действительно есть гамильтонов цикл в G. С другой стороны, Дима не раскрывает никакой информации о гамильтоновом цикле в G. Более того, Пете сложно будет доказать кому-либо ещё, что он сам или Дима знает гамильтовов цикл в G.

Предположим, что у Димы нет гамильтонова цикла в G и он хочет обмануть Петю. Тогда Диме необходим неизоморфный G граф G' , в котором он всё-таки знает гамильтонов цикл. В каждом раунде он может передавать Пете либо H' - изоморфный G' , либо H - изоморфный G. Если Петя попросит доказать изоморфизм и был передан H, то обман не вскроется. Аналогично, если он просит показать гамильтонов цикл и был передан H' . В таком случае вероятность того, что Дима все-таки обманет Петю после n раундов, равна 1/2ⁿ, что может меньше любой заранее заданной величы при достаточном числе раундов.

Предположим, что Петя не узнал гамильтонов цикл, но хочет доказать Васе, что Дима его знает. Если Петя, например, заснял на видео все раунды протокола, Вася едва ли ему поверит. Вася может предположить, что Петя и Дима в сговоре и в каждом раунде Петя заранее сообщал Диме свой выбор случайного бита, чтобы Дима мог передавать ему H для проверок изоморфизма и H' для проверок гамильтонова цикла. Таким образом без участия Димы доказать, что он знает гамильтонов цикл, можно лишь доказав, что во всех раундах протокола выбирались действительно случайные биты.