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

В криптографии, доказательство с нулевым разглашением или ноль - протокол знаний - это метод, с помощью которого одна сторона (доказывающая сторона) может доказать другую сторону (проверяющей), что она знает значение x, не передавая никакой информации, кроме того, что они знают значение х. Суть доказательств с нулевым разглашением в том, что легко доказать, что кто-то обладает знанием информации, просто раскрывая ее; задача состоит в том, чтобы доказать такое владение без раскрытия самой информации или какой-либо дополнительной информации.

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

Интерактивное доказательство с нулевым разглашением требует взаимодействия между человеком (или компьютерной системой), подтверждающим свои знания, и человеком, подтверждающим доказательство.

Протокол, реализующий доказательства с нулевым разглашением, обязательно должен потребовать интерактивного ввода от верификатора. Этот интерактивный ввод обычно имеет форму одного или нескольких агентов, проверяющий проверяющий, когда утверждение истинно, то есть проверяющий обладает знаниями. Если бы это было не так, верификатор мог бы выполнить выполнение протокола и выполнить его, чтобы убедить кого-то еще в том, что он владеет секретной информацией. Принятие новой стороны либо оправдано, поскольку проигрыватель действительно владеет информацией (что подразумевает, что информация утекла в протоколе, следовательно, не доказана с нулевым разглашением), либо принять ложным, т. Е. Было принято от кого-то, кто не действительно владею информацией.

Существуют некоторые формы неинтерактивных доказательств с нулевым разглашением, но достоверность доказательств зависит от вычислительных допущений (обычно допущений идеальной криптографической хеш-функции ).

Содержание

• 1 Примеры
  • 1.1 Пещера Али-Бабы
  • 1.2 Два шара и дальтоник
  • 1.3 Где Уолли?
• 2 Определение
• 3 Практические примеры
  • 3.1 Дискретный журнал заданного значения
    • 3.1.1 Краткое описание
  • 3.2 Гамильтонов цикл для большого графа
    • 3.2.1 Полнота
    • 3.2.2 С нулевым разглашением
    • 3.2.3 Надежность
• 4 Варианты нулевого знания
• 5 Типы нулевого знания
• 6 Приложения
  • 6.1 Системы аутентификации
  • 6.2 Этическое поведение
  • 6.3 Ядерное разоружение
  • 6.4 Блокчейны
• 7 История
• 8 См. Также
• 9 Ссылки

Похожие примеры

Пегги случайным образом выбирает путь A или B, в то, как Виктор ждет снаружи Виктор выбирает путь выхода Пегги надежно появляется на выходе Виктор имена

Пещера Али-Бабы

Существует известная история, представляющая фундаментальные идеи с нулевым разглашением, впервые опубликованная Жан-Жаком Кискватером и другими в их статье «Как сделать Объяснять вам протоколы с нулевым разглашением r» » Обычной практикой является обозначение двух сторон в доказательстве с нулевым разглашением как Пегги (доказывающий утверждение) и Виктор (проверяющий утверждение).

В истории Пегги раскрыла Пещера Пегги

Он и маркируют левый и правый пути от входов A и B. Сначала Виктор ждет снаружи пещеры, будучи очень закрытым человеком ом, не раскрывает свое знание (секретное слово факт). Пегги выбирает путь A или B; Виктору н е разрешается видеть, какой путь она выберет. Затем Виктор входит в пещеру и выкрикивает название пути, по которому он хочет, чтобы она вернулась, A или B, выбранный наугад. При условии, что она действительно знает волшебное слово, это легко: она открывает дверь, если необходимо, и возвращается по желаемому пути.

предположим, что она не знала этого слова. Тогда она сможет вернуться только по названному пути, если Виктор назовет имя того же пути, по которому она вошла. Украина Виктор выберет A или B наугад, у нее будет 50% шанс правильно угадать. Он успешно предвидеть все запросы Виктора стал бы исчезающе малым (примерно один на миллион).

Таким образом, если Пегги появляется на выходе по именам Виктора, он может сделать вывод, что весьма вероятно, что Пегги действительно знает секретное слово.

Одно замечание в отношении сторонних наблюдателей: даже если Виктор носит скрытую камеру, которая записывает всю транзакцию, единственное, что камера будет записывать, - это в одном случае Виктор кричит «А!» и Пегги появляется на А, или, в другом случае, Виктор кричит "Б!" и Пегги появляется в B. Запись такого типа будет тривиальной для любых людей (требуется только, чтобы Пегги и Виктор заранее согласовали последовательность A и B, которые Виктор будет кричать). Такая запись, конечно, никогда не убедит никого, кроме первоначальных участников. Фактически, даже человек, присутствовавший в качестве наблюдателя при первоначальном эксперименте, не убедился в этом, как Виктор и Пегги начал «эксперимент» от начала до конца.

Также обратите внимание, что если Виктор выбирает свои A и B, подбрасывая монету на камеру, этот протокол теряет свойство нулевого разглашения; подбрасывание на камеру, вероятно, будет монетным для любого человека, который позже будет смотреть запись. Таким образом, хотя это не раскрывает секретное слово Виктору, это действительно позволяет Виктору убедить мир в целом, что Пегги обладает знанием - вопреки заявленным желанием Пегги. Цифровая криптография обычно «подбрасывает монеты», полагаясь на генератор псевдослучайных чисел , который похож на монету с фиксированным рисунком орла и решки, известным только владельцу монеты. Если бы монета Виктора вела себя подобным образом, то Виктор и Пегги снова могли бы сфальсифицировать «эксперимент», поэтому использование генератора псевдослучайных чисел не раскроет миру знания Пегги так же, как использование перевернутой монеты. было бы.

Обратите внимание, что Пегги могла доказать Виктору, что она знает волшебное слово, не раскрывая его ему, в одном испытании. Если и Виктор, и Пегги вместе пойдут ко входу в пещеру, Виктор сможет вести, как Пегги входит через A и выходит через B. Это с уверенностью докажет, что Пегги знает волшебное слово, не раскрывая волшебное слово Виктору. Однако такое доказательство может быть обнаружено третьей стороной или записано Виктором, и такое доказательство будет убедительным для любого. Другими словами, Пегги не могла опровергнуть такое доказательство, заявив, что она была в сговоре с Виктором, и поэтому она больше не контролирует, кто знает ее знаниях.

Два шара и друг-дальтоник

Представьте, что ваш друг красно-зеленый дальтоник (пока вы не дальтоник), и у вас есть два шара: один красный и один зеленый, но в остальном идентичный. Вашему другу они кажутся полностью идентичными, и он скептически к тому. Вы хотите доказать ему, что они на самом деле другого цвета, но не более того; в частности, вы не хотите раскрывать, какой из них красный, а какой зеленый.

Вот система доказательств. Вы отдаете два мяча своему другу, и он кладет их за спину. Затем он берет один из шаров, достает его из-за спины и показывает его. Затем он снова кладет его за спину, а затем решает показать только один из двух шаров, выбирая один из двух наугад с равной вероятностью. Он спросит вас: «Я подменил мяч?» Затем вся процедура повторяется столько раз, сколько необходимо.

Глядя на их цвета, вы, конечно, можете с уверенностью сказать, поменял ли он их или нет. С другой стороны, если бы они были одного цвета и, следовательно, неразличимы, вы не смогли бы правильно угадать с вероятностью выше 50%.

вероятность того, что вам случайным образом удастся идентифицировать каждый переключатель / не переключение, составляет 50%, вероятность случайного успеха всех переключателей / не переключателей приближается к нулю («разумность»). Если вы и ваш друг это «доказательство» несколько раз (например, 100 раз), ваш друг должен убедиться («полнота»), что шары действительно разного цвета.

Приведенное выше доказательство является нулевым разглашением, потому что ваш друг никогда не узнает, какой шар зеленый, а какой красный; действительно, он ничего не знает о том, как различать шары.

Где Уолли?

Где Уолли? (или Где Уолли?) - это книжка с картинками, где читателю предлагается найти маленького персонажа по имени Уолли, спрятанному где-то на странице с двойным разворотом, заполненной множеством других персонажей. Картины сделаны так, что Уолли сложно найти.

Представьте, что вы профессионал. Где Уолли? решатель. Компания приходит к вам с вопросом "Где Уолли?" книга, которую им нужно решить. Компания хочет, чтобы вы доказали, что вы на самом деле профессионал. Где Уолли? решатель и поэтому просит вас найти Уолли на картинке из их книги. Проблема в том, что вы не хотите работать на них без оплаты.

И вы, и компания хотите сотрудничать, но вы не доверяете друг другу. Не существует, что можно удовлетворить потребности компании, не выполняя для них бесплатную работу, но на самом деле существует доказательство с помощью этого разглашения, которое позволяет вам представить компанию, где находится Уолли, не раскрывая ее. им, как вы его нашли, или где он.

Доказательство выглядит следующим образом: вы просите представителя компании повернуться, а затем получить очень большой кусок картона на картинку так, чтобы центр картона находился над Уолли. Вырезаете маленькое окошко в центре картона, чтобы был виден Уолли. Теперь вы можете попросить большого представителя компании повернуться и осмотреть кусок картона с отверстием посередине и увидеть, что Уолли виден через отверстие. Картон достаточно большой, поэтому невозможно определить положение книги под картоном. Затем вы просите представителя повернуться назад, чтобы вы удалить картон и вернуть книгу.

Как описано, это доказательство является иллюстрацией и не является полностью строгим. Представитель компании должен быть уверен, что вы не пронесли в комнату Уолли. Что-то вроде преподавенного от взлома перчаточного ящика может быть в более строгом доказательстве. Вышеупомянутое доказательство также приводит к тому, что положение тела Уолли передается представителю компании, что может помочь им найти Уолли, если его положение изменится в каждом разделе Где Уолли? головоломка.

Определение

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

1. Полнота : если утверждение истинно, честный проверяющий (то есть тот, кто правильно следует протоколу) в этом факте доказит честный доказывающий.
2. Обоснованность : если утверждение ложно, никакой обманщик не сможет убедить проверяющего в его истинности, за некоторой малой вероятности.
3. : если утверждение истинно, ни один проверяющий не узнает ничего, кроме того факта, что утверждение истинно. Другими словами, знание языка утверждения (а не секрета) достаточно, чтобы представить сценарий, показывающий, что доказывающий знает секрет. Это формализуется путем демонстрации того, что у каждого проверяющего есть некий имитатор, который при наличии только подтверждения, нужно доказать (и без доступа к доказывающему), может создать стенограмму, которая «выглядит» как взаимодействие между честным доказывающим и рассматриваемым проверяющим.

Первые два из них свойств более общих имеют интерактивных доказательств. Третье - это то, что делает доказательство нулевым разглашением.

Доказательства с нулевым разглашением не являются доказательствами в математическом смысле этого слова, потому что существует некоторая небольшая вероятность, ошибка здравого смысла, что мошеннический доказывающий сможет убедить проверяющего в ложном утверждении. Другими словами, доказательства с нулевым разглашением вероятными «доказательствами», а не детерминированными доказательствами. Однако есть методы, позволяющие уменьшить ошибку до пренебрежимо малых значений.

Формальное определение нулевого знания должно использовать некоторую вычислительную модель, наиболее распространенной из которой является модель машины Тьюринга. Пусть $P\; \{\backslash \; displaystyle\; P\}$, $V\; \{\backslash \; displaystyle\; V\}$и $S\; \{\backslash \; displaystyle\; S\}$машины Тьюринга. интерактивная система проверки с $(P,\; V)\; \{\backslash \; displaystyle\; (P,\; V)\}$для языка $L\; \{\backslash \; displaystyle\; L\}$является нулевым разглашением, если для любого вероятностного полиномиального времени (PPT) верификатор $V\; ^\; \{\backslash \; displaystyle\; \{\backslash \; hat\; \{V\}\}\}$существует симулятор PPT $S\; \{\; \backslash \; Displaystyle\; S\}$такой, что

$\forall \; x\; \in \; L,\; z\; \in \; \{0,\; 1\}\; \ast ,\; представление\; V\; ^\; \; [P\; (x)\; \leftrightarrow \; V\; ^\; (x,\; z)]\; =\; S\; (Икс,\; Z)\; \{\backslash \; Displaystyle\; \backslash \; forall\; х\; \backslash \; в\; L,\; z\; \backslash \; in\; \backslash \; \{0,1\; \backslash \}\; ^\; \{*\},\; \backslash \; operatorname\; \{View\}\; \_\; \{\backslash \; hat\; \{V\}\}\; \backslash \; left\; [P\; (x)\; \backslash \; leftrightarrow\; \{\backslash \; hat\; \{V\}\}\; (x,\; z)\; \backslash \; right]\; =\; S\; (x,\; z)\}$

где $Просмотр\; V\; ^\; \; [P\; (x)\; \leftrightarrow \; V\; ^\; (x,\; z)]\; \{\backslash \; displaystyle\; \backslash \; operatorname\; \{View\}\; \_\; \{\backslash \; hat\; \{V\}\}\; \backslash \; left\; [P\; (x)\; \backslash \; leftrightarrow\; \{\backslash \; hat\; \{V\}\}\; (x,\; z)\; \backslash \; right]\}$является записью записий между $P\; (x)\; \{\backslash \; displaystyle\; P\; (x)\}$и $V\; ^\; (x,\; z)\; \{\backslash \; displaystyle\; \{\backslash \; hat\; \{V\}\}\; (x,\; z)\}$. Прувер $P\; \{\backslash \; displaystyle\; P\}$моделируется как имеющий неограниченную вычислительную мощность (на практике $P\; \{\backslash \; displaystyle\; P\}$обычно является вероятностным представителем Тьюринга ). Интуитивно определение гласит, интерактивная система доказательств $(P,\; V)\; \{\backslash \; displaystyle\; (P,\; V)\}$является нулевым разглашением, если для верификатора $V\; ^\; \{\backslash \; displaystyle\; \{\backslash \; hat\; \{V)\; \}\}\}$существует эффективный симулятор $S\; \{\backslash \; displaystyle\; S\}$(в зависимости от $V\; ^\; \{\backslash \; displaystyle\; \{\backslash \; hat\; \{V\}\}\}$), который может воспроизводить диалог между $P\; \{\backslash \; displaystyle\; P\}$и $V\; ^\; \{\backslash \; displaystyle\; \{\backslash \; hat\; \{V\}\}\}$на любом заданном входе. Вспомогательная строка $z\; \{\backslash \; displaystyle\; z\}$играет роль «предварительных знаний» (включая случайные монеты $V\; ^\; \{\backslash \; displaystyle\; \{\backslash \; hat\; \{V\}\}\}$). Определение подразумевает, что $V\; ^\; \{\backslash \; displaystyle\; \{\backslash \; hat\; \{V\}\}\}$не может использовать какую-либо систему предшествующих знаний $z\; \{\backslash \; displaystyle\; z\}$для добычи информации вне его разговора с $P\; \{\backslash \; displaystyle\; P\}$, потому что если $S\; \{\backslash \; displaystyle\; S\}$также получил это предварительное знание, то он может воспроизвести разговор между $V\; ^\; \{\backslash \; displaystyle\; \{\backslash \; hat\; \{V\}\}\}$и $P\; \{\backslash \; displaystyle\; P\}$, как и раньше.

Дано определения совершенного нулевого. Вычислительное нулевое знание достигается путем требований, предъявляемых к представлению верификатора $V\; ^\; \{\backslash \; displaystyle\; \{\backslash \; hat\; \{V\}\}\}$и симулятора были только вычислительно неразличимы, с учетом специальных требований.

Практические примеры

Дискретный журнал заданного значения

Мы можем применить эти идеи к более реалистичному криптографическому приложению. Пегги хочет доказать Виктору, что ей известна дискретная логарифм заданное значение в данной группе .

, например, учитывая значение $y\; \{\backslash \; displaystyle\; y\}$, большой prime $p\; \{\backslash \; displaystyle\; p\}$и генератор $g\; \{\backslash \; displaystyle\; g\}$, она хочет доказать, что ей известно значение $x\; \{\backslash \; displaystyle\; x\}$такое, что $gx\; mod\; p\; =\; y\; \{\backslash \; displaystyle\; g\; ^\; \{x\}\; \{\backslash \; bmod\; \{p\}\}\; =\; y\}$, не раскрывая $х\; \{\backslash \; displaystyle\; x\}$. Действительно, знание $x\; \{\backslash \; displaystyle\; x\}$какое-то место в качестве доказательства личности, поскольку она выбрала случайное значение $x\; \{\backslash \; displaystyle\; x\}$, которую она никому не раскрывала, вычислила $y\; =\; gx\; mod\; p\; \{\backslash \; displaystyle\; y\; =\; g\; ^\; \{x\}\; \{\backslash \; bmod\; \{p\}\}\}$и распространила $y\; \{\backslash \; displaystyle\; y\}$для всех использованных проверяющих, так что позже доказательство знания $x\; \{\backslash \; displaystyle\; x\}$эквивалентно для подтверждения личности как Пегги.

Протокол работает следующим образом: в каждом раунде Пегги генерирует случайное число $r\; \{\backslash \; displaystyle\; r\}$, вычисляет $C\; =\; gr\; mod\; p\; \{\backslash \; displaystyle\; C\; =\; g\; ^\; \{r\}\; \{\backslash \; bmod\; \{p\}\}\}$и раскрывает это Виктору. Получив $C\; \{\backslash \; displaystyle\; C\}$, Виктор случайным образом отправляет один из следующих двух запросов: он либо запрашивает, чтобы Пегги раскрыла значение $r\; \{\backslash \; displaystyle\; r\}$или значение $(x\; +\; r)\; mod\; (p\; -\; 1)\; \{\backslash \; displaystyle\; (x\; +\; r)\; \{\backslash \; bmod\; \{(p-1)\}\}\}$. При ответе Пегги раскрывает только случайное значение, поэтому при правильном выполнении одного раунда протокола никакой информации не раскрывается.

Виктор может проверить любой ответ; если он запросил $r\; \{\backslash \; displaystyle\; r\}$, он может затем вычислить $gr\; mod\; p\; \{\backslash \; displaystyle\; g\; ^\; \{r\}\; \{\backslash \; bmod\; \{p\}\}\}$и убедитесь, что он соответствует $C\; \{\backslash \; displaystyle\; C\}$. Если он запросил $(x\; +\; r)\; mod\; (p\; -\; 1)\; \{\backslash \; displaystyle\; (x\; +\; r)\; \{\backslash \; bmod\; \{(p-1)\}\}\}$, он может проверить, что $C\; \{\backslash \; displaystyle\; C\}$согласуется с этим путем вычислений $g\; (x\; +\; r)\; mod\; (p\; -\; 1)\; mod\; p\; \{\backslash \; displaystyle\; g\; ^\; \{(x\; +\; r)\; \{\backslash \; bmod\; \{(p-1)\}\}\}\; \{\backslash \; bmod\; \{p\}\}\}$и проверка его соответствия $C\; \cdot \; y\; mod\; p\; \{\backslash \; displaystyle\; C\; \backslash \; cdot\; y\; \{\backslash \; bmod\; \{p\}\}\}$. Если Пегги действительно знает значение $x\; \{\backslash \; displaystyle\; x\}$, она может ответить на любого из преступников Виктора.

Если бы Пегги знала или могла догадаться, какой вызов бросить Виктор, она могла бы легко обмануть и убедить Виктора, что она знает $x\; \{\backslash \; displaystyle\; x\}$, когда не знает : если она знает, что Виктор собирается запросить $r\; \{\backslash \; displaystyle\; r\}$, то она работает нормально: она выбирает $r\; \{\backslash \; displaystyle\; r\}$, вычисляет $C\; =\; gr\; mod\; p\; \{\backslash \; displaystyle\; C\; =\; g\; ^\; \{r\}\; \{\backslash \; bmod\; \{p\}\}\}$и раскрывает $C\; \{\backslash \; displaystyle\; C\}$к Виктор ; она сможет ответить на вызов Виктора. С другой стороны, если она знает, что Виктор запросит $(x\; +\; r)\; mod\; (p\; -\; 1)\; \{\backslash \; displaystyle\; (x\; +\; r)\; \{\backslash \; bmod\; \{(p-1)\}\}\}$, затем она выбирает случайное значение $r\; \prime \; \{\backslash \; displaystyle\; r\; \text{'}\}$, вычисляет $C\; \prime \; =\; gr\; \prime \; \cdot \; (gx)\; -\; 1\; mod\; p\; \{\backslash \; displaystyle\; C\text{'}\; =\; g\; ^\; \{r\; \text{'}\}\; \backslash \; cdot\; \backslash \; left\; (g\; ^\; \{x\}\; \backslash \; right)\; ^\; \{-\; 1\}\; \{\backslash \; bmod\; \{p\}\}\}$, и раскрывает $C\text{'}\; \{\backslash \; displaystyle\; C\; \text{'}\}$Виктору как значение $C\; \{\backslash \; displaystyle\; C\}$, которое он ожидает. Когда Виктор предлагает ей раскрыть $(x\; +\; r)\; mod\; (p\; -\; 1)\; \{\backslash \; displaystyle\; (x\; +\; r)\; \{\backslash \; bmod\; \{(p-1)\}\}\}$, она показывает $r\; \prime \; \{\backslash \; displaystyle\; r\; \text{'}\}$, для которого Виктор провеританность, поскольку он, в свою очередь, вычислит $gr\; \prime \; mod\; p\; \{\backslash \; displaystyle\; g\; ^\; \{r\text{'}\}\; \{\backslash \; bmod\; \{p\; \}\}\}$, что соответствует $C\; \prime \; \cdot \; y\; \{\backslash \; displaystyle\; C\; \text{'}\backslash \; cdot\; y\}$, поскольку Пегги, умноженная на обратную запись $y\; \{\backslash \; displaystyle\; y\; \}$.

Однако, если в любом из вышеперечисленных сценариев Виктор выдает вызов, отличный от того, которого она ожидала, она не сможет ответить на вызов при допущении невозможности выполнения решения дискретного журнала для этой группы. Если она выбрала $r\; \{\backslash \; displaystyle\; r\}$и раскрыла $C\; =\; gr\; mod\; p\; \{\backslash \; displaystyle\; C\; =\; g\; ^\; \{r\}\; \{\backslash \; bmod\; \{p\}\}\}$, то есть не может создать действительный $(x\; +\; r)\; mod\; (p\; -\; 1)\; \{\backslash \; displaystyle\; (x\; +\; r)\; \{\backslash \; bmod\; \{(p-1)\}\}\}$, который проходит проверку Виктора, учитывая, что она не знает $x\; \{\backslash \; displaystyle\; x\}$. И если она выбрала значение $r\; \prime \; \{\backslash \; displaystyle\; r\; \text{'}\}$, которое представляет собой $(x\; +\; r)\; mod\; (p\; -\; 1)\; \{\backslash \; displaystyle\; (x\; +\; r)\; \{\backslash \; bmod\; \{(p-1)\}\}\}$, тогда дискретным журналом значения, которое раскрыла, - но Пегги не знает этого дискретного журнала, поскольку значение C, которое она раскрыла, было получено с помощью арифметики с известными значениями, путем не вычислений с помощью метода известного показателя степени.

Таким образом, вероятность успешного мошенничества у проверяющего есть 0,5 в одном раунде. При выполнении достаточно большого количества раундов вероятность мошенничества может быть сколь угодно низкой.

Краткое описание

Пегги доказывает, что знает значение x (например, свой пароль).

1. Пегги и Виктор договариваются о простом $p\; \{\backslash \; displaystyle\; p\}$и образующем $g\; \{\backslash \; displaystyle\; g\}$мультипликативной группы поля. $Z\; p\; \{\backslash \; displaystyle\; \backslash \; mathbb\; \{Z\}\; \_\; \{p\}\}$.
2. Пегги вычисляет значение $y\; =\; gx\; mod\; p\; \{\backslash \; displaystyle\; y\; =\; g\; ^\; \{x\}\; \{\backslash \; bmod\; \{p\}\}\}$и передает значение Виктору.
3. Следующие два шага повторяются (большое) количество раз.
   1. Пегги несколько раз выбирает случайное значение $r\; \in \; U\; [0,\; p\; -\; 1]\; \{\backslash \; displaystyle\; r\; \backslash \; in\; U\; [0,\; p-1]\}$и вычисляет $C\; =\; gr\; mod\; p\; \{\backslash \; displaystyle\; C\; =\; g\; ^\; \{r\}\; \{\backslash \; bmod\; \{p\}\}\}$. Она передает Виктору значение $C\; \{\backslash \; displaystyle\; C\}$.
   2. Виктор просит Пегги вычислить и передать либо значение $(x\; +\; r)\; mod\; (p\; -\; 1)\; \{\backslash \; displaystyle\; (x\; +\; r)\; \{\backslash \; bmod\; \{(p-1)\}\}\}$или значение $r\; \{\backslash \; displaystyle\; r\}$. В первом случае Виктор проверяет $(C\; \cdot \; y)\; mod\; p\; \equiv \; g\; (x\; +\; r)\; mod\; (p\; -\; 1)\; mod\; p\; \{\backslash \; displaystyle\; (C\; \backslash \; cdot\; y)\; \{\backslash \; bmod\; \{p\}\}\; \backslash \; Equiv\; g\; ^\; \{(x\; +\; r)\; \{\backslash \; bmod\; \{(p-1)\}\}\}\; \{\backslash \; bmod\; \{p\}\}\}$. Во втором случае он проверяет $C\; \equiv \; gr\; mod\; p\; \{\backslash \; displaystyle\; C\; \backslash \; Equiv\; g\; ^\; \{r\}\; \{\backslash \; bmod\; \{p\}\}\}$.

Значение $(x\; +\; r)\; mod\; (p\; -\; 1)\; \{\backslash \; displaystyle\; (x\; +\; r)\; \{\backslash \; bmod\; \{(\}\}\; p-1)\}$можно рассматривать как зашифрованное значение $x\; mod\; (p\; -\; 1)\; \{\backslash \; displaystyle\; x\; \{\backslash \; bmod\; \{(\; \}\}\; р-1)\}$. Если $r\; \{\backslash \; displaystyle\; r\}$действительно случайный, равномерно распределенный от нуля до $(p\; -\; 1)\; \{\backslash \; displaystyle\; (p-1)\}$, это не пропускает никакой информации о $x\; \{\backslash \; displaystyle\; x\}$(см. одноразовый блокнот ).

Гамильтонов цикл для большого графа

Следующая схема принадлежит Мануэлю Блюму.

В этой сценарии Пегги знает цикл гамильтонов для большого график G. Виктор знает G, но не цикл (например, Пегги сгенерировала Gи открыла его ему.) Нахождение гамильтонова цикла для большого графа считается вычислительно невозможным, поскольку его соответствующая версия решения известна как НП-полный. Пегги докажет, что знает цикл, не просто раскрывая его (возможно, Виктор заинтересован в его покупке, но сначала хочет проверить, или, может быть, Пегги - единственная, кто знает эту информацию и доказывает свою личность Виктору).

Чтобы показать, что Пегги знает этот цикл гамильтонов, они с Виктором играют в несколько раундов игр.

• В начале каждого раунда Пегги создает H, график, который изоморфен G(т.е. Hпросто как G, за исключением того, что все вершины имеют разные имена). Преобразовать цикл гамильтонов между изоморфными графами известным изоморфизмом тривиально, если Пегги знает цикл гамильтонов для G, она также должна знать один для H.
• Пегги соглашается на H. Она могла это, используя криптографическую схему обязательств. В качестве альтернативы она могла бы пронумеровать вершины H, затем для каждого края Hнаписать на небольшом листе бумаги, содержащем две вершины края, и положить эти кусочки бумаги лицом на стол. Цель этого обязательства состоит в том, что Пегги не может изменить H, в то время как Виктор имеет информацию о H.
• , а затем Виктор случайным образом выбирает один из двух вопросов, чтобы задать Пегги. Он может либо попросить ее показать изоморфизм между H и G(см. проблема изоморфизма графов ), либо он может попросить ее показать гамильтонов цикл в H.
• Если Пегги попросят показать, что эти два графа изоморфны, она сначала раскрывает все H(например, переворачивая все листы бумаги, которые кладет на стол), а затем переводы вершин, которые отображают Gдо H. Виктор может проверить, что они действительно изоморфны.
• Если Пегги попросят доказать, что она знает цикл гамильтонов в H, она переводит свой гамильтонов цикл в Gна Hи раскрывает только ребра гамильтонова цикла. Этого достаточно для Виктора, чтобы проверить, что Hдействительно содержит цикл гамильтонов.

Важно, чтобы привязка к графу была такая, чтобы Виктор мог проверить во втором случае, что цикл действительно сделан из кромок из H. Это можно сделать, например, зафиксировав каждое ребро (или его отсутствие) отдельно.

Полнота

Если Пегги действительно знает гамильтонов цикл в G, она может легко удовлетворить требование Виктора в отношении изоморфизма графов, производящего Hиз G(который она взяла на себя на первом этапе) или гамильтонов цикл в H(который она может построить, применив изоморфизм к циклу в G).

Нулевое знание

Ответы Пегги не раскрывают исходный гамильтонов цикл в G. Каждый раунд Виктор будет изучать только изоморфизм Hв Gили гамильтонов цикл в H. Ему потребуются оба ответа для одного H, чтобы построить цикл в G, поэтому информация остается неизвестной, пока Пегги может генерировать отдельный Hкаждый раунд.. Если Пегги не знает о гамильтоновом цикле в G, но каким-то образом заранее знала, что Виктор попросит увидеть каждый раунд, тогда она могла бы обмануть. Например, если бы Пегги заранее знала, что Виктор попросит увидеть гамильтонов цикл в H, она могла бы сгенерировать гамильтонов цикл для несвязанного графа. Точно так же, если бы Пегги знала заранее, что Виктор попросит показать изоморфизм, она могла бы просто сгенерировать изоморфный граф H(в котором также ей не известен цикл гамильтонов). Виктор может смоделировать протокол самостоятельно (без Пегги), потому что он знает, что он попросит показать. Следовательно, Виктор не получает никакой информации о гамильтоновом цикле в Gиз информации, раскрываемой в каждом раунде.

Надежность

Если Пегги не знает информации, она может угадать, какой вопрос задаст Виктор, и сгенерировать либо граф, изоморфный G, либо гамильтонов цикл для несвязанного графика, но поскольку она не знает гамильтонова цикла для G, она не может сделать оба. При такой догадке ее шанс обмануть Виктора равенство 2, где n- количество раундов. Для всех реалистичных целей невероятно сложно победить доказательство с нулевым разглашением с помощью разумного числа раундов таким способом.

Варианты с нулевым разглашением

Различные варианты с нулевым разглашением могут быть реализованы посредством формы интуитивного представления о, что подразумевается под результатами симуляция, «похожими на» выполнение реальных примеров методов методов:

• Мы говорим о совершенном нулевом разглашении, если распределение, созданное симулятором и протоколом доказательства, распределяются точно так же. Это, например, случай в первом примере выше.
• Статистическое нулевое знание означает, что они статистически близки, что означает, что их статистическая разница является незначительной функцией .
• Мы говорим о вычислительном нулевом разглашении, если эффективный алгоритм не может различить два распределения.

Типы с нулевым разглашением

• Доказательство знания : знание скрыто в экспоненте как в показанном выше.
• Криптография на основе пар : заданы f (x) и f (y), без знаний xи y, можно вычислить f (x×y).
• Свидетельские доказательства доказательства доказательства : какой-либо свидетельство используется для доказательства.
• Многостороннее вычисление : в то время как каждая сторона может хранить свой секрет, они вместе
• Кольцевая подпись : посторонние не знают, какой ключ используется для подписи.

Приложения

Aut системы проверки

Исследования доказательств с нулевым разглашением были мотивированы системой аутентификации, в которой одна сторона этой секретной информации используется вторая сторона с помощью некоторой секретной информации (например, одна сторона этого секрета), но не делает этого вторая сторона этой узнала что-нибудь об секрете. «Доказательством знания с нулевым разглашением ». учайный, чтобы его можно было использовать во многих схемах подтверждения знаний с нулевым разглашением. Пароль с нулевым разглашением - это особый вид доказательства с нулевым разглашением, который касается ограниченного размера паролей.

Этическое поведение

Одним из способов использования доказательств с нулевым разглашением в криптографических протоколах является обеспечение честного поведения при сохранении конфиденциальности. В соответствии с протоколом, доказать, что заставить его использовать доказательство с нулевым разглашением, доказать, что его поведение является правильным в соответствии с протоколом. Мы знаем, что из соображений надежности пользователь должен действительно действовать честно, чтобы иметь возможность предоставить достоверное доказательство. Из-за нулевого знания мы знаем, что пользователь не знает под угрозу конфиденциальность своих секретов в процессе предоставления доказательства.

Ядерное разоружение

В 2016 году Принстонская лаборатория физики плазмы и Принстонский университет применили новую технику, которая может быть применима к будущим переговорам по ядерному разоружению. Это позволит инспекторам подтвердить, что действительно ли объект является ядерным оружием, без регистрации, которая может быть секретной.

Блокчейны

Предполагается, что ZKP может использоваться для гарантии того, что транзакции действительны, несмотря на то, что информация об отправителе, получателе и другие детали транзакции остаются скрытыми. История

Доказательства с нулевым разглашением были впервые предложены в 1989 году Шафи Гольдвассером, Сильвио Микали и Чарльзом Ракоффом в их статье «Знание» Сложность интерактивных Proof-систем ». В этой статье представлена ​​иерархия IP интерактивных систем доказательства (см. интерактивная система доказательств ) и разработана концепция сложности знаний, измерения количества знаний о доказательстве, передаваемых от доказывающего. верификатору. Они также дали первое доказательство с нулевым разглашением для конкретной проблемы, а именно решения квадратичных невычетов mod m. Вместе с докладом Ласло Бабая и Шломо Морана в этой знаменательной статье были изобретены интерактивные системы доказательства, за которые все пять авторов получили первую премию Гёделя в 1993 году.

По их собственным словам, Голдвассер, Микали и Ракофф говорят:

Особый интерес представляет случай, когда это дополнительное знание по существу равно 0, и мы показываем, что [это] возможно интерактивно доказать, что число является квадратичным без остатка по модулю m, дающему 0 дополнительных знаний. Это удивительно, поскольку не известен эффективный алгоритм для определения модуля квадратичной остаточности m, если множитель m не задан. Более того, все известные NP-доказательства этой проблемы показывают факторизацию m на простые множители. Это указывает на то, что добавление взаимодействия к процессу доказательства может уменьшить объем знаний, которые необходимо сообщить, чтобы доказать теорему.

Квадратичная проблема невычетов имеет как алгоритм NP, так и алгоритм co-NP, и поэтому лежит на пересечении NP и со-НП . Это было верно и для нескольких других проблем, для которых впоследствии были обнаружены доказательства с нулевым разглашением, таких как неопубликованная система доказательств Одеда Голдрайха, подтверждающая, что двухпростой модуль не является целым числом Блюма.

Одед Голдрайх, Сильвио Микали и Ави Вигдерсон сделали еще один шаг вперед, продемонстрировав, что, допуская существование нерушимого шифрования, можно создать систему доказательства с нулевым разглашением для NP-полного задача раскраски графа в три цвета. Поскольку каждая проблема в NP может быть эффективно сведена к этой проблеме, это означает, что при этом предположении все проблемы в NP имеют доказательства с нулевым разглашением. Причина такого предположения в том, что, как и в приведенном выше примере, их протоколы требуют шифрования. Обычно цитируемым достаточным условием существования нерушимого шифрования является наличие односторонних функций, но вполне возможно, что некоторые физические средства также могут этого достичь.

Вдобавок к этому, они также показали, что проблема неизоморфизма графов, дополнение к проблеме изоморфизма графов, имеет нулевое - доказательство знаний. Эта проблема есть в НП, но в настоящее время не известно ни о НП, ни в любом практическом уроке. В более общем плане Рассел Импаглиаццо и Моти Юнг, а также Бен-Ор и др. продолжил бы, чтобы показать, что, также предполагаемая односторонние функции или нерушимое шифрование, есть доказательства с нулевым разглашением для всех проблем в IP= PSPACE, или, другими словами, всего, что может быть доказано интерактивным доказательством Система может быть доказана с нулевым разглашением.

Не любя делать ненужные предположения, многие теоретики искали способ устранения необходимости односторонних функций. Один из способов сделать это - использовать несколько независимых проверяющих систем, которые позволяют «избежать перекрестно исследовать» отдельных заблуждений, которые позволяют использовать несколько независимых систем доказательств (см. интерактивные системы доказательств ). Можно показать, что без каких-либо предположений о неразрешимости все языки в NP имеют доказательства с нулевым разглашением в такой системе.

Оказывается, что в условиях, подобных Интернету, где несколько протоколы могут выполняться одновременно, создание доказательств с нулевым разглашением является более сложной задачей. Линия исследований по изучению параллельных доказательств с нулевым разглашением была начата работами Дворка, Наора и Сахаи. Одно конкретное развитие в этих принципах была разработка протоколов неразличимости свидетелей. Свойство неразличимого свидетеля связано со своим нулевым разглашением, однако протоколы с неразличимым свидетелем не страдают теми же проблемами одинакового выполнения.

Другой вариант доказательств с нулевым разглашением - интерактивные доказательства с нулевым разглашением. Блюм, Фельдман и Микали показали, что общей случайной строки, используемой используемой которой, достаточно для достижения вычислительного нулевого знания без необходимости взаимодействия.

См. Также

• парадокс информации со стрелкой
• Криптографический протокол
• Схема идентификации Фейге-Фиат-Шамир
• Подтверждение знаний
• Темы в криптографии
• Неразличимое доказательство
• Пароль с нулевым разглашением
• Неинтерактивное доказательство с нулевым разглашением

Ссылки