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

Неинтерактивные доказательства с нулевым разглашением - также известные как NIZK, ^[1] zk-SNARK, ^[2] zk-STARK ^[3] - это доказательства с нулевым разглашением, которые не требуют взаимодействия ^{[ требуется пояснение ]} между доказывающим и проверяющим.

История [ править ]

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

Блюм , Фельдман и Микали ^[4] показали в 1988 г., что общая ссылочная строка, разделяемая проверяющим и проверяющим, достаточна для достижения вычислительного нулевого знания без необходимости взаимодействия. Голдрайх и Орен ^[5] дали результаты о невозможности ^{[ необходимы разъяснения ]} для одноразовых протоколов с нулевым разглашением в стандартной модели . В 2003 году Шафи Голдвассер и Яэль Тауман Калаи опубликовали пример схемы идентификации, для которой любая хеш-функция приводит к небезопасной схеме цифровой подписи. ^[6] Эти результаты не противоречат друг другу, так как невозможность^{[ Требуется пояснение ]} Голдрейха и Орена не выполняется ни в общей эталонной струнной модели, ни в модели случайного оракула . Однако неинтерактивные доказательства с нулевым разглашением показывают разделение между криптографическими задачами, которые могут быть выполнены в стандартной модели, и теми, которые могут быть выполнены в «более мощных» расширенных моделях. ^{[ необходима цитата ]}

Модель влияет на свойства, которые могут быть получены из протокола с нулевым разглашением. Пасс ^[7] показал, что в общей модели ссылочной строки неинтерактивные протоколы с нулевым разглашением не сохраняют всех свойств интерактивных протоколов с нулевым разглашением; например, они не оставляют за собой право отрицания.

Неинтерактивные доказательства с нулевым разглашением также могут быть получены в модели случайного оракула с использованием эвристики Фиат – Шамира . В статье Битанского и др. 2012 года введено сокращение zk-SNARK для краткого неинтерактивного аргумента знания с нулевым разглашением . ^[2] Первое широко распространенное применение zk-SNARK было в протоколе цепочки блоков Zerocash , где криптография с нулевым разглашением обеспечивает вычислительную основу, облегчая математические доказательства того, что одна сторона владеет определенной информацией, не раскрывая, что это за информация. ^{[8] [9]} К 2021 году "82 криптовалютына общую сумму 8,85 миллиарда долларов США [зашифрованные] их транзакции с использованием доказательств с нулевым разглашением или аналогичной частной технологии » ^[8].

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

В 2018 году был представлен протокол zk- STARK (масштабируемый прозрачный аргумент знаний с нулевым разглашением) ^[12] , ^[13] обеспечивающий прозрачность (отсутствие доверенной настройки), квазилинейное время проверки и время полилогарифмической проверки. ^[3]

Определение [ править ]

Этот раздел, возможно, содержит оригинальные исследования . Пожалуйста, улучшите его , проверив сделанные утверждения и добавив встроенные цитаты . Заявления, содержащие только оригинальные исследования, следует удалить. ( Апрель 2021 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

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

В этой модели проверяющий и проверяющий обладают эталонной строкой, взятой из дистрибутива D доверенной установкой . Чтобы доказать заявление со свидетелем w , проверяющий бежит и отправляет доказательство ,, проверяющему. Проверяющий принимает, если , и отклоняет в противном случае. Чтобы учесть тот факт, который может повлиять на утверждения, которые доказываются, отношение свидетеля может быть обобщено до параметризованного с помощью . ^{[ необходима цитата ]}${\ displaystyle \ sigma \ gets \ operatorname {Setup} \ left (1 ^ {k} \ right)}$${\ displaystyle y \ in L}$${\ displaystyle \ pi \ gets \ operatorname {Prove} (\ sigma, y, w)}$${\ displaystyle \ pi}$${\ displaystyle \ operatorname {Verify} \ left (\ sigma, y, \ pi \ right) = \ mathrm {accept}}$${\ displaystyle \ sigma}$${\ Displaystyle (у, ш) \ в Р _ {\ sigma}}$${\ displaystyle \ sigma}$

Полнота [ править ]

Проверка успешна для всех и каждого . ^{[ необходима цитата ]}${\ displaystyle \ sigma \ in \ operatorname {Setup} \ left (1 ^ {k} \ right)}$${\ Displaystyle (у, ш) \ в Р _ {\ sigma}}$

Более формально, ^{[ необходима цитата ]}

для всех k , all и all : ${\ displaystyle \ sigma \ in \ operatorname {Setup} \ left (1 ^ {k} \ right)}$${\ Displaystyle (у, ш) \ в Р _ {\ sigma}}$

${\ displaystyle \ Pr \ left [\ pi \ gets \ operatorname {Prove} (\ sigma, y, w): \ operatorname {Verify} (\ sigma, y, \ pi) = \ mathrm {accept} \ right] = 1}$

Обоснованность [ править ]

Обоснованность требует, чтобы ни один доказывающий не мог заставить проверяющего принять неверное утверждение, кроме как с некоторой небольшой вероятностью. Верхняя граница этой вероятности называется ошибкой надежности системы доказательств. ^{[ необходима цитата ]}${\ displaystyle y \ not \ in L}$

Более формально, ^{[ необходима цитата ]}

для каждой злонамеренной расстойки, существует ничтожную функцию , такие , что${\ displaystyle {\ tilde {P}}}$${\ displaystyle \ nu}$

${\displaystyle \Pr \left[\sigma \gets \operatorname {Setup} \left(1^{k}\right),(y,\pi )\gets {\tilde {P}}(\sigma ):y\not \in L\land \operatorname {Verify} (\sigma ,y,\pi )=\mathrm {accept} \right]=\nu (k)\;.}$

Приведенное выше определение требует, чтобы ошибкой надежности можно было пренебречь в параметре безопасности k . Увеличивая k, можно сделать произвольно малую ошибку надежности. Если ошибка надежности равна 0 для всех k , мы говорим об идеальной надежности .

Мульти-теорема с нулевым разглашением [ править ]

Неинтерактивная система доказательства является многопрофильной теоремой с нулевым знанием, если существует имитатор, такие , что для всех неравномерных полиномиальных противников времени, , ^{[ править ]}${\displaystyle (\operatorname {Setup} ,\operatorname {Prove} ,\operatorname {Verify} )}$${\displaystyle \operatorname {Sim} =(\operatorname {Sim} _{1},\operatorname {Sim} _{2})}$${\displaystyle {\mathcal {A}}}$

${\displaystyle \Pr \left[\sigma \gets \operatorname {Setup} (1^{k}):{\mathcal {A}}^{{\operatorname {Prove} }(\sigma ,.,.)}(\sigma )=1\right]\equiv \Pr \left[(\sigma ,\tau )\gets \operatorname {Sim} _{1}:{\mathcal {A}}^{{\operatorname {Sim} }(\sigma ,\tau ,.,.)}(\sigma )=1\right]}$

Здесь выходы для и оба оракулов выхода неисправность в противном случае. ^{[ необходима цитата ]}${\displaystyle \operatorname {Sim} (\sigma ,\tau ,y,w)}$${\displaystyle \operatorname {Sim} _{2}(\sigma ,\tau ,y)}$${\displaystyle (y,w)\in R_{\sigma }}$

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

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

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

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

Ссылки [ править ]

Внешние ссылки [ править ]

• Эффективная неинтерактивная статистическая система доказательства с нулевым разглашением для квазибезопасных простых продуктов