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

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:38:52Z

rollbackEdits.php mass rollback

217.79.179.7 в 03:37, 1 сентября 2022

2022-09-01T03:37:00Z

217.107.105.99: /* Пример: изоморфизм графов. */ убрал точку из конца подзаголовка

2020-11-13T11:31:38Z

‎Пример: изоморфизм графов.: убрал точку из конца подзаголовка

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

2010-06-22T08:58:39Z

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

SVKazakov в 13:15, 2 июня 2010

2010-06-02T13:15:23Z

192.168.0.2 в 14:51, 27 мая 2010

2010-05-27T14:51:13Z

192.168.0.2 в 14:46, 27 мая 2010

2010-05-27T14:46:58Z

192.168.0.2 в 13:11, 27 мая 2010

2010-05-27T13:11:54Z

Argentony в 07:59, 27 мая 2010

2010-05-27T07:59:39Z

Argentony в 07:57, 27 мая 2010

2010-05-27T07:57:24Z

← Предыдущая		Версия 16:38, 4 сентября 2022
Строка 1:		Строка 1:
−	~~{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"~~	+	В криптографии '''Доказательство с нулевым разглашением (информации)''' (Zero-Knowledge Proof) — это интерактивный протокол, позволяющий одной из сторон (проверяющему, Verifier) убедиться в достоверности какого-либо утверждения (обычно математического), не получив при этом никакой другой информации от второй стороны (доказывающего, Prover).
−	\|+
−	~~\|-align="center"~~
−	~~\|'''НЕТ ВОЙНЕ'''~~
−	~~\|-style="font-size: 16px;"~~
−	\|
−	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
−
−	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
−
−	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
−
−	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
−
−	~~''Антивоенный комитет России''~~
−	~~\|-style="font-size: 16px;"~~
−	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
−	~~\|-style="font-size: 16px;"~~
−	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
−	\|}
−
−	В криптографии '''Доказательство с нулевым разглашением (информации)''' (Zero-Knowledge Proof) — это интерактивный протокол, позволяющий одной из сторон (проверяющему, Verifier) убедиться в достоверности какого-либо утверждения (обычно математического), не получив при этом никакой другой информации от второй стороны (доказывающего, Prover).

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

← Предыдущая		Версия 03:37, 1 сентября 2022
Строка 1:		Строка 1:
−	В криптографии '''Доказательство с нулевым разглашением (информации)''' (Zero-Knowledge Proof) — это интерактивный протокол, позволяющий одной из сторон (проверяющему, Verifier) убедиться в достоверности какого-либо утверждения (обычно математического), не получив при этом никакой другой информации от второй стороны (доказывающего, Prover).	+	{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
		+	\|+
		+	\|-align="center"
		+	\|'''НЕТ ВОЙНЕ'''
		+	\|-style="font-size: 16px;"
		+	\|
		+	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
		+
		+	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
		+
		+	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
		+
		+	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
		+
		+	''Антивоенный комитет России''
		+	\|-style="font-size: 16px;"
		+	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
		+	\|-style="font-size: 16px;"
		+	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
		+	\|}
		+
		+	В криптографии '''Доказательство с нулевым разглашением (информации)''' (Zero-Knowledge Proof) — это интерактивный протокол, позволяющий одной из сторон (проверяющему, Verifier) убедиться в достоверности какого-либо утверждения (обычно математического), не получив при этом никакой другой информации от второй стороны (доказывающего, Prover).

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

@@ Строка 12: / Строка 12: @@
 # '''Нулевое разглашение''': Для любой вероятностной полиномиальной интерактивной стратегии <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>. Пегги хочет доказать Виктору, что графы изоморфны, не выдавая при этом ни самой перестановки, ни какой-либо информации о ней.

@@ Строка 14: / Строка 14: @@
 == Пример: изоморфизм графов. ==
-Назовем проверяющую сторону Виктор (Victor), а доказывающую сторону Пегги (Peggy). Им обоим известна пара графов <tex>\langle G_0, G_1 \rangle</tex>. Допустим, эти графы изоморфны и Пегги известена биекция между вершинами этих графов, то есть некоторая перестановка <tex>\pi</tex>, такая что <tex>G_0 = \pi G_1</tex>. Пегги хочет доказать Виктору, что графы изоморфны, не выдавая при этом ни самой перестановки, ни какой-либо информации о ней.
+Назовем проверяющую сторону Виктор (Victor), а доказывающую сторону Пегги (Peggy). Им обоим известна пара графов <tex>\langle G_0, G_1 \rangle</tex>. Допустим, эти графы изоморфны и Пегги известна биекция между вершинами этих графов, то есть некоторая перестановка <tex>\pi</tex>, такая что <tex>G_0 = \pi G_1</tex>. Пегги хочет доказать Виктору, что графы изоморфны, не выдавая при этом ни самой перестановки, ни какой-либо информации о ней.
 Для этого Виктор и Пегги совместно выполняют несколько раундов протокола:

@@ Строка 21: / Строка 21: @@
 * Виктор выбирает случайный бит <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>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>. Более того, Виктору сложно будет доказать кому-либо ещё изоморфизм этих графов.

@@ Строка 9: / Строка 9: @@
 Пусть <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>
-# '''Корректность''': Если ''x'' ∉ ''L'', то для любых <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>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>, такой что для любого ''x'' ∈ ''L'' и соответствующего сертификата ''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'ом без доступа к последнему.
+# '''Нулевое разглашение''': Для любой вероятностной полиномиальной интерактивной стратегии <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'ом без доступа к последнему.
 == Пример: изоморфизм графов. ==

@@ Строка 6: / Строка 6: @@
 # '''Нулевое разглашение''': если утверждение верно, то даже нечестный проверяющий не узнает ничего кроме самого факта, что утверждение верно.
+== Формальное определение ==
 == Пример: изоморфизм графов. ==

@@ Строка 10: / Строка 10: @@
 == Пример: изоморфизм графов. ==
-Назовем проверяющую сторону Петей, а доказывающую сторону Димой. Им обоим известна пара графов <tex>\langle G_0, G_1 \rangle</tex>. Допустим, эти графы изоморфны и Диме известена биекция между вершинами этих графов, то есть некоторая перестановка <tex>\pi</tex>, такая что <tex>G_0 = \pi G_1</tex>. Дима хочет доказать Пете, что графы изоморфны, не выдавая при этом ни самой перестановки, ни какой-либо информации о ней.
+Назовем проверяющую сторону Виктор (Victor), а доказывающую сторону Пегги (Peggy). Им обоим известна пара графов <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>\phi</tex>. Применив ее к <tex>G_0</tex>, она получает некий граф <tex>H = \phi G_0</tex>.
-* Дима передает граф <tex>H</tex> Пете.
+* Пегги передает граф <tex>H</tex> Виктору.
-* Петя выбирает случайный бит <tex>i \leftarrow \{0,1\}</tex>
+* Виктор выбирает случайный бит <tex>i \leftarrow \{0,1\}</tex>
-* Петя просит Диму доказать изоморфизм <tex>G_i</tex> и <tex>H</tex>, то есть предоставить соответствие вершин этих двух графов.
+* Виктор просит Пегги доказать изоморфизм <tex>G_i</tex> и <tex>H</tex>, то есть предоставить соответствие вершин этих двух графов.
-* Если <tex>i = 0</tex>, то Дима отсылает Пете <tex>\phi</tex>, иначе <tex>\phi \cdot \pi</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>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> для проверок изоморфизма. Таким образом без участия Пегги доказать изоморфизм графов, можно лишь доказав, что во всех раундах протокола выбирались действительно случайные биты.

@@ Строка 4: / Строка 4: @@
 # '''Полнота''': если утверждение действительно верно, то доказывающий убедит в этом проверяющего.
 # '''Корректность''': если утверждение неверно, то даже нечестный доказывающий не сможет убедить проверяющего за исключением пренебрежимо малой вероятности.
-# '''Нулевое разглашение''': если утверждение верно, то любой даже нечестный проверяющий не узнает ничего кроме самого факта, что утверждение верно.
+# '''Нулевое разглашение''': если утверждение верно, то даже нечестный проверяющий не узнает ничего кроме самого факта, что утверждение верно.