Пересечение доказательств с нулевым разглашением и проверяемых вычислений
10 января 2024 г.:::информация Этот документ доступен на arxiv по лицензии CC 4.0.
Авторы:
(1) Тарик Бонтекое, Гронингенский университет;
(2) Димка Карастоянова, Гронингенский университет;
(3) Фатих Туркмен, Гронингенский университет.
:::
Таблица ссылок
Доказательства с нулевым разглашением и проверяемые вычисления
Вычисления, обеспечивающие конфиденциальность
Требования: точка зрения приложения
Проверяемые вычисления с сохранением конфиденциальности
Открытые проблемы и будущие направления
3. Доказательства с нулевым разглашением и проверяемые вычисления
Доказательство с нулевым разглашением позволяет сторонам доказать правильность определенного утверждения (т. е. утверждения), скрывая при этом всю связанную с ним личную информацию [17]. Это полезно в случаях, когда правильность утверждения не очевидна, но доказывающий располагает частной информацией, достаточной для доказательства правильности.
Примеры вариантов использования ZKP включают подтверждение совершеннолетия без раскрытия информации, связанной с данными о рождении, доказательство того, что у человека есть доступ к зданию без раскрытия личности, или доказательство знания прообраза хеш-значения.
3.1. Терминология
Мы следуем терминологии, определенной в [18], и используем доказательство совершеннолетия в качестве рабочего примера:
• Экземпляр: входные данные, которые общеизвестны (часто общедоступная информация) как для доказывающего, так и для проверяющего, и используются для определения утверждения, которое необходимо доказать. Обычно обозначается как х. (Пример: защищенный от несанкционированного доступа идентификационный чип.)
• Свидетель: данные, известные только тому, кто доказывает. Обычно обозначается как w. (Пример: дата рождения и идентификационные данные.)
• Отношение: условие, определяющее достоверность пары экземпляр-свидетель. Обозначается как R. (Пример: дата рождения на идентификационном чипе не менее 18 лет назад.)
• Язык: множество всех экземпляров x, для которых существует действительный свидетель w относительно R: {x : ∃w : (x, w) ∈ R}. Обозначается как L. (Пример: все ID-чипы с датой рождения не менее 18 лет назад.)
• Утверждение: утверждает, что экземпляр x принадлежит языку L: x ∈ L. В качестве альтернативы, ∃w : (x, w) ∈ R. (Пример: я взрослый человек.) Отметим, что некоторые авторы используют термины «экземпляр » и «заявление» взаимозаменяемы.
Система ZKP должна удовлетворять как минимум следующим (неформальным) требованиям:
• Полнота: честный доказывающий должен быть в состоянии убедить проверяющего в достоверности любого истинного утверждения.
• Звук: Доказывающий не должен быть в состоянии убедить проверяющего в достоверности ложного утверждения.
• Нулевое разглашение: при истинном утверждении протокол не должен раскрывать никакой другой информации, кроме достоверности утверждения, проверяющему, при условии, что доказывающее следует протоколу. В частности, не допускается утечка информации о свидетеле.
Выходные данные протокола ZKP могут быть либо доказательством, либо аргументом. Там, где доказательство должно быть обоснованным против любого доказывающего, неограниченного в вычислительном отношении, аргумент должен быть обоснованным только против доказывающих, ограниченных в вычислительном отношении. В большинстве литературы термин «доказательство» используется для обозначения как доказательств, так и аргументов. Мы следуем этому соглашению.
В зависимости от типа претензии и типа обоснованности схемы мы различаем два типа схемы ZKP:
• Доказательство членства с нулевым разглашением доказывает только то, что утверждение x ∈ L истинно, т. е. что существует свидетель w такой, что экземпляр x является частью L.
• Доказательство знания с нулевым разглашением (ZKPoK) не только доказывает, что существует такой свидетель w, но также и то, что доказывающее знает w.
Любое доказательство знания с нулевым разглашением (ZKPoK) должно удовлетворять более строгому понятию достоверности, известному как достоверность знания: доказывающий, который не знает свидетеля утверждения, не должен быть в состоянии убедить проверяющего в том, что он знает действительного свидетеля для этого утверждения. . Следуя общепринятому соглашению, мы будем использовать ZKP для обозначения ZKPoK и при необходимости уточнять.
3.2. Конкретные схемы НИЗК
Изначально большинство схем ZKP представляли собой решения конкретных задач, в основном в виде Σ-протоколов, например, протокола Шнорра [19]. Недостатком этих схем является то, что они не обеспечивают решения для общих вычислений, а время проверки и размер доказательства линейно (или хуже) масштабируются в зависимости от размера вычислений.
Более того, они интерактивны и требуют честного проверяющего. Положительным моментом является то, что эти схемы можно сделать неинтерактивными с помощью эвристики Фиата-Шамира (FS) [20], подразумевающей публичную проверку и безопасность от злонамеренных проверяющих. Из-за недостатков интерактивных ZKP мы сосредоточим внимание на неинтерактивных доказательствах с нулевым разглашением (NIZK).
Схема NIZK обычно описывается тремя (вероятностными) алгоритмами с полиномиальным временем (Setup, Prove, Verify). В целом эти алгоритмы определяются и используются следующим образом:
• Настройка(1κ,params) → (ppR,ppP,ppV,aux): принимает в качестве входных данных параметр безопасности κ и дополнительные входные параметры, специфичные для схемы. Он создает общедоступные параметры для проверяющего ppP и проверяющего ppV. В случае, если настройка зависит от входного отношения R, мы помещаем соответствующие параметры в ppR. Дополнительные параметры настройки возвращаются в aux;
• Prove(ppP , x, w) → π: Доказывающая программа принимает на вход параметры доказательства ppP и пару экземпляр-свидетель (x, w) ∈ R и возвращает доказательство π;
• Verify(ppV , x, π)- > {0, 1}: алгоритм проверки принимает на вход параметры проверки ppV , экземпляр x и доказательство π и возвращает 0 (отклонить) или 1 (принять).
Внедрение Буратино [21] в качестве первого краткого ZKP или краткого неинтерактивного аргумента знания с нулевым разглашением (zk-SNARK) дало первую схему без ранее упомянутых недостатков. Более того, он также позволял проверять любые вычисления, которые можно описать как арифметическую схему, то есть поддерживает проверяемые вычисления. За Пиноккио последовало множество схем с меньшим временем доказательства или проверки и меньшими размерами доказательств. Groth16 [22], Marlin [23] и PLONK [24] являются примерами популярных схем с общедоступными реализациями.
Другая линейка эффективных НИЗК началась с появления Bulletproofs [25]. Совсем недавно эффективная конструкция, используемая для Bulletproofs, была применена для создания Σ-пули [26] или теории сжатого Σ-протокола [27]. Эти последние протоколы могут использоваться для построения доказательств с нулевым разглашением для арифметических схем на основе стандартных предположений безопасности, чего нельзя сказать о zk-SNARK, за счет увеличения размера доказательства и времени проверки.
Для более обширного и актуального обзора схем ZKP мы отсылаем читателя, например, к [28], [29].
Оригинал