Редактирование: Доказательства с нулевым разглашением
Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 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'ом без доступа к последнему. | # '''Нулевое разглашение''': Для любой вероятностной полиномиальной интерактивной стратегии <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>. Пегги хочет доказать Виктору, что графы изоморфны, не выдавая при этом ни самой перестановки, ни какой-либо информации о ней. | Назовем проверяющую сторону Виктор (Victor), а доказывающую сторону Пегги (Peggy). Им обоим известна пара графов <tex>\langle G_0, G_1 \rangle</tex>. Допустим, эти графы изоморфны и Пегги известна биекция между вершинами этих графов, то есть некоторая перестановка <tex>\pi</tex>, такая что <tex>G_0 = \pi G_1</tex>. Пегги хочет доказать Виктору, что графы изоморфны, не выдавая при этом ни самой перестановки, ни какой-либо информации о ней. |