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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 9 промежуточных версий 5 участников)
Строка 4: Строка 4:
 
# '''Полнота''': если утверждение действительно верно, то доказывающий убедит в этом проверяющего.
 
# '''Полнота''': если утверждение действительно верно, то доказывающий убедит в этом проверяющего.
 
# '''Корректность''': если утверждение неверно, то даже нечестный доказывающий не сможет убедить проверяющего за исключением пренебрежимо малой вероятности.
 
# '''Корректность''': если утверждение неверно, то даже нечестный доказывающий не сможет убедить проверяющего за исключением пренебрежимо малой вероятности.
# '''Нулевое разглашение''': если утверждение верно, то любой даже нечестный проверяющий не узнает ничего кроме самого факта, что утверждение верно.
+
# '''Нулевое разглашение''': если утверждение верно, то даже нечестный проверяющий не узнает ничего кроме самого факта, что утверждение верно.
  
 +
== Формальное определение ==
 +
Пусть <tex>L</tex> ∈ '''[[NP]]''', и <tex>M</tex> — машина Тьюринга для проверки сертификата, то есть <tex>x \in L \Leftrightarrow \exists y \in \{0,1\}^{p(|x|)} : M(x, y) = 1</tex>. Пара <tex>\langle P, V \rangle</tex> интерактивных вероятностных алгоритмов называется доказательством с нулевым разглашением для <tex>L</tex>, если выполнены следующие три условия:
 +
# '''Полнота''': Для любого <tex>x \in L</tex> и сертификата <tex>y</tex> выполнено <tex>P \left( \text{out}_V \left\langle P(x,y), V(x) \right\rangle = 1 \right) \ge 2/3</tex>
 +
# '''Корректность''': Если <tex>x \not \in L</tex>, то для любых <tex>P^*, y</tex> выполнено <tex> P \left( \text{out}_V \left\langle P^*(x,y), V(x) \right\rangle = 1 \right) \le 1/3</tex>
 +
# '''Нулевое разглашение''': Для любой вероятностной полиномиальной интерактивной стратегии <tex>V^*</tex> существует вероятностный полиномиальный алгоритм <tex>S^*</tex>, такой что для любого <tex>x \not \in L</tex> и соответствующего сертификата ''y'' выполнено <tex>\text{out}_{V^*} \left \langle P(x,y), V^*(x) \right \rangle\equiv S^*(x)</tex>. Такой алгоритм <tex>S^*</tex> называется симулятором для <tex>V^*</tex>, он симулирует результат взаимодействия <tex>V^*</tex> c proover'ом без доступа к последнему.
  
 +
== Пример: изоморфизм графов ==
  
== Пример: изоморфизм графов. ==
+
Назовем проверяющую сторону Виктор (Victor), а доказывающую сторону Пегги (Peggy). Им обоим известна пара графов <tex>\langle G_0, G_1 \rangle</tex>. Допустим, эти графы изоморфны и Пегги известна биекция между вершинами этих графов, то есть некоторая перестановка <tex>\pi</tex>, такая что <tex>G_0 = \pi G_1</tex>. Пегги хочет доказать Виктору, что графы изоморфны, не выдавая при этом ни самой перестановки, ни какой-либо информации о ней.
  
Назовем проверяющую сторону Петей, а доказывающую сторону Димой. Им обоим известна пара графов <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>\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>, который он отсылает Пете, будет не изоморфен хотя бы одному из пары графов <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> для проверок изоморфизма. Таким образом без участия Пегги доказать изоморфизм графов, можно лишь доказав, что во всех раундах протокола выбирались действительно случайные биты.
 
 
Предположим, что Петя не узнал перестановку <tex>\pi</tex>, но хочет доказать Васе, что Дима ее знает. Если Петя, например, заснял на видео все раунды протокола, Вася едва ли ему поверит. Вася может предположить, что Петя и Дима в сговоре и в каждом раунде Петя заранее сообщал Диме свой выбор случайного бита, чтобы Дима мог передавать ему <tex>H</tex> для проверок изоморфизма. Таким образом без участия Димы доказать изоморфизм графов, можно лишь доказав, что во всех раундах протокола выбирались действительно случайные биты.
 

Текущая версия на 19:38, 4 сентября 2022

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

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

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

Формальное определение

Пусть [math]L[/math]NP, и [math]M[/math] — машина Тьюринга для проверки сертификата, то есть [math]x \in L \Leftrightarrow \exists y \in \{0,1\}^{p(|x|)} : M(x, y) = 1[/math]. Пара [math]\langle P, V \rangle[/math] интерактивных вероятностных алгоритмов называется доказательством с нулевым разглашением для [math]L[/math], если выполнены следующие три условия:

  1. Полнота: Для любого [math]x \in L[/math] и сертификата [math]y[/math] выполнено [math]P \left( \text{out}_V \left\langle P(x,y), V(x) \right\rangle = 1 \right) \ge 2/3[/math]
  2. Корректность: Если [math]x \not \in L[/math], то для любых [math]P^*, y[/math] выполнено [math] P \left( \text{out}_V \left\langle P^*(x,y), V(x) \right\rangle = 1 \right) \le 1/3[/math]
  3. Нулевое разглашение: Для любой вероятностной полиномиальной интерактивной стратегии [math]V^*[/math] существует вероятностный полиномиальный алгоритм [math]S^*[/math], такой что для любого [math]x \not \in L[/math] и соответствующего сертификата y выполнено [math]\text{out}_{V^*} \left \langle P(x,y), V^*(x) \right \rangle\equiv S^*(x)[/math]. Такой алгоритм [math]S^*[/math] называется симулятором для [math]V^*[/math], он симулирует результат взаимодействия [math]V^*[/math] c proover'ом без доступа к последнему.

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

Назовем проверяющую сторону Виктор (Victor), а доказывающую сторону Пегги (Peggy). Им обоим известна пара графов [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] для проверок изоморфизма. Таким образом без участия Пегги доказать изоморфизм графов, можно лишь доказав, что во всех раундах протокола выбирались действительно случайные биты.