В криптографии доказательство с нулевым разглашением или протокол с нулевым разглашением — это метод, с помощью которого одна сторона (доказывающая) может доказать другой стороне (проверяющей), что некоторое данное утверждение верно, избегая при этом передачи проверяющему какую-либо информацию, выходящую за рамки просто факт истинности этого утверждения. [1] Интуиция, лежащая в основе доказательств с нулевым разглашением, заключается в том, что доказать владение соответствующей информацией тривиально, просто раскрыв ее; самое сложное — доказать это владение, не раскрывая эту информацию (или какой-либо ее аспект). [2]
В свете того факта, что человек должен быть в состоянии создать доказательство некоторого утверждения только тогда, когда обладает определенной секретной информацией, связанной с этим утверждением, проверяющий, даже убедившись в истинности утверждения, тем не менее, должен оставаться неспособным доказать истинность утверждения. заявление третьим лицам.
В простой модели нетривиальные доказательства с нулевым разглашением (т. е. для языков, не входящих в BPP ) требуют взаимодействия между доказывающим и проверяющим. [3] Это взаимодействие обычно влечет за собой выбор проверяющим одного или нескольких случайных вызовов; случайное происхождение этих проблем, а также успешные ответы на них проверяющего, несмотря на это, все вместе убеждают проверяющего в том, что проверяющий действительно обладает заявленными знаниями. (Если бы взаимодействие отсутствовало, то проверяющий, получив расшифровку выполнения протокола — то есть единственное сообщение проверяющего — мог бы воспроизвести эту расшифровку третьей стороне, тем самым убедив третью сторону в том, что проверяющая сторона тоже владеет секретной информацией. )
В обычных моделях случайных строк и случайных оракулов существуют неинтерактивные доказательства с нулевым разглашением в свете эвристики Фиата – Шамира . [4] [5] [6] Эти доказательства на практике основаны на вычислительных предположениях (обычно на устойчивости к коллизиям криптографической хэш-функции ).
Существует хорошо известная история, представляющая фундаментальные идеи доказательств с нулевым разглашением, впервые опубликованная в 1990 году Жан-Жаком Кискатером и другими в их статье «Как объяснить вашим детям протоколы с нулевым разглашением». [7] В истории доказательства с нулевым разглашением участвуют две стороны: Пегги как доказывающий утверждение и Виктор как проверяющий утверждение .
В этой истории Пегги раскрыла секретное слово, с помощью которого можно открыть волшебную дверь в пещере. Пещера имеет форму кольца: вход с одной стороны и волшебная дверь, закрывающая противоположную сторону. Виктор хочет знать, знает ли Пегги секретное слово; но Пегги, будучи очень закрытым человеком, не хочет раскрывать свои знания (секретное слово) Виктору или раскрывать факт своего знания миру в целом.
Они помечают левый и правый пути от входа A и B. Сначала Виктор ждет снаружи пещеры, пока Пегги входит. Пегги выбирает либо путь A, либо B; Виктору не разрешено видеть, по какому пути она идет. Затем Виктор входит в пещеру и выкрикивает название пути, по которому она должна вернуться: A или B, выбранного наугад. Если она действительно знает волшебное слово, это легко: она открывает дверь, если нужно, и возвращается по нужному пути.
Однако предположим, что она не знала этого слова. Тогда она сможет вернуться по указанному пути только в том случае, если Виктор назовет тот же путь, по которому она вошла. Поскольку Виктор выберет А или Б наугад, у нее будет 50% шанс угадать правильно. Если бы они повторили этот трюк много раз, скажем, 20 раз подряд, ее шансы успешно предугадать все запросы Виктора уменьшились бы до 1 из 2 20 , или 9,56 × 10 −7 .
Таким образом, если Пегги неоднократно появится у выхода, названного Виктором, он может заключить, что весьма вероятно, что Пегги действительно знает секретное слово.
Одно замечание относительно сторонних наблюдателей: даже если Виктор носит скрытую камеру, которая записывает всю транзакцию, единственное, что камера запишет, это в одном случае, когда Виктор кричит «А!» и Пегги, появляющаяся в точке А, или, в другом случае, Виктор, кричащий «Б!» и Пегги появляется в B. Запись этого типа будет легко подделать любым двум людям (требуется только, чтобы Пегги и Виктор заранее договорились о последовательности букв A и B, которые Виктор будет кричать). Такая запись, конечно, никогда не будет убедительной ни для кого, кроме первоначальных участников. Фактически, даже человек, присутствовавший в качестве наблюдателя при первоначальном эксперименте, не был бы в этом убежден, поскольку Виктор и Пегги могли организовать весь «эксперимент» от начала до конца.
Кроме того, если Виктор выбирает свои А и Б, подбрасывая монету перед камерой, этот протокол теряет свойство нулевого разглашения; подбрасывание монеты на камеру, вероятно, будет убедительным для любого человека, который позже посмотрит запись. Таким образом, хотя это не раскрывает Виктору секретное слово, оно позволяет Виктору убедить мир в целом, что Пегги обладает этим знанием, что противоречит заявленным желаниям Пегги. Однако цифровая криптография обычно «подбрасывает монеты», полагаясь на генератор псевдослучайных чисел , который подобен монете с фиксированным набором орлов и решек, известным только владельцу монеты. Если бы монета Виктора вела себя таким образом, то Виктор и Пегги снова могли бы подделать эксперимент, поэтому использование генератора псевдослучайных чисел не раскрыло бы знания Пегги миру так же, как это сделало бы использование подброшенной монеты.
Обратите внимание, что Пегги могла доказать Виктору, что она знает волшебное слово, не раскрывая его ему, за одно испытание. Если Виктор и Пегги вместе пойдут ко входу в пещеру, Виктор сможет увидеть, как Пегги входит через А и выходит через Б. Это с уверенностью докажет, что Пегги знает волшебное слово, не раскрывая волшебное слово Виктору. Однако такое доказательство может быть замечено третьей стороной или записано Виктором, и такое доказательство будет убедительным для любого. Другими словами, Пегги не могла опровергнуть такое доказательство, заявив, что она вступила в сговор с Виктором, и поэтому она больше не контролирует, кто знает о ее знаниях.
Представьте, что ваш друг «Виктор» не различает красно-зеленый цвет (а вы — нет), и у вас есть два мяча: один красный и один зеленый, но в остальном идентичные. Виктору мячи кажутся совершенно одинаковыми. Виктор скептически относится к тому, что шары действительно различимы. Вы хотите доказать Виктору, что шарики на самом деле разного цвета , но не более того. В частности, вы не хотите раскрывать, какой шар красный, а какой зеленый.
Вот система доказательств. Вы даете два мяча Виктору, и он кладет их себе за спину. Далее он берет один из шаров, достает его из-за спины и показывает. Затем он снова кладет его за спину, а затем решает показать только один из двух шаров, выбирая один из двух наугад с равной вероятностью. Он спросит вас: «Я подменил мяч?» Вся эта процедура затем повторяется столько раз, сколько необходимо.
Глядя на цвета шаров, вы, конечно, можете с уверенностью сказать, поменял он их или нет. С другой стороны, если бы шары были одного цвета и, следовательно, неотличимы, вы не смогли бы угадать правильно с вероятностью выше 50%.
Поскольку вероятность того, что вам удалось случайным образом идентифицировать каждое переключение/непереключение, составляет 50%, вероятность случайного успеха во всех переключателях/непереключателях приближается к нулю («надежность»). Если вы и ваш друг повторите это «доказательство» несколько раз (например, 20 раз), ваш друг должен убедиться («полнота»), что шары действительно разного цвета.
Приведенное выше доказательство является доказательством с нулевым разглашением, поскольку ваш друг никогда не узнает, какой шар зеленый, а какой красный; действительно, он не получает никаких знаний о том, как различать шары. [8]
Одним из хорошо известных примеров доказательства с нулевым разглашением является пример «Где Уолдо». В этом примере проверяющий хочет доказать проверяющему, что он знает, где находится Уолдо на странице « Где Уолдо?» книгу, не раскрывая проверяющему свое местонахождение. [9]
Испытатель начинает с того, что берет большую черную доску с маленькой дырочкой размером с Уолдо. Доска в два раза больше книги в обоих направлениях, поэтому проверяющий не может видеть, где на странице ее размещает проверяющий. Затем проверяющий кладет доску на страницу так, чтобы Уолдо оказался в яме. [9]
Теперь проверяющий может заглянуть в дыру и увидеть Уолдо, но не сможет увидеть какую-либо другую часть страницы. Таким образом, проверяющий доказал проверяющему, что знает, где находится Уолдо, не раскрывая никакой другой информации о его местонахождении. [9]
Этот пример не является идеальным доказательством с нулевым разглашением, поскольку доказывающее устройство раскрывает некоторую информацию о местонахождении Уолдо, например положение его тела. Тем не менее, это достойная иллюстрация базовой концепции доказательства с нулевым разглашением.
Доказательство некоторого утверждения с нулевым разглашением должно удовлетворять трем свойствам:
Первые два из них являются свойствами более общих систем интерактивных доказательств . Третье — это то, что делает доказательство с нулевым разглашением. [10]
Доказательства с нулевым разглашением не являются доказательствами в математическом смысле этого термина, поскольку существует некоторая небольшая вероятность, ошибка обоснованности , того, что мошеннический доказывающий сможет убедить проверяющего в ложном утверждении. Другими словами, доказательства с нулевым разглашением являются вероятностными «доказательствами», а не детерминистическими доказательствами. Однако существуют методы уменьшения ошибки достоверности до пренебрежимо малых значений (например, правильное угадывание ста или тысячи двоичных решений имеет ошибку достоверности или соответственно . По мере увеличения количества бит ошибка достоверности уменьшается до нуля). .
Формальное определение нулевого знания должно использовать некоторую вычислительную модель, наиболее распространенной из которых является модель машины Тьюринга . Пусть P , V и S — машины Тьюринга. Интерактивная система доказательства для языка L является системой с нулевым разглашением, если для любого верификатора вероятностного полиномиального времени (PPT) существует симулятор PPT S такой, что:
где – запись взаимодействий между и . Доказывающее устройство P моделируется как имеющее неограниченную вычислительную мощность (на практике P обычно представляет собой вероятностную машину Тьюринга ). Интуитивно, определение гласит, что интерактивная система доказательства является системой с нулевым разглашением, если для любого верификатора существует эффективный симулятор S (в зависимости от ), который может воспроизвести диалог между P и на любом заданном входе. Вспомогательная строка z в определении играет роль «предварительного знания» (включая случайные монеты ). Определение подразумевает, что он не может использовать какую-либо строку предшествующих знаний z для извлечения информации из своего разговора с P , потому что, если S также получит эти предварительные знания, то он сможет воспроизвести разговор между и P так же, как и раньше. [ нужна цитата ]
Данное определение представляет собой определение идеального нулевого знания. Вычислительное нулевое разглашение достигается требованием, чтобы представления верификатора и симулятора были неотличимы только в вычислительном отношении с учетом вспомогательной строки. [ нужна цитата ]
Мы можем применить эти идеи к более реалистичному приложению криптографии. Пегги хочет доказать Виктору, что она знает дискретный лог заданного значения в данной группе . [11]
Например, имея значение , большое простое число и генератор , она хочет доказать, что ей известно такое значение, что , не раскрывая . Действительно, знание можно использовать в качестве доказательства личности, поскольку Пегги могла обладать такими знаниями, потому что она выбрала случайное значение , которое никому не раскрыла, вычислила и распределила значение среди всех потенциальных проверяющих, так что за один раз в более позднее время доказательство знания эквивалентно доказательству личности Пегги.
Протокол работает следующим образом: в каждом раунде Пегги генерирует случайное число , вычисляет и сообщает его Виктору. Получив , Виктор случайным образом отправляет один из следующих двух запросов: он либо просит Пегги раскрыть значение , либо значение .
Виктор может проверить любой ответ; если он запросил , он может затем вычислить и проверить соответствие . Если он запросил , он может проверить, что это соответствует этому, вычислив и проверив, что оно соответствует . Если Пегги действительно знает ценность , она сможет ответить на любой из возможных вызовов Виктора.
Если бы Пегги знала или могла догадаться, какой вызов собирается бросить Виктор, тогда она могла бы легко обмануть и убедить Виктора, что она знает, когда она этого не делает: если она знает, что Виктор собирается запросить , то она действует нормально: она выбирает , вычисляет и раскрывается Виктору; она сможет ответить на вызов Виктора. С другой стороны, если она знает, что Виктор запросит , тогда она выбирает случайное значение , вычисляет и сообщает Виктору значение, которое он ожидает. Когда Виктор предлагает ей раскрыть , она раскрывает , для чего Виктор проверит согласованность, поскольку он, в свою очередь, вычислит , что соответствует , поскольку Пегги умножила на модульную мультипликативную инверсию .
Однако если в любом из приведенных выше сценариев Виктор задаст задачу, отличную от той, которую он ожидал и для которой он произвел результат, то он не сможет ответить на вызов в предположении невозможности решения дискретного логарифма для эта группа. Если она выберет и раскроет , то она не сможет предоставить действительный документ , который пройдет проверку Виктора, поскольку она не знает . И если бы она выбрала значение , которое выдает себя за , то ей пришлось бы ответить дискретным логарифмом значения, которое она раскрыла – но Пегги не знает этого дискретного логарифма, поскольку раскрытое ею значение C было получено посредством арифметики с известными значениями, а не путем вычисления степени с известным показателем.
Таким образом, вероятность успешного мошенничества за один раунд составляет 0,5. Выполняя достаточно большое количество раундов, вероятность успеха доказывающего мошенничества можно сделать сколь угодно низкой.
Чтобы показать, что приведенное выше интерактивное доказательство не дает никаких знаний, кроме того факта, что Пегги знает значение , можно использовать аргументы, аналогичные тем, которые использовались в приведенном выше доказательстве полноты и достоверности. В частности, симулятор, скажем, Саймон, который не знает значения , может имитировать обмен между Пегги и Виктором с помощью следующей процедуры. Во-первых, Саймон случайным образом подбрасывает честную монету. Если результатом является «голова», он выбирает случайное значение , вычисляет и раскрывает его, как если бы это было сообщение от Пегги Виктору. Затем Саймон также выводит сообщение «запросить значение », как если бы оно было отправлено от Виктора к Пегги, и немедленно выводит значение, как если бы оно было отправлено от Пегги к Виктору. Один раунд завершен. С другой стороны, если результатом подбрасывания монеты является «хвост», Саймон выбирает случайное число , вычисляет и раскрывает его, как если бы это было сообщение от Пегги Виктору. Затем Саймон выводит «запросить значение », как будто это сообщение от Виктора Пегги. Наконец, Саймон выводит значение так, как будто это ответ Пегги Виктору. Один раунд завершен. По предыдущим доводам при доказательстве полноты и обоснованности интерактивное общение, смоделированное Саймоном, неотличимо от истинной переписки между Пегги и Виктором. Таким образом, свойство нулевого разглашения гарантируется.
Пегги доказывает, что знает значение x (например, свой пароль).
Это значение можно рассматривать как зашифрованное значение . Если действительно случайно, равномерно распределено между нулем и , это не приводит к утечке никакой информации (см. одноразовый блокнот ).
Следующая схема принадлежит Мануэлю Блюму . [12]
В этом сценарии Пегги знает гамильтонов цикл для большого графа G. Виктор знает G , но не цикл (например, Пегги сгенерировала G и открыла его ему). Считается, что найти гамильтонов цикл по большому графу вычислительно невозможно, поскольку известно, что соответствующая версия решения является NP-полной . Пегги докажет, что она знает цикл, не раскрывая его просто (возможно, Виктор заинтересован в его покупке, но хочет сначала проверить, или, может быть, Пегги - единственная, кто знает эту информацию и доказывает свою личность Виктору).
Чтобы показать, что Пегги знает этот гамильтонов цикл, они с Виктором играют несколько раундов игры:
Важно, чтобы привязка к графу была такой, чтобы во втором случае Виктор мог проверить, что цикл действительно состоит из ребер из H . Это можно сделать, например, зафиксировав каждое ребро (или его отсутствие) отдельно.
Если Пегги знает гамильтонов цикл в G , она может легко удовлетворить требование Виктора либо об изоморфизме графа, производящего H из G (который она взяла на себя на первом этапе), либо о гамильтоновом цикле в H (который она может построить, применив изоморфизм циклу в G ).
Ответы Пегги не раскрывают исходный гамильтонов цикл в G. В каждом раунде Виктор будет изучать только изоморфизм H и G или гамильтонов цикл в H. Ему понадобятся оба ответа для одного H , чтобы обнаружить цикл в G , поэтому информация остается неизвестной до тех пор, пока Пегги может генерировать отдельный H в каждом раунде. Если Пегги не знает о гамильтоновом цикле в G , но каким-то образом заранее знала, что Виктор будет просить увидеть в каждом раунде, то она могла бы смошенничать. Например, если бы Пегги заранее знала, что Виктор попросит показать гамильтонов цикл в H , то она могла бы сгенерировать гамильтонов цикл для несвязанного графа. Аналогично, если бы Пегги заранее знала, что Виктор попросит показать изоморфизм, она могла бы просто сгенерировать изоморфный граф H (в котором она также не знает гамильтонова цикла). Виктор мог бы смоделировать протокол самостоятельно (без Пегги), поскольку он знает, что он попросит показать. Следовательно, Виктор не получает никакой информации о гамильтоновом цикле в G из информации, полученной в каждом раунде.
Если Пегги не знает информации, она может угадать, какой вопрос задаст Виктор, и сгенерировать либо граф, изоморфный G , либо гамильтонов цикл для несвязанного графа, но, поскольку она не знает гамильтонов цикл для G, она не может сделать и то, и другое. С помощью этих догадок ее шанс обмануть Виктора равен 2 − n , где n — количество раундов. Для всех реалистичных целей таким способом невероятно сложно победить доказательство с нулевым разглашением за разумное количество раундов.
Различные варианты нулевого разглашения могут быть определены путем формализации интуитивного понятия о том, что подразумевается под выходными данными симулятора, «выглядящими как» выполнение реального протокола доказательства, следующими способами:
Исследования доказательств с нулевым разглашением были мотивированы системами аутентификации , в которых одна сторона хочет подтвердить свою личность второй стороне с помощью некоторой секретной информации (например, пароля), но не хочет, чтобы вторая сторона узнала что-либо об этом секрете. Это называется « доказательством знания с нулевым разглашением ». Однако пароль обычно слишком мал или недостаточно случайен, чтобы его можно было использовать во многих схемах доказательства знаний с нулевым разглашением. Доказательство пароля с нулевым разглашением — это особый вид доказательства с нулевым разглашением, который учитывает ограниченный размер паролей. [ нужна цитата ]
В апреле 2015 года был введен протокол «один из многих доказательств» ( протокол Sigma ). [14] В августе 2021 года Cloudflare , американская компания, занимающаяся веб-инфраструктурой и безопасностью, решила использовать механизм «один из многих доказательств» для частной веб-проверки с использованием оборудования поставщика. [15]
Одним из применений доказательств с нулевым разглашением в криптографических протоколах является обеспечение честного поведения при сохранении конфиденциальности. Грубо говоря, идея состоит в том, чтобы заставить пользователя доказать, используя доказательство с нулевым разглашением, что его поведение соответствует протоколу. [16] [17] Из-за обоснованности мы знаем, что пользователь должен действовать честно, чтобы иметь возможность предоставить действительные доказательства. Благодаря нулевому разглашению мы знаем, что пользователь не ставит под угрозу конфиденциальность своих секретов в процессе предоставления доказательств. [ нужна цитата ]
В 2016 году Принстонская лаборатория физики плазмы и Принстонский университет продемонстрировали метод, который может быть применим к будущим переговорам по ядерному разоружению . Это позволило бы инспекторам подтвердить, действительно ли объект является ядерным оружием, без регистрации, разглашения или раскрытия внутренней работы, которая может быть секретной. [18]
Доказательства с нулевым разглашением были применены в протоколах Zerocoin и Zerocash, кульминацией которых стало рождение Zcoin [19] (позже переименованного в Firo в 2020 году) [20] и криптовалют Zcash в 2016 году. Zerocoin имеет встроенную модель смешивания, которая не доверяйте никаким пирам или поставщикам централизованного микширования для обеспечения анонимности. [19] Пользователи могут совершать транзакции в базовой валюте и могут конвертировать валюту в Zerocoins и обратно. [21] Протокол Zerocash использует аналогичную модель (вариант, известный как неинтерактивное доказательство с нулевым разглашением ) [22] за исключением того, что он может скрывать сумму транзакции, в то время как Zerocoin не может этого сделать. Учитывая значительные ограничения данных транзакций в сети Zerocash, Zerocash менее подвержен атакам на конфиденциальность по сравнению с Zerocoin. Однако этот дополнительный уровень конфиденциальности может вызвать потенциально незамеченную гиперинфляцию предложения Zerocash, поскольку мошеннические монеты невозможно отследить. [19] [23]
В 2018 году были представлены Bulletproofs. Bulletproofs — это улучшение неинтерактивного доказательства с нулевым разглашением, когда надежная настройка не требуется. [24] Позже он был реализован в протоколе Mimblewimble (на котором основаны криптовалюты Grin и Beam) и криптовалюте Monero . [25] В 2019 году Фиро внедрила протокол Sigma, который является усовершенствованием протокола Zerocoin без доверенной настройки. [26] [14] В том же году Фиро представила протокол Lelantus, усовершенствованный вариант протокола Sigma, в котором первый скрывает происхождение и сумму транзакции. [27]
Доказательства с нулевым разглашением по своей природе могут повысить конфиденциальность в системах обмена идентификационными данными, которые уязвимы для утечки данных и кражи личных данных. При интеграции с децентрализованной системой идентификации ZKP добавляют дополнительный уровень шифрования в документы DID. [28]
Доказательства с нулевым разглашением были впервые предложены в 1985 году Шафи Голдвассером , Сильвио Микали и Чарльзом Ракоффом в их статье «Сложность знаний интерактивных систем доказательства». [16] В этой статье была представлена иерархия IP интерактивных систем доказательств ( см. интерактивную систему доказательств ) и задумана концепция сложности знаний , измерения объема знаний о доказательстве, передаваемых от доказывающего к проверяющему. Они также дали первое доказательство с нулевым разглашением для конкретной задачи — решения квадратичных невычетов по модулю m . Вместе с работой Ласло Бабая и Шломо Морана эта знаковая статья изобрела интерактивные системы доказательства, за которые все пять авторов получили первую премию Гёделя в 1993 году.
По их собственным словам, Гольдвассер, Микали и Ракофф говорят:
Особый интерес представляет случай, когда это дополнительное знание по существу равно 0, и мы показываем, что [можно] в интерактивном режиме доказать, что число является квадратичным без вычета по модулю m, высвобождая 0 дополнительных знаний. Это удивительно, поскольку не известен эффективный алгоритм определения квадратичной невязки по модулю m , если не задана факторизация m . Более того, все известные NP- доказательства этой задачи демонстрируют простую факторизацию m . Это указывает на то, что добавление взаимодействия к процессу доказательства может уменьшить объем знаний, которые необходимо передать для доказательства теоремы.
Квадратичная задача без вычета имеет как NP , так и алгоритм co-NP , и поэтому находится на пересечении NP и co-NP . Это также относится и к нескольким другим задачам, для которых впоследствии были обнаружены доказательства с нулевым разглашением, например, к неопубликованной системе доказательств Одеда Гольдрейха, проверяющей, что модуль с двумя простыми числами не является целым числом Блюма . [29]
Одед Гольдрайх , Сильвио Микали и Ави Вигдерсон пошли еще дальше, показав, что, предполагая существование невзламываемого шифрования, можно создать систему доказательства с нулевым разглашением для NP-полной задачи раскраски графа тремя цветами. Поскольку любую проблему в NP можно эффективно свести к этой задаче, это означает, что при этом предположении все проблемы в NP имеют доказательства с нулевым разглашением. [30] Причиной предположения является то, что, как и в приведенном выше примере, их протоколы требуют шифрования. Обычно упоминаемым достаточным условием существования невзламываемого шифрования является существование односторонних функций , но вполне возможно, что этого можно достичь и с помощью некоторых физических средств.
Помимо этого, они также показали, что проблема неизоморфизма графов , дополнение к проблеме изоморфизма графов , имеет доказательство с нулевым разглашением. Эта проблема находится в co-NP , но в настоящее время неизвестно, существует ли она ни в NP , ни в каком-либо практическом классе. В более общем плане Рассел Импальяццо и Моти Юнг, а также Бен-Ор и др. продолжил бы показывать, что, также предполагая односторонние функции или невзламываемое шифрование, существуют доказательства с нулевым разглашением для всех проблем в IP = PSPACE , или, другими словами, все, что может быть доказано с помощью интерактивной системы доказательств, может быть доказано с нулевым знанием. [31] [32]
Не желая делать ненужные предположения, многие теоретики искали способ устранить необходимость односторонних функций . Одним из способов, которым это было сделано, были интерактивные системы доказательств с несколькими доказывающими (см. Интерактивная система доказательств ), в которых есть несколько независимых доказывающих вместо одного, что позволяет проверяющему «перекрестно допрашивать» доказывающих изолированно, чтобы избежать введения в заблуждение. Можно показать, что без каких-либо предположений о неразрешимости все языки в NP имеют доказательства с нулевым разглашением в такой системе. [33]
Оказывается, в условиях Интернета, где несколько протоколов могут выполняться одновременно, построение доказательств с нулевым разглашением является более сложной задачей. Направление исследований по изучению параллельных доказательств с нулевым разглашением было инициировано работами Дворка , Наора и Сахаи . [34] Одним из конкретных достижений в этом направлении стала разработка протоколов доказательств, неотличимых от свидетелей . Свойство неотличимости свидетеля связано со свойством нулевого разглашения, однако протоколы, неотличимые от свидетеля, не страдают от тех же проблем одновременного выполнения. [35]
Другим вариантом доказательств с нулевым разглашением являются неинтерактивные доказательства с нулевым разглашением . Блюм, Фельдман и Микали показали, что общей случайной строки, разделяемой между доказывающим и проверяющим, достаточно для достижения вычислительного нулевого знания без необходимости взаимодействия. [5] [6]
Наиболее популярные интерактивные или неинтерактивные протоколы доказательства с нулевым разглашением (например, zk-SNARK) можно разделить на следующие четыре категории: краткие неинтерактивные аргументы знаний (SNARK), масштабируемые прозрачные аргументы знаний (STARK), Проверяемое полиномиальное делегирование (VPD) и краткие неинтерактивные аргументы (SNARG). Ниже представлен список протоколов и библиотек доказательства с нулевым разглашением вместе со сравнением, основанным на прозрачности , универсальности , правдоподобной постквантовой безопасности и парадигме программирования . [36] Прозрачный протокол — это протокол, который не требует какой-либо доверенной настройки и использует публичную случайность. Универсальный протокол — это протокол, который не требует отдельной доверенной настройки для каждого канала. Наконец, правдоподобным постквантовым протоколом является тот, который не подвержен известным атакам с использованием квантовых алгоритмов.
{{cite book}}
: CS1 maint: location missing publisher (link){{cite book}}
: CS1 maint: location missing publisher (link)