Доказательства с нулевым разглашением: это похоже на волшебство, но я объясню это

Предположим, Пегги нужно доказать Виктору, что она владеет секретом, не раскрывая его. Сможет ли она сделать это так, чтобы убедить Виктора, что она действительно знает секрет? Этот вопрос лежит в основе одного из самых мощных криптографических процессов, которые мы можем использовать в системах идентификации: доказательства с нулевым разглашением (ZKP) .

Предположим, например, что у Пегги есть цифровые водительские права, и она хочет доказать бармену Виктору, что ей больше 21 года, не просто передавая свои водительские права и даже не показывая ему дату своего рождения. ZKP позволяют Пегги доказать, что в ее водительских правах указано, что ей как минимум 21 год, таким образом, чтобы убедить Виктора, без необходимости Пегги раскрывать что-либо еще (т. Е. Никаких лишних знаний нет).

Эта проблема была впервые исследована исследователями Массачусетского технологического института Шафи Голдвассером, Сильвио Микали и Чарльзом Ракоффом в 1980-х годах как способ борьбы с утечкой информации. Цель состоит в том, чтобы уменьшить количество дополнительной информации, которую проверяющий Виктор может узнать о проверяющей Пегги.

Одним из способов понять, как работают ZKP, является история о Пещере Алибабы, впервые опубликованная криптографами Кискатером, Гийу и Берсоном1. На следующей диаграмме представлена иллюстрация.

В Пещере Алибабы есть два прохода, обозначенных A и B, которые разделяются на один проход, ведущий к входу. У Пегги есть секретный код, который позволяет ей открыть дверь, соединяющую А и Б. Виктор хочет купить код, но не будет платить, пока не будет уверен, что Пегги его знает. Пегги не поделится ими с Виктором, пока он не заплатит.

Алгоритм, позволяющий Пегги доказать, что она знает код, выглядит следующим образом:

• Виктор стоит возле пещеры, а Пегги входит и выбирает один из проходов. Виктору не разрешено видеть, по какому пути идет Пегги.
• Виктор входит в пещеру и наугад называет «А» или «Б».
• Пегги выходит из правильного прохода, потому что она может легко открыть дверь независимо от того, какой выбор она сделала при входе.
• Конечно, Пегги могла просто повезти и угадать правильно, поэтому Пегги и Виктор повторяют эксперимент много раз.

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

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

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

Когда мы говорим «нулевое знание» и говорим о том, что Виктор не узнал ничего, кроме рассматриваемого утверждения, это не совсем так. В пещере Алибабы Пегги с нулевым разглашением доказывает, что знает секрет. Но есть много других вещей, которые Виктор узнает о Пегги, с которыми ЗКП ничего не может поделать. Например, Виктор знает, что Пегги его слышит, говорит на его языке, ходит и готова сотрудничать. Он также может узнать кое-что о пещере, например, сколько времени нужно, чтобы открыть дверь. Пегги узнает то же самое о Викторе. Итак, реальность такова, что доказательство представляет собой приблизительно нулевое знание, а не совершенно нулевое знание.

ЗКП Системс

Примером пещеры Alibaba является очень специфическое использование ZKP, так называемое доказательство знания с нулевым разглашением . Пегги доказывает, что она что-то знает (или обладает). В более общем плане Пегги, возможно, захочет доказать Виктору множество фактов. Они могут включать в себя пропозициональные фразы или даже значения. ЗКП тоже могут это сделать.

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

Для простоты предположим, что Пегги и Виктору платят по 10, 20, 30 или 40 долларов в час.

Алгоритм работает следующим образом:

• Пегги покупает четыре сейфа и маркирует их по 10, 20, 30 и 40 долларов.
• Она выбрасывает ключи от всех ящиков, кроме той, на которой указана ее зарплата.
• Пегги передает все запертые коробки Виктору, который конфиденциально вкладывает листок бумаги со знаком «+» в прорезь в верхней части коробки с надписью его зарплата. Во все остальные ячейки он кладет квитанцию со знаком «-».
• Виктор возвращает коробки Пегги, которая использует свой ключ наедине, чтобы открыть коробку со своей зарплатой.
• Если она найдет «+», то они заработают одинаковую сумму. В противном случае они зарабатывают другую сумму. Она может использовать это, чтобы доказать Виктору этот факт.

Это называется передачей без внимания и доказывает истинность или ложность предложения VictorSalary = PeggySalary с нулевым знанием (т. е. без раскрытия какой-либо другой информации).

Чтобы это сработало, Пегги и Виктор должны поверить, что другой ответит и назовет свою реальную зарплату. Виктору нужно верить, что Пегги выбросит три других ключа. Пегги должна верить, что Виктор положит в коробки только один листок со знаком «+».

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

Неинтерактивные ЗКП

В предыдущих примерах Пегги смогла доказать Виктору что-то посредством серии взаимодействий. Чтобы ZKP были практичными, взаимодействие между проверяющим и проверяющим должно быть минимальным. К счастью, метод под названием SNARK позволяет проводить неинтерактивные доказательства с нулевым разглашением.

SNARK обладают следующими свойствами (отсюда и свое название):

• Кратко: размеры сообщений малы по сравнению с длиной фактического доказательства.
• Неинтерактивный : за исключением некоторых настроек, проверяющий отправляет проверяющему только одно сообщение.
• АРГУМЕНТЫ: на самом деле это аргумент в пользу того, что что-то верно, а не доказательство, как мы понимаем это математически. В частности, доказывающее устройство теоретически могло бы доказать ложные утверждения при наличии достаточной вычислительной мощности. Таким образом, SNARK являются «вычислительно обоснованными», а не «идеально обоснованными».
• Знания: доказывающий знает рассматриваемый факт.

Обычно вы увидите букву «zk» (для нулевого разглашения), прикрепленную спереди, чтобы указать, что во время этого процесса проверяющий не узнает ничего, кроме доказываемых фактов.

Математика, лежащая в основе zkSNARKs, включает гомоморфные вычисления над полиномами высокой степени. Но мы можем понять, как работают zkSNARK, не зная базовой математики, которая гарантирует их работоспособность. Если вам нужны более подробные сведения о математике, я рекомендую книгу Кристиана Райтвисснера «zkSNARKs в двух словах» .

В качестве простого примера предположим, что Виктору дан хэш sha256 H некоторого значения. Пегги хочет доказать, что она знает такое значение s , что sha265(s) == H , не раскрывая s Виктору. Мы можем определить функцию C , которая фиксирует взаимосвязь:

 C(x, w) = ( sha256(w) == x )

Итак, C(H, s) == true , а другие значения w вернут false .

Для вычисления zkSNARK требуются три функции G , P и V G — это генератор ключей, который принимает секретный параметр, называемый lambda , и функцию C , и генерирует два открытых ключа: ключ подтверждения pk и ключ проверки vk . Их нужно сгенерировать только один раз для данной функции C После этого шага параметр lambda должен быть уничтожен, поскольку он больше не нужен, и любой, у кого он есть, может создать поддельные доказательства.

Функция доказательства P принимает в качестве входных данных доказывающий ключ pk , общедоступный вход x и частного (секретного) свидетеля w . Результатом выполнения P(pk,x,w) является доказательство prf того, что доказывающему известно значение w , удовлетворяющее C

Функция проверки V вычисляет V(vk, x, prf) , которое истинно, если доказательство prf верно, и ложно в противном случае.

Возвращаясь к Пегги и Виктору, Виктор выбирает функцию C , представляющую то, что он хочет, чтобы Пегги доказала, создает случайное число lambda и запускает G для генерации ключей доказательства и проверки:

 (pk, vk) = G(C, lambda)

Пегги не должна изучать значение lambda . Виктор делится C , pk и vk с Пегги.

Пегги хочет доказать, что она знает значение s , которое удовлетворяет C для x = H Она запускает проверочную функцию P , используя эти значения в качестве входных данных:

 prf = P(pk, H, s)

Пегги представляет prf доказательства Виктору, который запускает функцию проверки:

 V(vk, H, prf)

Если результат верен, Виктор может быть уверен, что Пегги знает значение s .

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

Эта статья представляет собой отрывок из моей книги Learning Digital Identity , опубликованной O’Reilly Media.

Примечания

1. Кискатер, Жан-Жак; Гийу, Луи К.; Берсон, Томас А. (1990). Как объяснить вашим детям протоколы с нулевым разглашением (PDF) . Достижения в криптологии - КРИПТО '89: Труды. Конспекты лекций по информатике. 435. стр. 628–631. дои: 10.1007/0-387-34805-0_60. ISBN 978-0-387-97317-3.