Неинтерактивное доказательство с нулевым разглашением
Криптографический примитив

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

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

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

История

Blum , Feldman и Micali [2] показали в 1988 году, что общая ссылочная строка, разделяемая доказывающим и проверяющим, достаточна для достижения вычислительного нулевого разглашения без необходимости взаимодействия. Goldreich и Oren [3] дали результаты невозможности [ необходимо разъяснение ] для одноразовых протоколов нулевого разглашения в стандартной модели . В 2003 году Shafi Goldwasser и Yael Tauman Kalai опубликовали пример схемы идентификации, для которой любая хэш-функция даст небезопасную схему цифровой подписи. [4]

Модель влияет на свойства, которые могут быть получены из протокола с нулевым разглашением. Пасс [5] показал, что в модели общей справочной строки неинтерактивные протоколы с нулевым разглашением не сохраняют все свойства интерактивных протоколов с нулевым разглашением; например, они не сохраняют отрицаемость. Неинтерактивные доказательства с нулевым разглашением также могут быть получены в модели случайного оракула с использованием эвристики Фиата–Шамира . [ необходима цитата ]

Блокчейн-приложения

Сравнение наиболее широко используемых систем доказательства [ необходима ссылка ]

В 2012 году Алессандро Кьеза и др. разработали протокол zk-SNARK, аббревиатуру от zero-knowledge succinct non-interactive argument of knowledge ( краткий неинтерактивный аргумент с нулевым разглашением) . [6] Первое широко распространенное применение zk-SNARK было в протоколе блокчейна Zerocash , где криптография с нулевым разглашением обеспечивает вычислительную основу, облегчая математические доказательства того, что одна сторона владеет определенной информацией, не раскрывая, что это за информация. [7] Zcash использовал zk-SNARK для упрощения четырех различных типов транзакций: частная, экранирующая, деэкранирующая и публичная. Этот протокол позволял пользователям определять, какой объем данных был передан публичному реестру для каждой транзакции. [8] Ethereum zk-Rollups также используют zk-SNARK для повышения масштабируемости. [9]

В 2017 году был выпущен Bulletproofs [10] , который позволяет доказать, что зафиксированное значение находится в диапазоне, используя логарифмическое (в битовой длине диапазона) число элементов поля и группы. [11] Позже Bulletproofs был реализован в протоколе Mimblewimble (основа для Grin и Beam, а также Litecoin через блоки расширения) и криптовалюте Monero . [12]

В 2018 году протокол zk-STARK ( zero-knowledge Scalable Transparent Argument of Knowledge ) [13] был представлен Эли Бен-Сассоном, Иддо Бентовым, Йиноном Хорешем и Майклом Рябзевым [14] , предлагающим прозрачность (отсутствие доверенной настройки), квазилинейное время доказательства и полилогарифмическое время проверки. Zero-Knowledge Succinct Transparent Arguments of Knowledge — это тип криптографической системы доказательств, которая позволяет одной стороне (доказывающей) доказать другой стороне (проверяющей), что определенное утверждение истинно, не раскрывая никакой дополнительной информации, выходящей за рамки истинности самого утверждения. zk-STARKs лаконичны, что означает, что они позволяют создавать короткие доказательства, которые легко проверить, и они прозрачны, что означает, что любой может проверить доказательство, не нуждаясь в какой-либо секретной информации. [14]

В отличие от первого поколения zk-SNARK, zk-STARK по умолчанию не требуют доверенной настройки, что делает их особенно полезными для децентрализованных приложений, таких как блокчейны. Кроме того, zk-STARK можно использовать для проверки многих утверждений одновременно, что делает их масштабируемыми и эффективными. [1]

В 2019 году были представлены рекурсивные zk-SNARK HALO без доверенной настройки. [15] Pickles [16] zk-SNARK, основанные на предыдущей конструкции, обеспечивают работу Mina, первого кратко проверяемого блокчейна. [17]

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

Неинтерактивные системы доказательства с нулевым разглашением
система ЗКПГод публикацииПротоколПрозрачныйУниверсальныйВероятно, постквантовая безопасность
Пиноккио [18]2013zk-SNARKНетНетНет
Джеппетто [19]2015zk-SNARKНетНетНет
TinyRAM [20]2013zk-SNARKНетНетНет
Шведский стол [21]2015zk-SNARKНетНетНет
виртуальная оперативная память [22]2018zk-SNARGНетДаНет
vnTinyRAM [23]2014zk-SNARKНетДаНет
МИРАЖ [24]2020zk-SNARKНетДаНет
Соник [25]2019zk-SNARKНетДаНет
Марлин [26]2020zk-SNARKНетДаНет
ПЛОНК [27]2019zk-SNARKНетДаНет
Сверхзвуковой [28]2020zk-SNARKДаДаНет
Пуленепробиваемые [29]2018ПуленепробиваемыеДаДаНет
Даман [30]2018zk-SNARKДаДаНет
Гало [15]2019zk-SNARKДаДаНет
Дева [31]2020zk-SNARKДаДаДа
Лигеро [32]2017zk-SNARKДаДаДа
Аврора [33]2019zk-SNARKДаДаДа
zk-STARK [14] [34]2019zk-STARKДаДаДа
Пшик [35] [36]2021zk-STARKДаДаДа

Определение

Первоначально [2] неинтерактивное нулевое разглашение было определено только как единая система доказательства теоремы. В такой системе каждое доказательство требует своей собственной новой общей справочной строки. Общая справочная строка в общем случае не является случайной строкой. Она может, например, состоять из случайно выбранных групповых элементов, которые используют все стороны протокола. Хотя групповые элементы являются случайными, справочная строка не является таковой, поскольку она содержит определенную структуру (например, групповые элементы), которая отличается от случайности. Впоследствии Фейге, Лапидот и Шамир [37] ввели доказательства с нулевым разглашением для нескольких теорем как более универсальное понятие для неинтерактивных доказательств с нулевым разглашением.

Неинтерактивные доказательства на основе парного сопоставления

Криптография на основе пар привела к нескольким криптографическим достижениям. Одним из таких достижений являются более мощные и более эффективные неинтерактивные доказательства с нулевым разглашением. Основополагающая идея заключалась в том, чтобы скрыть значения для оценки пар в обязательстве . Используя различные схемы обязательств, эта идея была использована для построения систем доказательств с нулевым разглашением при скрытии подгруппы [38] и при линейном предположении принятия решений . [39] Эти системы доказательств доказывают выполнимость схемы и, таким образом, по теореме Кука–Левина позволяют доказать принадлежность для каждого языка к NP. Размер общей ссылочной строки и доказательств относительно невелик; однако преобразование утверждения в булеву схему влечет за собой значительные накладные расходы.

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

При сильных предположениях о знаниях известно, как создавать вычислительно-надежные системы доказательств сублинейной длины для NP-полных языков. Точнее, доказательство в таких системах доказательств состоит только из небольшого числа билинейных групповых элементов. [41] [42]

Ссылки

  1. ^ abc Gong, Yinjie; Jin, Yifei; Li, Yuchan; Liu, Ziyi; Zhu, Zhiyi (январь 2022 г.). «Анализ и сравнение основной схемы доказательства с нулевым разглашением». Международная конференция по большим данным, информации и компьютерным сетям (BDICN) 2022 г. стр.  366–372 . doi :10.1109/BDICN55575.2022.00074. ISBN 978-1-6654-8476-3. S2CID  248267862.
  2. ^ ab Мануэль Блюм, Пол Фельдман и Сильвио Микали. Неинтерактивное нулевое знание и его применение. Труды двадцатого ежегодного симпозиума ACM по теории вычислений (STOC 1988). 103–112. 1988
  3. ^ Одед Голдрайх и Яир Орен. Определения и свойства систем с нулевым разглашением. Журнал криптологии. Том 7(1). 1–32. 1994 (PS)
  4. ^ Шафи Голдвассер и Яэль Калай. О (не)безопасности парадигмы Фиата–Шамира. Труды 44-го ежегодного симпозиума IEEE по основам компьютерной науки (FOCS'03). 2003
  5. ^ Рафаэль Пасс. Об отрицании в общей справочной строке и модели случайного оракула. ​​Достижения в криптологии – CRYPTO 2003. 316–337. 2003 (PS)
  6. ^ Bitansky, Nir; Canetti, Ran; Chiesa, Alessandro; Tromer, Eran (январь 2012 г.). «От извлекаемой устойчивости к столкновениям к кратким неинтерактивным аргументам знания и обратно». Труды 3-й конференции по инновациям в теоретической информатике на ITCS '12 . ACM . С.  326–349 . doi :10.1145/2090236.2090263. ISBN 978-1-4503-1115-1. S2CID  2576177.
  7. ^ Бен-Сассон, Эли; Кьеза, Алессандро; Гарман, Кристина; Грин, Мэтью; Майерс, Ян; Тромер, Эран; Вирза, Мадарс (18 мая 2014 г.). "Zerocash: децентрализованные анонимные платежи из биткойнов" (PDF) . IEEE . Получено 26 января 2016 г. .
  8. ^ Бен-Сассон, Эли; Кьеза, Алессандро. «Что такое зк-СНАРК?». з.кэш . Проверено 3 ноября 2022 г.
  9. ^ "Zero-Knowledge Rollups". ethereum.org . Получено 2023-02-25 .
  10. ^ Бюнц, Бенедикт; Бутл, Джонатан; Бонех, Дэн; Поэлстра, Эндрю; Вюйле, Питер; Максвелл, Грег (май 2018 г.). «Пуленепробиваемые материалы: краткие доказательства для конфиденциальных транзакций и не только». Симпозиум IEEE 2018 г. по безопасности и конфиденциальности (SP) . стр.  315–334 . doi :10.1109/SP.2018.00020. ISBN 978-1-5386-4353-2. S2CID  3337741.
  11. ^ Бюнц, Бенедикт; Бутл, Джонатан; Бонех, Дэн; Поэлстра, Эндрю; Вюйле, Питер; Максвелл, Грег (май 2018 г.). «Пуленепробиваемые материалы: краткие доказательства для конфиденциальных транзакций и не только» (PDF) . Симпозиум IEEE 2018 г. по безопасности и конфиденциальности (SP) . стр.  315–334 . doi :10.1109/SP.2018.00020. ISBN 978-1-5386-4353-2. S2CID  3337741 . Получено 2 декабря 2022 г. .
  12. ^ Одендал, Ханси; Шаррок, Кейл; Хеерден, SW. «Пуленепробиваемые покрытия и мимблвимбл». Университет Тари Лабс. Архивировано из оригинала 29 сентября 2020 г. Получено 3 декабря 2020 г.
  13. ^ http://www.cs.technion.ac.il/RESEARCH_DAY_17/POSTERS/michael_riabzev.pdf
  14. ^ abc Эли Бен-Сассон; Иддо Бентов; Йинон Хореш; Майкл Рябцев (6 марта 2018 г.). «Масштабируемая, прозрачная и постквантовая безопасная вычислительная целостность» (PDF) . Международная ассоциация криптологических исследований . Получено 24 октября 2021 г. .
  15. ^ ab Боуи, Шон; Григг, Джек; Хопвуд, Дайра (2019). «Рекурсивная композиция доказательств без доверенной настройки». Архив Cryptology ePrint .
  16. ^ "Meet Pickles SNARK: Включение смарт-контрактов в протоколе Coda". Протокол Mina . Получено 25.02.2023 .
  17. ^ Бонно, Джозеф; Меклер, Айзек; Рао, В.; Эван; Шапиро (2021). «Mina: децентрализованная криптовалюта в масштабе» (PDF) . S2CID  226280610.
  18. ^ Парно, Брайан; Хауэлл, Джон; Джентри, Крейг; Райкова, Мариана (май 2013 г.). «Пиноккио: почти практически проверяемые вычисления». Симпозиум IEEE по безопасности и конфиденциальности 2013 г. , стр.  238–252 . doi :10.1109/SP.2013.47. ISBN 978-0-7695-4977-4. S2CID  1155080.
  19. ^ Костелло, Крейг; Фурне, Седрик; Хауэлл, Джон; Кольвайс, Маркульф; Кройтер, Бенджамин; Наериг, Майкл; Парно, Брайан; Захур, Сами (май 2015 г.). «Geppetto: Versatile Verifiable Computation». Симпозиум IEEE 2015 г. по безопасности и конфиденциальности . стр.  253–270 . doi :10.1109/SP.2015.23. ISBN 978-1-4673-6949-7. S2CID  3343426.
  20. ^ Бен-Сассон, Эли; Кьеза, Алессандро; Генкин, Даниэль; Тромер, Эран; Вирза, Мадарс (2013). «SNARKs для C: Проверка выполнения программ кратко и с нулевым знанием». В Canetti, Ran; Garay, Juan A. (ред.). Достижения в криптологии – CRYPTO 2013. Конспект лекций по информатике. Том 8043. Берлин, Гейдельберг: Springer. С.  90– 108. doi :10.1007/978-3-642-40084-1_6. ISBN 978-3-642-40084-1.
  21. ^ Wahby, Riad S.; Setty, Srinath; Ren, Zuocheng; Blumberg, Andrew J.; Walfish, Michael (2015). Эффективная оперативная память и поток управления в проверяемых аутсорсинговых вычислениях. doi :10.14722/ndss.2015.23097. ISBN 978-1-891562-38-9. Получено 25.02.2023 .
  22. ^ Чжан, Юпэн; Генкин, Даниэль; Кац, Джонатан; Пападопулос, Димитриос; Папаманту, Харалампос (май 2018 г.). «VRAM: более быстрая проверяемая оперативная память с программно-независимой предварительной обработкой». Симпозиум IEEE 2018 г. по безопасности и конфиденциальности (SP) . стр.  908–925 . doi :10.1109/SP.2018.00013. ISBN 978-1-5386-4353-2. S2CID  41548742.
  23. ^ Бен-Сассон, Эли; Кьеза, Алессандро; Тромер, Эран; Вирза, Мадарс (2014). Краткий {неинтерактивный} нулевой уровень знаний для архитектуры фон Неймана. стр.  781–796 . ISBN. 978-1-931971-15-7.
  24. ^ Косба, Ахмед; Пападопулос, Димитриос; Папаманту, Харалампос; Сонг, Дон (2020). «МИРАЖ: краткие аргументы в пользу рандомизированных алгоритмов с приложениями к универсальным zk-SNARK». Архив Cryptology ePrint .
  25. ^ Маллер, Мэри; Боу, Шон; Кольвайс, Маркульф; Мейкледжон, Сара (2019-11-06). "Sonic". Труды конференции ACM SIGSAC 2019 года по компьютерной и коммуникационной безопасности. CCS '19. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр.  2111– 2128. doi :10.1145/3319535.3339817. ISBN 978-1-4503-6747-9. S2CID  60442921.
  26. ^ Кьеза, Алессандро; Ху, Юньконг; Маллер, Мэри; Мишра, Пратюш; Веселы, Ноа; Уорд, Николас (2020). «Марлин: предварительная обработка zkSNARK с универсальной и обновляемой SRS». В Canteaut, Энн; Ишай, Ювал (ред.). Достижения в криптологии – EUROCRYPT 2020. Конспект лекций по информатике. Том 12105. Cham: Springer International Publishing. стр.  738– 768. doi : 10.1007/978-3-030-45721-1_26. ISBN 978-3-030-45721-1. S2CID  204772154.
  27. ^ Габизон, Ариэль; Уильямсон, Закари Дж.; Чиоботару, Оана (2019). "PLONK: Перестановки по базисам Лагранжа для вселенских неинтерактивных аргументов знания". Архив Cryptology ePrint .
  28. ^ Бюнц, Бенедикт; Фиш, Бен; Шепиенец, Алан (2020). «Прозрачные SNARKs из компиляторов DARK». В Канто, Энн; Ишай, Ювал (ред.). Достижения в криптологии – EUROCRYPT 2020. Конспект лекций по информатике. Том 12105. Cham: Springer International Publishing. стр.  677– 706. doi : 10.1007/978-3-030-45721-1_24. ISBN 978-3-030-45721-1. S2CID  204892714.
  29. ^ Бюнц, Бенедикт; Бутл, Джонатан; Бонех, Дэн; Поэлстра, Эндрю; Вюйле, Питер; Максвелл, Грег (май 2018 г.). «Пуленепробиваемые материалы: краткие доказательства для конфиденциальных транзакций и не только». Симпозиум IEEE 2018 г. по безопасности и конфиденциальности (SP) . стр.  315–334 . doi :10.1109/SP.2018.00020. ISBN 978-1-5386-4353-2. S2CID  3337741.
  30. ^ Wahby, Riad S.; Tzialla, Ioanna; Shelat, Abhi; Thaler, Justin; Walfish, Michael (май 2018 г.). «Двойная эффективность zkSNARKs без доверенной настройки». Симпозиум IEEE 2018 г. по безопасности и конфиденциальности (SP) . стр.  926–943 . doi :10.1109/SP.2018.00060. ISBN 978-1-5386-4353-2. S2CID  549873.
  31. ^ Чжан, Цзяхэн; Сье, Тяньчэн; Чжан, Юпэн; Сонг, Дон (май 2020 г.). «Прозрачное полиномиальное делегирование и его применение к доказательству с нулевым разглашением». Симпозиум IEEE 2020 г. по безопасности и конфиденциальности (SP) . стр.  859–876 . doi :10.1109/SP40000.2020.00052. ISBN 978-1-7281-3497-0. S2CID  209467198.
  32. ^ Эймс, Скотт; Хазай, Кармит; Ишай, Ювал; Венкитасубраманиам, Мутурамакришнан (2017-10-30). "Ligero". Труды конференции ACM SIGSAC 2017 года по компьютерной и коммуникационной безопасности . CCS '17. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр.  2087–2104 . doi :10.1145/3133956.3134104. ISBN 978-1-4503-4946-8. S2CID  5348527.
  33. ^ Бен-Сассон, Эли; Кьеза, Алессандро; Рябцев, Майкл; Спунер, Николас; Вирза, Мадарс; Уорд, Николас П. (2019). «Aurora: прозрачные краткие аргументы в пользу R1CS». В Ishai, Ювал; Rijmen, Винсент (ред.). Достижения в криптологии – EUROCRYPT 2019. Конспект лекций по информатике. Том 11476. Cham: Springer International Publishing. стр.  103–128 . doi :10.1007/978-3-030-17653-2_4. ISBN 978-3-030-17653-2. S2CID  52832327.
  34. ^ Бен-Сассон, Эли; Бентов, Иддо; Хореш, Йинон; Рябцев, Майкл (2019). «Масштабируемое нулевое знание без доверенной настройки». В Болдырева, Александра; Мичианчо, Даниэле (ред.). Достижения в криптологии – CRYPTO 2019. Конспект лекций по информатике. Том 11694. Cham: Springer International Publishing. стр.  701– 732. doi :10.1007/978-3-030-26954-8_23. ISBN 978-3-030-26954-8. S2CID  199501907.
  35. ^ Computing, Trustworthy (2021-08-30). "Прозрачные доказательства с нулевым разглашением с нулем". Medium . Получено 2023-02-25 .
  36. ^ Mouris, Dimitris; Tsoutsos, Nektarios Georgios (2021). «Zilch: A Framework for Deploying Transparent Zero-Knowledge Proofs». IEEE Transactions on Information Forensics and Security . 16 : 3269– 3284. doi : 10.1109/TIFS.2021.3074869. ISSN  1556-6021. S2CID  222069813.
  37. ^ Уриэль Фейге, Дрор Лапидот, Ади Шамир: Множественные неинтерактивные доказательства с нулевым разглашением при общих предположениях. SIAM J. Comput. 29(1): 1–28 (1999)
  38. ^ Йенс Грот, Рафаил Островский, Амит Сахаи: Идеальное неинтерактивное нулевое знание для NP. EUROCRYPT 2006: 339–358
  39. ^ Йенс Грот, Рафаил Островский, Амит Сахаи: Неинтерактивные Zaps и новые методы для NIZK. CRYPTO 2006: 97–111
  40. ^ Йенс Грот, Амит Сахаи: Эффективные неинтерактивные системы доказательств для билинейных групп. EUROCRYPT 2008: 415–432
  41. ^ Йенс Грот. Короткие парные неинтерактивные аргументы с нулевым знанием. ASIACRYPT 2010: 321–340
  42. ^ Хельгер Липмаа. Множества без прогрессии и неинтерактивные аргументы с нулевым знанием, основанные на сублинейном парном строении. TCC 2012: 169–189
Взято с "https://en.wikipedia.org/w/index.php?title=Неинтерактивное_доказательство_нулевого_знания&oldid=1259071783#История"