6
правок
Изменения
Нет описания правки
В криптографии '''Доказательство с нулевым разглашением (информации)''' (Zero-knowledge proofKnowledge Proof) — это интерактивный протокол, позволяющий одной из сторон (проверяющему, verifierVerifier) убедиться в достоверности какого-либо утверждения (обычно математического), не получив при этом никакой другой информации от второй стороны (доказывающего, proverProver).
Доказательство с нулевым разглашением должно обладать тремя свойствами:
# '''Корректность''': если утверждение неверно, то даже нечестный доказывающий не сможет убедить проверяющего за исключением пренебрежимо малой вероятности.
# '''Нулевое разглашение''': если утверждение верно, то любой даже нечестный проверяющий не узнает ничего кроме самого факта, что утверждение верно.
== Пример: изоморфизм графов. ==
Назовем проверяющую сторону Петей, а доказывающую сторону Димой. Им обоим известна пара графов <tex>\langle G_0, G_1 \rangle</tex>. Допустим, Диме известена биекция между вершинами этих графов, то есть некоторая перестановка <tex>\pi</tex>, такая что <tex>G_0 = \pi G_1</tex>. Дима хочет доказать Пете, что графы изоморфны, не выдавая при этом ни самой перестановки, ни какой-либо информации о ней.
Для этого Петя и Дима совместно выполняют несколько раундов протокола:
* Вначале Дима создает случайную перестановку <tex>\phi</tex>. Применив ее к <tex>G_0</tex>, он получает некий граф <tex>H = \phi G_0</tex>.
* Дима передает граф <tex>H</tex> Пете.
* Петя выбирает случайный бит <tex>i \leftarrow \{0,1\}</tex>
* Петя просит Диму доказать изоморфизм <tex>G_i</tex> и <tex>H</tex>, то есть предоставить соответствие вершин этих двух графов.
* Если <tex>i = 0</tex>, то Дима отсылает Пете <tex>\phi</tex>, иначе <tex>\phi \cdot \pi</tex>
В каждом раунде Петя выбирает новый случайный бит, который неизвестен Диме. Поэтому чтобы ответить на оба вопроса, Диме нужно чтобы <tex>H</tex> был в самом деле изоморфен <tex>G_i</tex>. Это означает, что после достаточного числа раундов, Петя может быть уверен в том, что графы <tex>G_0</tex> и <tex>G_1</tex> изоморфны. С другой стороны, Дима не раскрывает никакой информации о перестановке <tex>\pi</tex>. Более того, Пете сложно будет доказать кому-либо ещё изоморфизм этих графов.
Предположим, что у Димы нет перестановки <tex>\pi</tex> и он хочет обмануть Петю. Тогда граф <tex>H</tex>, который он отсылает Пете, будет не изоморфен хотя бы одному из пары графов <tex>\langle G_0, G_1 \rangle</tex>. Поэтому вероятность того, что он сможет обмануть Петю в одном раунде не более <tex>\frac{1}{2}</tex>. Вероятность того, что Дима сможет обманывать Петю на протяжении <tex>n</tex> раундов не превосходит <tex>2^{-n}</tex>.
Предположим, что Петя не узнал перестановку <tex>\pi</tex>, но хочет доказать Васе, что Дима ее знает. Если Петя, например, заснял на видео все раунды протокола, Вася едва ли ему поверит. Вася может предположить, что Петя и Дима в сговоре и в каждом раунде Петя заранее сообщал Диме свой выбор случайного бита, чтобы Дима мог передавать ему <tex>H</tex> для проверок изоморфизма. Таким образом без участия Димы доказать изоморфизм графов, можно лишь доказав, что во всех раундах протокола выбирались действительно случайные биты.
