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

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

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

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

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

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

Абстрактные примеры

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

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

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

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

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

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

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

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

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

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

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

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

Два мяча и друг-дальтоник

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

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

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

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

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

Где Уолли?

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

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

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

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

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

Определение

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

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

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

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

Формальное определение нулевого знания должно использовать некоторую вычислительную модель, наиболее распространенной из которых является модель Машина Тьюринга. Позволять ${ displaystyle P}$ , ${ displaystyle V}$ , и ${ displaystyle S}$ быть машинами Тьюринга. An интерактивная система доказательства с ${ displaystyle (P, V)}$ для языка ${ displaystyle L}$ является нулевым разглашением, если для любого вероятностное полиномиальное время (PPT) верификатор ${ displaystyle { hat {V}}}$ существует симулятор PPT ${ 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 (х + г) { bmod {(р-1)}}}$ . В любом ответе Пегги раскрывает только случайное значение, поэтому при правильном выполнении одного раунда протокола никакой информации не раскрывается.

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

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

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

Краткое содержание

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

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

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

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

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

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

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

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

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

Полнота

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

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

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

Разумность

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

Варианты нулевого знания

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

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

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

Доказательство знаний: знания скрыты в экспоненте, как в примере, показанном выше.
Криптография на основе пар: данный $f (Икс)$ и $f (у)$ , не зная $Икс$ и $у$ , можно вычислить $f (Икс \times у)$ .
Свидетель неотличимых доказательств: верификаторы не могут знать, какой свидетель используется для доказательства.
Многосторонние вычисления: хотя каждая партия может хранить свой секрет, вместе они дают результат.
Кольцевая подпись: посторонние понятия не имеют, какой ключ используется для подписи.

Приложения

Системы аутентификации

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

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

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

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

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

Блокчейны

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

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

История

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

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

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

Квадратичная проблема невычетов имеет как НП и со-НП алгоритм, и поэтому лежит на пересечении НП и со-НП. То же самое было и в отношении нескольких других проблем, для которых впоследствии были обнаружены доказательства с нулевым разглашением, таких как неопубликованная система доказательств Одеда Голдрайха, подтверждающая, что двухпростой модуль не является Целое число Блюма.^[20]

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

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

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

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

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