Неинтерактивное доказательство с нулевым разглашением
Неинтерактивные доказательства с нулевым разглашением представляют собой криптографические примитивы , в которых информация между доказывающим и проверяющим может быть подтверждена доказывающим без раскрытия какой-либо конкретной информации, выходящей за рамки действительности самого утверждения. Это делает ненужным прямое общение между проверяющим и проверяющим, эффективно устраняя любых посредников.
Ключевое преимущество неинтерактивных доказательств с нулевым разглашением заключается в том, что их можно использовать в ситуациях, когда нет возможности взаимодействия между доказывающим и проверяющим, например, в онлайн-транзакциях, когда две стороны не могут общаться в реальном времени. Это делает неинтерактивные доказательства с нулевым разглашением особенно полезными в децентрализованных системах, таких как блокчейны , где транзакции проверяются сетью узлов и нет центрального органа для наблюдения за процессом проверки. [1]
Большинство неинтерактивных доказательств с нулевым разглашением основаны на математических конструкциях, таких как криптография на основе эллиптических кривых или криптография на основе пар , которые позволяют создавать короткие и легко проверяемые доказательства истинности утверждения. В отличие от интерактивных доказательств с нулевым разглашением, которые требуют нескольких раундов взаимодействия между доказывающим и проверяющим, неинтерактивные доказательства с нулевым разглашением разработаны так, чтобы быть эффективными и могут использоваться для одновременной проверки большого количества утверждений. [1]
История
[ редактировать ]![]() | Этот раздел нуждается в дополнении: история того, как доказательства с нулевым разглашением используются в реальных приложениях и приложениях и для каких целей. Вы можете помочь, добавив к нему . ( октябрь 2020 г. ) |
Блюм , Фельдман и Микали [2] показал в 1988 году, что общей ссылочной строки, разделяемой между доказывающим и проверяющим, достаточно для достижения вычислительного нулевого знания без необходимости взаимодействия. Гольдрейх и Орен [3] дал невозможные результаты [ нужны разъяснения ] для одноразовых протоколов с нулевым разглашением в стандартной модели . В 2003 году Шафи Гольдвассер и Яэль Тауман Калаи опубликовали пример схемы идентификации, для которой любая хеш-функция приведет к небезопасной схеме цифровой подписи. [4]
Модель влияет на свойства, которые можно получить из протокола с нулевым разглашением. Проходить [5] показал, что в модели общей эталонной строки неинтерактивные протоколы с нулевым разглашением не сохраняют все свойства интерактивных протоколов с нулевым разглашением; например, они не сохраняют возможность отрицания. Неинтерактивные доказательства с нулевым разглашением также могут быть получены в модели случайного оракула с использованием эвристики Фиата – Шамира . [ нужна ссылка ]
Блокчейн-приложения
[ редактировать ]
В 2012 году Алессандро Кьеза и др. разработали протокол zk-SNARK, аббревиатуру от с нулевым краткого неинтерактивного аргумента знания разглашением . [6] Первое широкое применение zk-SNARK было в Zerocash протоколе блокчейна , где криптография с нулевым разглашением обеспечивает вычислительную основу, облегчая математические доказательства того, что одна сторона владеет определенной информацией, не раскрывая, что это за информация. [7] Zcash использовал zk-SNARK для осуществления четырех различных типов транзакций: частных, экранирующих, деэкранирующих и публичных. Этот протокол позволял пользователям определять, какой объем данных был передан в публичный реестр для каждой транзакции. [8] В Ethereum zk-Rollups также используются zk-SNARK для повышения масштабируемости. [9]
В 2017 году Bulletproofs [10] был выпущен, которые позволяют доказать, что зафиксированное значение находится в диапазоне, используя логарифмическое (по битовой длине диапазона) количество элементов поля и группы. [11] Позже Bulletproofs был реализован в протоколе Mimblewimble (основа Grin and Beam и Litecoin через блоки расширения) и криптовалюте Monero . [12]
В 2018 году zk-STARK ( с нулевым разглашением Масштабируемый прозрачный аргумент знаний ) [13] протокол представили Эли Бен-Сассон, Иддо Бентов, Инон Хореш и Михаил Рябзев, [14] обеспечивая прозрачность (отсутствие доверенной настройки), квазилинейное время проверки и полилогарифмическое время проверки. Краткие прозрачные аргументы знания с нулевым разглашением — это тип криптографической системы доказательства, которая позволяет одной стороне (доказывающему) доказать другой стороне (проверяющему), что определенное утверждение верно, не раскрывая никакой дополнительной информации, кроме истинности утверждения. сам. zk-STARK являются краткими, что означает, что они позволяют создавать короткие доказательства, которые легко проверить, и они прозрачны, что означает, что каждый может проверить доказательство, не нуждаясь в какой-либо секретной информации. [14]
В отличие от первого поколения zk-SNARK, zk-STARK по умолчанию не требуют доверенной настройки, что делает их особенно полезными для децентрализованных приложений, таких как блокчейны. Кроме того, zk-STARK можно использовать для одновременной проверки множества операторов, что делает их масштабируемыми и эффективными. [1]
В 2019 году были представлены рекурсивные zk-SNARK HALO без доверенной настройки. [15] Соленья [16] zk-SNARKs, основанные на предыдущей конструкции, приводят в действие Mina, первый блокчейн, поддающийся краткой проверке. [17]
Ниже представлен список протоколов и библиотек доказательства с нулевым разглашением, а также сравнение, основанное на прозрачности, универсальности и вероятной постквантовой безопасности. Прозрачный протокол — это протокол, который не требует какой-либо доверенной настройки и использует публичную случайность. Универсальный протокол — это протокол, который не требует отдельной доверенной настройки для каждого канала. Наконец, правдоподобным постквантовым протоколом является тот, который не подвержен известным атакам с использованием квантовых алгоритмов.
система ЗКП | Год публикации | Протокол | Прозрачный | Универсальный | Вероятно, постквантовая безопасность |
---|---|---|---|---|---|
Буратино [18] | 2013 | зк-СНАРК | Нет | Нет | Нет |
Джеппетто [19] | 2015 | зк-СНАРК | Нет | Нет | Нет |
TinyRAM [20] | 2013 | зк-СНАРК | Нет | Нет | Нет |
Буфет [21] | 2015 | зк-СНАРК | Нет | Нет | Нет |
виртуальная оперативная память [22] | 2018 | zk-СНАРГ | Нет | Да | Нет |
vnTinyRAM [23] | 2014 | зк-СНАРК | Нет | Да | Нет |
МИРАЖ [24] | 2020 | зк-СНАРК | Нет | Да | Нет |
Соник [25] | 2019 | зк-СНАРК | Нет | Да | Нет |
Марлин [26] | 2020 | зк-СНАРК | Нет | Да | Нет |
ПЛОНК [27] | 2019 | зк-СНАРК | Нет | Да | Нет |
СуперСоник [28] | 2020 | зк-СНАРК | Да | Да | Нет |
Пуленепробиваемость [29] | 2018 | Пуленепробиваемость | Да | Да | Нет |
Хайракс [30] | 2018 | зк-СНАРК | Да | Да | Нет |
Гало [15] | 2019 | зк-СНАРК | Да | Да | Нет |
Дева [31] | 2020 | зк-СНАРК | Да | Да | Да |
Свет [32] | 2017 | зк-СНАРК | Да | Да | Да |
Аврора [33] | 2019 | зк-СНАРК | Да | Да | Да |
zk-СТАРК [14] [34] | 2019 | zk-СТАРК | Да | Да | Да |
Зильч [35] [36] | 2021 | zk-СТАРК | Да | Да | Да |
Определение
[ редактировать ]Первоначально, [2] неинтерактивное нулевое разглашение определялось только как единая система доказательства теорем. В такой системе каждое доказательство требует собственной новой общей ссылочной строки. Общая ссылочная строка, как правило, не является случайной строкой. Например, он может состоять из случайно выбранных групповых элементов, которые используют все стороны протокола. Хотя элементы группы являются случайными, ссылочная строка не является таковой, поскольку содержит определенную структуру (например, элементы группы), отличающуюся от случайности. Впоследствии Файги, Лапидот и Шамир [37] представил доказательства с нулевым разглашением, основанные на нескольких теоремах, как более универсальное понятие для неинтерактивных доказательств с нулевым разглашением.
Неинтерактивные доказательства на основе пар
[ редактировать ]Криптография на основе спаривания привела к нескольким достижениям в области криптографии. Одним из этих достижений являются более мощные и эффективные неинтерактивные доказательства с нулевым разглашением. Оригинальная идея заключалась в том, чтобы скрыть значения парной оценки в обязательстве . Используя различные схемы обязательств, эта идея была использована для создания систем доказательства с нулевым разглашением в рамках подгруппы, скрывающей [38] и при решающем линейном предположении . [39] Эти системы доказательств доказывают выполнимость схемы и, таким образом, по теореме Кука – Левина позволяют доказать принадлежность каждого языка к NP. Размер общей ссылочной строки и доказательств относительно невелик; однако преобразование оператора в логическую схему требует значительных накладных расходов.
системы доказательств при сокрытии подгруппы , линейном предположении принятия решения и внешнем предположении Диффи-Хеллмана , которые позволяют напрямую доказывать уравнения произведения пар, которые распространены в криптографии на основе пар . Были предложены [40]
При сильных предположениях о знаниях известно, как создавать вычислительно обоснованные системы доказательства сублинейной длины для NP-полных языков. Точнее, доказательство в таких системах доказательств состоит лишь из небольшого числа элементов билинейной группы . [41] [42]
Ссылки
[ редактировать ]- ^ Перейти обратно: а б с Гун, Иньцзе; Джин, Ифэй; Ли, Ючан; Лю, Цзыи; Чжу, Чжии (январь 2022 г.). «Анализ и сравнение основных схем доказательства с нулевым разглашением» . Международная конференция по большим данным, информации и компьютерным сетям (BDICN) 2022 года . стр. 366–372. дои : 10.1109/BDICN55575.2022.00074 . ISBN 978-1-6654-8476-3 . S2CID 248267862 .
- ^ Перейти обратно: а б Мануэль Блюм, Пол Фельдман и Сильвио Микали. Неинтерактивное нулевое знание и его приложения. Материалы двадцатого ежегодного симпозиума ACM по теории вычислений (STOC 1988). 103–112. 1988 год
- ^ Одед Гольдрейх и Яир Орен. Определения и свойства систем доказательства с нулевым разглашением. Журнал криптологии. Том 7 (1). 1–32. 1994 (ПС)
- ^ Шафи Гольдвассер и Яэль Калаи. О (не)безопасности парадигмы Фиата-Шамира. Материалы 44-го ежегодного симпозиума IEEE по основам информатики (FOCS'03). 2003 г.
- ^ Рафаэль Пасс. Об отрицании в общей ссылочной строке и случайной модели Oracle. Достижения в криптологии – КРИПТО 2003. 316–337. 2003 (ПС)
- ^ Битанский, Нир; Канетти, Ран; Кьеза, Алессандро; Тромер, Эран (январь 2012 г.). «От извлекаемого сопротивления столкновению к кратким неинтерактивным аргументам знаний и обратно» . Материалы 3-й конференции «Инновации в теоретической информатике» - ITCS '12 . АКМ . стр. 326–349. дои : 10.1145/2090236.2090263 . ISBN 978-1-4503-1115-1 . S2CID 2576177 .
- ^ Бен-Сассон, Эли; Кьеза, Алессандро; Гарман, Кристина; Грин, Мэтью; Майерс, Ян; Тромер, Эран; Вирза, Мадарс (18 мая 2014 г.). «Zerocash: децентрализованные анонимные платежи из биткойнов» (PDF) . ИИЭЭ . Проверено 26 января 2016 г. .
- ^ Бен-Сассон, Эли; Кьеза, Алессандро. «Что такое zk-СНАРК?» . з.кэш . Проверено 3 ноября 2022 г.
- ^ «Сборки с нулевым разглашением» . Ethereum.org . Проверено 25 февраля 2023 г.
- ^ Бюнц, Бенедикт; Бутл, Джонатан; Боне, Дэн; Поэльстра, Эндрю; Вилле, Питер; Максвелл, Грег (май 2018 г.). «Пуленепробиваемые доказательства: краткие доказательства конфиденциальных транзакций и многое другое» . Симпозиум IEEE по безопасности и конфиденциальности (SP) 2018 г. стр. 315–334. дои : 10.1109/SP.2018.00020 . ISBN 978-1-5386-4353-2 . S2CID 3337741 .
- ^ Бюнц, Бенедикт; Бутл, Джонатан; Боне, Дэн; Поэльстра, Эндрю; Вилле, Питер; Максвелл, Грег (май 2018 г.). «Пуленепробиваемые доказательства: краткие доказательства конфиденциальных транзакций и многого другого» (PDF) . Симпозиум IEEE по безопасности и конфиденциальности (SP) 2018 г. стр. 315–334. дои : 10.1109/SP.2018.00020 . ISBN 978-1-5386-4353-2 . S2CID 3337741 . Проверено 2 декабря 2022 г.
- ^ Одендал, Хэнси; Шаррок, Кейл; Херден, Юв. «Пуленепробиваемость и Мимблвимбл» . Университет Тари Лабс. Архивировано из оригинала 29 сентября 2020 года . Проверено 3 декабря 2020 г.
- ^ http://www.cs.technion.ac.il/RESEARCH_DAY_17/POSTERS/michael_riabzev.pdf
- ^ Перейти обратно: а б с Эли Бен-Сассон; Иддо Бентов; Йинон Хореш; Михаил Рябзев (6 марта 2018 г.). «Масштабируемая, прозрачная и постквантовая безопасная вычислительная целостность» (PDF) . Международная ассоциация криптологических исследований . Проверено 24 октября 2021 г.
- ^ Перейти обратно: а б Боу, Шон; Григг, Джек; Хопвуд, Дайра (2019). «Рекурсивная композиция доказательства без доверенной установки» . Архив электронной печати по криптологии .
- ^ «Знакомьтесь, Pickles SNARK: включение смарт-контрактов на протоколе Coda» . Минский протокол . Проверено 25 февраля 2023 г.
- ^ Бонно, Джозеф; Меклер, Исаак; Рао, В.; Эван; Шапиро (2021). «Мина: децентрализованная криптовалюта в больших масштабах» (PDF) . S2CID 226280610 .
- ^ Парно, Брайан; Хауэлл, Джон; Джентри, Крейг; Райкова, Мариана (май 2013 г.). «Пиноккио: почти практические проверяемые вычисления» . Симпозиум IEEE 2013 по безопасности и конфиденциальности . стр. 238–252. дои : 10.1109/СП.2013.47 . ISBN 978-0-7695-4977-4 . S2CID 1155080 .
- ^ Костелло, Крейг; Фурне, Седрик; Хауэлл, Джон; Кольвайс, Маркульф; Кройтер, Бенджамин; Наэриг, Майкл; Парно, Брайан; Захур, Сами (май 2015 г.). «Джеппетто: универсальные проверяемые вычисления» . Симпозиум IEEE 2015 по безопасности и конфиденциальности . стр. 253–270. дои : 10.1109/СП.2015.23 . ISBN 978-1-4673-6949-7 . S2CID 3343426 .
- ^ Бен-Сассон, Эли; Кьеза, Алессандро; Генкин, Даниил; Тромер, Эран; Вирза, Мадарс (2013). «SNARK для C: краткая проверка выполнения программы с нулевым разглашением» . В Канетти Ран; Гарай, Хуан А. (ред.). Достижения криптологии – CRYPTO 2013 . Конспекты лекций по информатике. Том. 8043. Берлин, Гейдельберг: Springer. стр. 90–108. дои : 10.1007/978-3-642-40084-1_6 . ISBN 978-3-642-40084-1 .
- ^ Вахби, Риад С.; Сетти, Шринат; Рен, Цзочэн; Блумберг, Эндрю Дж.; Уолфиш, Майкл (2015). Эффективная оперативная память и поток управления в проверяемых аутсорсинговых вычислениях . дои : 10.14722/ndss.2015.23097 . ISBN 978-1-891562-38-9 . Проверено 25 февраля 2023 г.
- ^ Чжан, Юпэн; Генкин, Даниил; Кац, Джонатан; Пападопулос, Димитриос; Папаманту, Харалампос (май 2018 г.). «VRAM: более быстрая проверяемая ОЗУ с программно-независимой предварительной обработкой» . Симпозиум IEEE по безопасности и конфиденциальности (SP) 2018 г. стр. 908–925. дои : 10.1109/SP.2018.00013 . ISBN 978-1-5386-4353-2 . S2CID 41548742 .
- ^ Бен-Сассон, Эли; Церковь, Александр; Тромер, Эран; Вирза, Мадарс (2014). Краткий {неинтерактивный} нулевой уровень знаний для архитектуры фон Неймана . стр. 781–796. ISBN 978-1-931971-15-7 .
- ^ Косба, Ахмед; Пападопулос, Димитриос; Папаманту, Харалампос; Песня, Рассвет (2020). «МИРАЖ: Краткие аргументы в пользу рандомизированных алгоритмов с приложениями к универсальным zk-SNARK» . Архив электронной печати по криптологии .
- ^ Маллер, Мэри; Боу, Шон; Кольвайс, Маркульф; Мейкледжон, Сара (6 ноября 2019 г.). «Соник» . Материалы конференции ACM SIGSAC 2019 по компьютерной и коммуникационной безопасности . ККС '19. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 2111–2128. дои : 10.1145/3319535.3339817 . ISBN 978-1-4503-6747-9 . S2CID 60442921 .
- ^ Кьеза, Алессандро; Ху, Юньконг; Маллер, Мэри; Мишра, Пратюш; Веселый, Ной; Уорд, Николас (2020). «Марлин: предварительная обработка zkSNARK с помощью универсального и обновляемого SRS» . В Канто, Энн; Ишаи, Юваль (ред.). Достижения в криптологии – EUROCRYPT 2020 . Конспекты лекций по информатике. Том. 12105. Чам: Springer International Publishing. стр. 738–768. дои : 10.1007/978-3-030-45721-1_26 . ISBN 978-3-030-45721-1 . S2CID 204772154 .
- ^ Габизон, Ариэль; Уильямсон, Закари Дж.; Чиоботару, Оана (2019). «ПЛОНК: Перестановки над базисами Лагранжа для вселенских неинтерактивных аргументов познания» . Архив электронной печати по криптологии .
- ^ Бюнц, Бенедикт; Фиш, Бен; Шепенец, Алан (2020). «Прозрачные SNARK от компиляторов DARK» . В Канто, Энн; Ишай, Юваль (ред.). Достижения в криптологии – EUROCRYPT 2020 . Конспекты лекций по информатике. Том. 12105. Чам: Springer International Publishing. стр. 677–706. дои : 10.1007/978-3-030-45721-1_24 . ISBN 978-3-030-45721-1 . S2CID 204892714 .
- ^ Бюнц, Бенедикт; Бутл, Джонатан; Боне, Дэн; Поэльстра, Эндрю; Вилле, Питер; Максвелл, Грег (май 2018 г.). «Пуленепробиваемые доказательства: краткие доказательства конфиденциальных транзакций и многое другое» . Симпозиум IEEE по безопасности и конфиденциальности (SP) 2018 г. стр. 315–334. дои : 10.1109/SP.2018.00020 . ISBN 978-1-5386-4353-2 . S2CID 3337741 .
- ^ Вахби, Риад С.; Циалла, Иоанна; Шелат, Абхи; Талер, Джастин; Уолфиш, Майкл (май 2018 г.). «Двойная эффективность zkSNARK без доверенной настройки» . Симпозиум IEEE по безопасности и конфиденциальности (SP) 2018 г. стр. 926–943. дои : 10.1109/SP.2018.00060 . ISBN 978-1-5386-4353-2 . S2CID 549873 .
- ^ Чжан, Цзяхэн; Се, Тяньчэн; Чжан, Юпэн; Песня, Рассвет (май 2020 г.). «Прозрачное полиномиальное делегирование и его применение для доказательства с нулевым разглашением» . Симпозиум IEEE 2020 по безопасности и конфиденциальности (SP) . стр. 859–876. дои : 10.1109/SP40000.2020.00052 . ISBN 978-1-7281-3497-0 . S2CID 209467198 .
- ^ Эймс, Скотт; Хазай, Кармит; Ишаи, Юваль; Венкитасубраманиам, Мутурамакришнан (30 октября 2017 г.). «Лигеро» . Материалы конференции ACM SIGSAC 2017 года по компьютерной и коммуникационной безопасности . ККС '17. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 2087–2104. дои : 10.1145/3133956.3134104 . ISBN 978-1-4503-4946-8 . S2CID 5348527 .
- ^ Бен-Сассон, Эли; Кьеза, Алессандро; Рябзев, Михаил; Спунер, Николас; Вирза, Мадарс; Уорд, Николас П. (2019). «Аврора: прозрачные и краткие аргументы в пользу R1CS» . В Ишае, Юваль; Реймен, Винсент (ред.). Достижения в криптологии – EUROCRYPT 2019 . Конспекты лекций по информатике. Том. 11476. Чам: Springer International Publishing. стр. 103–128. дои : 10.1007/978-3-030-17653-2_4 . ISBN 978-3-030-17653-2 . S2CID 52832327 .
- ^ Бен-Сассон, Эли; Бентов, Иддо; Хореш, Инон; Рябзев, Михаил (2019). «Масштабируемость с нулевым знанием без доверенной настройки» . У Болдыревой Александры; Миччанчо, Даниэле (ред.). Достижения криптологии – CRYPTO 2019 . Конспекты лекций по информатике. Том. 11694. Чам: Springer International Publishing. стр. 701–732. дои : 10.1007/978-3-030-26954-8_23 . ISBN 978-3-030-26954-8 . S2CID 199501907 .
- ^ Вычисления, заслуживающие доверия (30 августа 2021 г.). «Прозрачные доказательства с нулевым разглашением с пшиком» . Середина . Проверено 25 февраля 2023 г.
- ^ Моурис, Димитрис; Цуцос, Нектариос Георгиос (2021). «Зилч: основа для развертывания прозрачных доказательств с нулевым разглашением» . Транзакции IEEE по информационной криминалистике и безопасности . 16 : 3269–3284. дои : 10.1109/TIFS.2021.3074869 . ISSN 1556-6021 . S2CID 222069813 .
- ^ Уриэль Файги, Дрор Лапидот, Ади Шамир: Множественные неинтерактивные доказательства с нулевым разглашением при общих предположениях. СИАМ Дж. Компьютер. 29 (1): 1–28 (1999)
- ^ Йенс Грот, Рафаил Островский, Амит Сахай: Идеальное неинтерактивное нулевое знание для NP. ЕВРОКРИПТ 2006: 339–358.
- ^ Йенс Грот, Рафаил Островский, Амит Сахай: Неинтерактивные запы и новые методы для NIZK. КРИПТО 2006: 97–111.
- ^ Йенс Грот, Амит Сахаи: Эффективные неинтерактивные системы доказательств для билинейных групп. ЕВРОКРИПТ 2008: 415–432.
- ^ Йенс Грот. Короткие неинтерактивные аргументы с нулевым разглашением на основе пар. АЗИАКРИПТ 2010: 321–340.
- ^ Хельгер Липмаа. Множества без прогрессии и неинтерактивные аргументы с нулевым разглашением на основе сублинейных пар. ТСС 2012: 169–189.