Протоколы с нулевым разглашением позволяют осуществлять идентификацию, обмен ключами и другие основные криптографические операции без утечки секретной информации во время разговора и с меньшими вычислительными требованиями, чем использование сопоставимых протоколов с открытым ключом. Одно из современных воплощений данного протокола - Zcash.
В статье описан очень простой протокол нулевого знания и проанализированы его возможное использование и криптографические сильные и слабые стороны. Протоколы с нулевым разглашением не раскрывают информацию или секрет во время обмена, или любому подслушивающему устройству. У них есть некоторые очень интересные свойства, например, поскольку сам секрет (например, ваша личность) не передается проверяющей стороне, то она не сможет попытаться представиться вами какой-либо третьей стороне. С их помощью можно решить большинство обычных криптографических проблем. Для некоторых приложений, таких как обмен ключами (для более позднего нормального дешевого и быстрого симметричного шифрования по каналу связи) или доказательство взаимных идентичностей, протоколы с нулевым разглашением могут во многих случаях быть очень хорошим и подходящим решением.
Стороны в протоколе с нулевым разглашением:
Пегги - Доказывающий. У Пегги есть информация, которую она хочет доказать Виктору, но она не хочет рассказывать Виктору сам секрет.
Виктор-Проверяющий.Виктор задает Пегги ряд вопросов, пытаясь выяснить, действительно ли Пегги знает секрет или нет. Виктор не узнает ничего из самого секрета, даже если обманет или не будет придерживаться протокола.
Ева Подслушивающая. Ева слушает разговор между Пегги и Виктором. Хороший протокол с нулевым разглашением также гарантирует, что любая третья сторона не узнает ничего о секрете и даже не сможет воспроизвести его для кого-либо позже, чтобы убедить их.
Мэгги Злоумышленник. Мэгги слушает трафик протокола и злонамеренно отправляет дополнительные сообщения и изменяет или уничтожает сообщения. Протокол должен быть устойчив к такому виду деятельности.
Терминология
Секрет означает некоторую часть информации, будь то пароль, закрытый ключ криптосистемы с открытым ключом, решение какой-то математической проблемы или набор учетных данных. В протоколах с нулевым разглашением, Доказывающий может убедить Проверяющего , что у него есть знание, секрет, не раскрывая самого секрета, в отличие, например, от обычных запросов имени пользователя-пароля.
Аккредитация означает укрепление доверия к каждой итерации протокола. Если в одном шаге протокола с нулевым разглашением вероятность того, что самозванец сможет дать ответ, составляет 1 из 2, шансы на ее прохождение всего разговора убывают со скоростью 2 в степени количества раундов
Протокол "Выбирая-или-Выбывай" ("Cut-and-choose ") - одна неудача означает провал всего протокола, но возможно продолжать работать по протоколу, сколь угодно долго, если ответы верные. По достижении определенного уровня доверия, протокол считается успешным.
Особенности протоколов с нулевым разглашением можно описать так:
Проверяющий не может ничего узнать из протокола
Проверяющий ничего не узнает из протокола, чего он не мог бы узнать сам, без Доказывающего. Это Центральная концепция нулевого разглашения, т. е. не передается никакого знания (нулевое разглашение). Без этой функции протокол будет называться протоколом с минимальным разглашением, т. е. протоколы с нулевым уровнем знаний требуют, чтобы в любом случае не было никакой информации.
Доказывающий не может обмануть Проверяющего
Если Пегги не знает секрет, она может добиться успеха только с большим количеством везения. После нескольких раундов протокола шансы самозванца резко падают.
Протоколы также вырезают и выбирают, т. е. первый раз, когда Доказывающий терпит неудачу, Виктор знает, что Пегги - Злоумышленник. Таким образом, с каждым раундом протокола уверенность становится все лучше и лучше.
Протоколы могут работать, даже если шансы на прохождение догадки высоки, вам просто нужно больше раундов в протоколе.
Проверяющий не может обмануть Доказывающего.
Виктор не может получить информацию из протокола, даже если он не следует протоколу. Единственное, что Виктор может сделать, это убедить себя, что Пегги знает секрет. Доказывающий всегда будет раскрывать только одно решение из многих по каждому вопросу, никогда не все из них, что позволило бы выяснить сам секрет.
Проверяющий не может претендовать на роль Доказывающего перед любой третьей стороной.
Поскольку никакая информация не может течь от Пегги до Виктора, Виктор не может пытаться маскироваться под Пегги для какой-либо третьей стороны. Атака посредника (man-in-the-middle) невозможна.
Кроме того, если Проверяющий записывает разговор между ним и Проверяющим, эта запись не может использоваться для убеждения любой третьей стороны. Это выглядит так же, как фальшивый разговор (например, когда Проверяющий и Доказывающий заранее договорились, какие запросы выберет Проверяющий ).
Режимы работы
Интерактивный, где Пегги и Виктор интерактивно проходят через протокол, создавая определенность по частям.
Параллельный, где Пегги создает ряд проблем и Виктор просит ряд решений. Это можно использовать для уменьшения количества интерактивных сообщений с подключением во время медленного ответа.
Оффлайн, где Пегги создает ряд вопросов, а затем использует криптографически сильную одностороннюю хэш-функцию на данных и набор задач, чтобы играть роль Виктора, чтобы выбрать случайное решение, необходимое для каждой задачи. Затем она добавляет эти решения к сообщению. Этот режим можно использовать для цифровых подписей .
Вычислительные требования.
Многие источники утверждают, что протоколы с нулевым разглашением имеют более легкие вычислительные требования, чем, например, протоколы с открытым ключом. Обычное утверждение состоит в том, что протоколы с нулевым разглашением могут достигать тех же результатов, что и протоколы с открытым ключом, требуя при этом на один-два порядка меньше вычислительной мощности.
Типичная реализация может потребовать 20 30 модульных умножений полнотекстовых битовых строк, которые могут быть оптимизированы до 10 20 с предварительной калькуляцией. Это намного быстрее, чем RSA.
Требования к памяти кажутся примерно равными - чтобы иметь очень высокий уровень безопасности протокола с нулевым разглашением, вам понадобятся очень длинные ключи и номера, поэтому в терминах памяти требования могут быть не очень разными.
Итеративные Относительно Легкие Транзакции.Механизмы с нулевым разглашением позволяют разделить протокол на итерационный процесс более легких транзакций, а не одну тяжелую транзакцию.
Простейший пример: пещера Али Бабы
Классическим примером протокола доказательства с нулевым разглашением является протокол доказательства знания пароля к двери внутри круговой пещеры. Пусть Алиса (Alice) знает этот пароль и хочет доказать его знание Бобу (Bob) без разглашения самого пароля. Используется следующий протокол:
1. Алиса заходит в пещеру и подходит к двери с произвольной стороны так чтобы Боб не знал с какой стороны находится Алиса.
2. Боб заходит в пещеру и просит выйти Алису с какой либо из сторон пещеры (слева или справа).
3. Алиса зная пароль к двери всегда сможет выполнить пожелание Боба, появившись с любой стороны. После каждой итерации уверенность Боба в том что Алиса знает секрет увеличивается вдвое. Таким образом после k успешно выполненных операций вероятность того что Алиса на самом деле обманывает Боба равна 1/2^k .
Протоколы с нулевым разглашением и их применения.
А. Ханну Аронссон Протоколы с нулевым разглашением и малые системы
Протоколы аутентификации с нулевым разглашением секрета
Randomness and Mathematical Proof
Cryptographic and Physical Zero-Knowledge Proof Systems for Solutions of Sudoku Puzzles
Scalable, transparent, and post-quantum secure computational integrity
STARKs, Part I: Proofs with Polynomials
Zero Knowledge Proofs: An illustrated primer
лекция Zooko Wilcox о протоколах нулевого разглашения и как это используется в ZCash .
Zero knowledge and some applications
