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

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

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

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

Пример: изоморфизм графов.

Назовем проверяющую сторону Петей, а доказывающую сторону Димой. Им обоим известна пара графов [math]\langle G_0, G_1 \rangle[/math]. Допустим, эти графы изоморфны и Диме известена биекция между вершинами этих графов, то есть некоторая перестановка [math]\pi[/math], такая что [math]G_0 = \pi G_1[/math]. Дима хочет доказать Пете, что графы изоморфны, не выдавая при этом ни самой перестановки, ни какой-либо информации о ней.

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

• Вначале Дима создает случайную перестановку [math]\phi[/math]. Применив ее к [math]G_0[/math], он получает некий граф [math]H = \phi G_0[/math].
• Дима передает граф [math]H[/math] Пете.
• Петя выбирает случайный бит [math]i \leftarrow \{0,1\}[/math]
• Петя просит Диму доказать изоморфизм [math]G_i[/math] и [math]H[/math], то есть предоставить соответствие вершин этих двух графов.
• Если [math]i = 0[/math], то Дима отсылает Пете [math]\phi[/math], иначе [math]\phi \cdot \pi[/math]

В каждом раунде Петя выбирает новый случайный бит, который неизвестен Диме. Поэтому чтобы ответить на оба вопроса, Диме нужно чтобы [math]H[/math] был в самом деле изоморфен [math]G_i[/math]. Это означает, что после достаточного числа раундов, Петя может быть уверен в том, что графы [math]G_0[/math] и [math]G_1[/math] изоморфны. С другой стороны, Дима не раскрывает никакой информации о перестановке [math]\pi[/math]. Более того, Пете сложно будет доказать кому-либо ещё изоморфизм этих графов.

Предположим, что у Димы нет перестановки [math]\pi[/math] и он хочет обмануть Петю. Тогда граф [math]H[/math], который он отсылает Пете, будет не изоморфен хотя бы одному из пары графов [math]\langle G_0, G_1 \rangle[/math]. Поэтому вероятность того, что он сможет обмануть Петю в одном раунде не более [math]\frac{1}{2}[/math]. Вероятность того, что Дима сможет обманывать Петю на протяжении [math]n[/math] раундов не превосходит [math]2^{-n}[/math].

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