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

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 21: Строка 21:
 
* Виктор выбирает случайный бит <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>. Более того, Виктору сложно будет доказать кому-либо ещё изоморфизм этих графов.

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)