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

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

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

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

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

Некоторые формы неинтерактивных доказательств с нулевым знанием существует, ^{[2] [3]} , но действительность доказательства основывается на расчетных предположениях ( как правило , в предположениях идеальной криптографической хэш - функции ).

Абстрактные примеры [ править ]

Виктор выбирает путь выхода

Пегги достоверно появляется на выходе, имена Виктора

Пещера Али-Баба [ править ]

Хорошо известна история, представляющая фундаментальные идеи доказательств с нулевым разглашением, впервые опубликованная Жан-Жаком Кискватером и другими в их статье «Как объяснить детям протоколы с нулевым разглашением». ^[4] Это обычная практика для обозначения двух сторон в доказательстве с нулевым знанием , как Пегги ( прувер заявления) и Виктор ( верификатор заявления).

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

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

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

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

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

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

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

Два шара и дальтоник [ править ]

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

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

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

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

Вышеупомянутое доказательство - нулевое знание, потому что ваш друг никогда не узнает, какой шар коричневый, а какой красный; действительно, он ничего не знает о том, как различать шары. ^[5]

Где Уолли? [ редактировать ]

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

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

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

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

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

Определение [ править ]

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

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

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

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

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

${\ displaystyle \ forall x \ in L, z \ in \ {0,1 \} ^ {*}, \ operatorname {View} _ {\ hat {V}} \ left [P (x) \ leftrightarrow {\ hat {V}} (x, z) \ right] = S (x, z)}$

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

Приведено определение совершенного нулевого знания. Вычислительное нулевое знание достигается за счет требования, чтобы представления верификатора и симулятора были неразличимы только в вычислительном отношении , учитывая вспомогательную строку.${\ displaystyle {\ hat {V}}}$

Практические примеры [ править ]

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

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

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

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

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

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

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

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

Краткое описание [ править ]

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

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

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

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

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

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

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

• В начале каждого раунда, Пегги создает H , граф, изоморфный к G (т.е. Н так же , как 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 изоморфизм «s к G или гамильтонов цикл в H . Ему понадобятся оба ответа для одного H, чтобы обнаружить цикл в G , поэтому информация остается неизвестной, пока Пегги может генерировать отдельный H каждый раунд. Если Пегги не знает о гамильтоновом цикле в G , но каким-то образом заранее знала, что Виктор попросит увидеть каждый круг, тогда она могла бы обмануть. Например, если бы Пегги заранее знала, что Виктор попросит увидеть гамильтонов цикл в Hтогда она могла бы создать гамильтонов цикл для несвязанного графа. Точно так же, если бы Пегги знала заранее, что Виктор попросит показать изоморфизм, она могла бы просто сгенерировать изоморфный граф H (в котором она также не знает гамильтонова цикла). Виктор может смоделировать протокол самостоятельно (без Пегги), потому что он знает, что он попросит показать. Следовательно, Виктор не получает информации о гамильтоновом цикле в G из информации, раскрываемой в каждом раунде.

Обоснованность [ править ]

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

Варианты нулевого знания [ править ]

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

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

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

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

Приложения [ править ]

Системы аутентификации [ править ]

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

Этическое поведение [ править ]

Одним из способов использования доказательств с нулевым разглашением в криптографических протоколах является обеспечение честного поведения при сохранении конфиденциальности. Грубо говоря, идея состоит в том, чтобы заставить пользователя доказать, используя доказательство с нулевым разглашением, что его поведение является правильным в соответствии с протоколом. ^{[9] [10]} Мы знаем, что в силу здравого смысла пользователь должен действительно действовать честно, чтобы иметь возможность предоставить действительное доказательство. Из-за нулевого знания мы знаем, что пользователь не ставит под угрозу конфиденциальность своих секретов в процессе предоставления доказательства.

Ядерное разоружение [ править ]

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

Блокчейны [ править ]

Доказательства с нулевым разглашением были применены в протоколах Zerocoin и Zerocash, что привело к рождению Zcoin ^[12] (позже переименованного в Firo в 2020 году) ^[13] и криптовалют Zcash . Zerocoin имеет встроенную модель микширования, которая не доверяет никаким партнерам или централизованным провайдерам микширования для обеспечения анонимности. ^[12] Пользователи могут совершать транзакции в базовой валюте, а также менять валюту на Zerocoins и обратно. ^[14] Протокол Zerocash использует аналогичную модель (вариант, известный как неинтерактивное доказательство с нулевым разглашением ) ^[15]за исключением того, что он может скрыть сумму транзакции, а Zerocoin - нет. Учитывая значительные ограничения данных транзакций в сети Zerocash, Zerocash менее подвержен атакам на конфиденциальность по сравнению с Zerocoin. Однако этот дополнительный уровень конфиденциальности может вызвать потенциально необнаруженную гиперинфляцию предложения Zerocash, поскольку мошеннические монеты не могут быть отслежены. ^{[12] [16]}

В 2018 был выпущен Bulletproofs. Это улучшение по сравнению с неинтерактивным доказательством с нулевым разглашением, когда надежная установка не требуется. ^[17] Позже он был реализован в протоколе Mimblewimble (на котором основаны криптовалюты Grin и Beam) и в криптовалюте Monero . ^[18] В 2019 году Firo внедрила протокол Sigma, который является улучшением протокола Zerocoin без надежной настройки. ^{[19] [20]} В том же году Фиро представил протокол Lelantus, усовершенствованный протокол Sigma, в котором первый скрывает происхождение и сумму транзакции. ^[21]

История [ править ]

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

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

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

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

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

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

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

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

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

См. Также [ править ]

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

Ссылки [ править ]