Доказательство с нулевым разглашением загадка про скрепку
Обновлено: 17.09.2024
Протоколы с нулевым разглашением позволяют осуществлять идентификацию, обмен ключами и другие основные криптографические операции без утечки секретной информации во время разговора и с меньшими вычислительными требованиями, чем использование сопоставимых протоколов с открытым ключом. Одно из современных воплощений данного протокола - 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 .
Где еще используется доказательство с нулевым разглашением?
Aztec - это проект, который пытается внедрить доказательство с нулевым разглашением в существующую сеть Ethereum путем создания стека интеллектуальных контрактов, ориентированных на конфиденциальность.
Эти полностью частные смарт контракты могут быть использованы для создания частных токенов Ethereum и децентрализованных организаций (DAO).
Обновление Ethereum под кодовым названием Istanbul было специально разработано для сокращения затрат на доказательства с нулевым разглашением, подобные тем, которые используются в Aztec.
Другие блокчейны также начинают серьезно относиться к конфиденциальности. Tron развернул версию zk-SNARK в своей сети, хотя не все транзакции являются у этой монеты частными.
Краткая история
- 1985 - Первые доказательства с нулевым разглашением были написаны в статье «Сложность знаний интерактивных систем доказательств» Шафи Голдвассером, Сильвио Микали и Чарльзом Ракоффом.
- 2012- Алессандро Кьеза и команда исследователей используют термин zk-SNARKs.
- 2016 - Zcash выпущен и становится первой используемой криптовалютой, ориентированной на конфиденциальность, с использованием zk-SNARK.
В 1990 году криптограф Квискватер опубликовал статью «Как Объяснить Протоколы Нулевого Разглашения своим детям». В статье представлена концепция ZK доказательств с притчей о пещере Али-Бабы.
С момента ее первой публикации эта статья несколько раз подверглась редакции, и сейчас в интернете можно найти несколько её вариантов. Тем не менее, основная информация во всех измененных редакциях та же самая.
Представьте себе круглую пещеру с 1 входом и волшебной дверью в нее, разделяющей две боковые дорожки. Чтобы пройти через эту магическую дверь, необходимо условие: сказать правильные секретные слова.
Итак, учтите, что Алиса (желтая) хочет доказать Бобу (синему), что она знает настоящие секретные слова, но в то же время она хочет держать эти слова в секрете. Для этого Боб соглашается подождать ее снаружи, пока Алиса входит в пещеру и идет до конца одного из двух возможных путей. Ниже в примере она решает пройти путь 1.
Спустя время Боб проходит мимо входа и кричит, с какой стороны он хочет, чтобы Алиса появилась (путь 2 в данном случае).
Если Алиса не врет и действительно знает секретные слова, она точно окажется на выбранном пути Боба.
Весь процесс может быть проверен несколько раз, чтобы доказать, что Алиса не случайно выбрала правильный путь.
Притча о Али-Бабе и Пещере иллюстрирует концепцию доказательств с нулевым разглашением, которое является частью zk-SNARK и zk-STARK протоколов.
ZK-доказательства могут быть использованы для подтверждения владения определенными знаниями, не раскрывая никакой при этом информации о них.
Следующая загадка
Доказательство с нулевым разглашением (знанием) (Zero-knowledge proof) представляет собой криптографический протокол, позволяющий одной из сторон (проверяющему, стороне B) убедиться в том, что вторая сторона (доказывающая, сторона A) знает какое-либо утверждение, при этом проверяющий не получает никакой другой информации о самом утверждении. Другими словами, А доказывает знание секрета, не разглашая самого секрета.
Использовать доказательства с нулевым знанием для доказательства идентичности было впервые предложено Уриелем Файгом, Амосом Фиатом и Ади Шамиром. В данном случае пользователь доказывает знание своего закрытого ключа, который в данном случае выступает в роли секрета, не раскрывая его. Таким образом, он доказывает свою идентичность.
Доказательство с нулевым разглашением обладает тремя основными свойствами:
1. Полнота. Если доказывающий знает утверждение, то он сможет убедить в этом проверяющего.
2. Корректность. Если доказывающий не знает утверждение, то он может обмануть проверяющего только с пренебрежимо малой вероятности.
3. Нулевое разглашение. Проверяющий, даже если он ведет себя нечестно, не узнает ничего кроме самого факта, что утверждение известно доказывающему.
Пещера нулевого знания
Хорошо поясняют доказательство с нулевым знанием Жан-Жак Кискатер и Луи Гиллу с помощью истории о пещере Али-Бабы (см. рисунок). Чтобы пройти сквозь пещеру, необходимо открыть дверь между C и D. Дверь открывается только тогда, когда кто-нибудь произносит волшебные слова. Пусть Пегги знает волшебные слова и хочет доказать это Виктору, не раскрывая самих слов.
Вот как происходит доказательство с нулевым знанием в данном случае:
1. Виктор находится в точке А.
2. Пегги проходит весь путь по пещере до двери либо по проходу C, либо по проходу D. Виктор не видит в какую сторону пошла Пегги. После того, как Пегги исчезнет в пещере, Виктор переходит в точку В.
3. Виктор кричит Пегги, чтобы она вышла из пещеры либо из левого прохода, либо из правого прохода.
4. Пегги, при необходимости используя волшебные слова, чтобы отпереть дверь, выходит из пещеры из того прохода, из которого просил ее выйти Виктор.
5. Пегги и Виктор повторяют этапы 1-4 некоторое количество раз.
В случае когда Пегги не знает секрета, то она не сможет обмануть Виктора, если этапы доказательства (аккредитации) повторяются несколько раз подряд. Так как она может выйти только из того прохода, в который она зашла, в каждом раунде протокола вероятность угадать, с какой стороны Виктор попросит ее выйти, составляет 50 %. Соответственно, ее вероятность обмануть Виктора также равна 50 %. Однако, вероятность обмануть его в двух раундах составит уже 25 %, а в n раундах у нее есть только один шанс из 2^n. Виктор может уверенно предположить, что если все n (n=10-20) раундов доказательства Пегги правильны, то она действительно знает тайные слова, открывающие дверь между точками С и D.
Если Виктор записывает все, что происходит на видеокамеру, то данная видеозапись не является доказательством для третьей стороны. Пегги и Виктор могли заранее договориться о том, откуда Виктор будет просить ее выйти. Тогда она будет каждый раз выходить из указанного Виктором места, не зная волшебных слов. С другой стороны, Виктор может подделать видеозапись, оставив в ней только удачные попытки Пегги, вырезав все остальное.
Следует отметить, что аналогия с пещерой не совсем верна. Так как для доказательства знания слов Пегги может просто входить с одной стороны, при этом Виктор видит в какую сторону она пошла, и выходить с другой. Однако, это протокол отлично описывает доказательство с нулевым знанием с математической точки зрения.
Протокол Фиата-Шамира
Одним из наиболее известных протоколов идентификации личности с помощью доказательства с нулевым знанием является протокол, предложенный Амосом Фиатом и Ади Шамиром, стойкость которого основывается на сложности извлечения квадратного корня по модулю достаточно большого составного числа n, факторизация которого неизвестна.
Предварительно, перед самим доказательством доверенный центр T выбирает и публикует модуль достаточно большого числа n = p*q, разложить на множители которое трудно. При этом p, q – простые числа и держатся в секрете. Каждый пользователь A выбирает секретное s из интервала (1, n−1) взаимно простое с n. Затем вычисляется открытый ключ v = s^2 (mod n).
Полученное v регистрируется центром доверия в качестве открытого ключа пользователя A, а значение s является секретом A. Именно знание этого секрета s необходимо доказать A стороне В без его разглашение за t раундов. Каждая аккредитация состоит из следующих этапов:
1. А выбирает случайное r из интервала (1, n−1) и отсылает x = r^2 (mod n) стороне B.
2. B случайно выбирает бит e (0 или 1) и отсылает его A.
3. А вычисляет y = r*s^e (mod n) и отправляет его обратно к B.
4. Сторона B проверяет равенство y^2 ≡ x*v^e (mod n). Если оно верно, то происходит переход к следующему раунду протокола, иначе доказательство не принимается.
Выбор е из множества предполагает, что если сторона А действительно знает секрет, то она всегда сможет правильно ответить, вне зависимости от выбранного e. Допустим, что А хочет обмануть B, выбирает случайное r и отсылает x = r^2 / v, тогда если е=0, то А удачно возвращает B y = r, в случае же е=1, А не сможет правильно ответить, т.к. не знает s, а извлечь квадратный корень из v по модулю n достаточно сложно.
Вероятность того, что пользователь А не знает секрета s, но убеждает в обратном проверяющего B будет оцениваться вероятностью равной p = =2^(–t), где t – число аккредитаций. Для достижения высокой достоверности его выбирают достаточно большим (t = 20 − 40). Таким образом, B удостоверяется в знании А тогда и только тогда, когда все t раундов прошли успешно.
Для того чтобы этот протокол корректно выполнялся, сторона А никогда не должна повторно использовать значение x. Если бы А поступил таким образом, а B во время другого цикла отправил бы А на шаге 2 другой случайный бит r, то B бы имел оба ответа А. После этого B может вычислить значение s, и ему будет известен секретный ключ Алисы.
Вывод
На централизованных платформах, таких как Facebook, Amazon и Google, наши данные продаются с целью получения прибыли, чтобы манипулировать нашим поведением с помощью рекламы.
В полностью открытых сетях блокчейн все наши действия записываются и публикуются. То, что предлагает доказательства с нулевым разглашением, является публичной и прозрачной сетью, которая защищает людей от подслушивающих устройств, а также комерчиских компаний которые сливают информацию.
Что такого особенного в этом протоколе?
Zcash - это первый широко распространенный пример использования и применения доказательств с нулевым разглашением в мире криптографии.
Монета конфиденциальности использует форму доказательства с нулевым разглашением, называемую zk-SNARKs, что означает «сжатый неинтерактивный аргумент знания с нулевым разглашением».
В базовых доказательствах с нулевым разглашением, которые мы обсуждали, проверяющие и верификаторы должны взаимодействовать в течение нескольких раундов, чтобы верификатор был убежден в честности проверяющего.
В zk-SNARKs взаимодействие убирается, поэтому доказательства становятся более сложными. Тем не менее, zk-SNARK также позволяют проверкам быть более эффективными и использовать меньше данных - жизненно важная функция в блокчейне, где память и пространство очень важны для поддержания сети на плаву.
В протоколе, основанном на zk-SNARK, должна быть «доверенная настройка» для запуска системы. Информация, используемая при запуске - если она попала в чужие руки - может быть использована для того, чтобы поставить под угрозу и повредить всю систему после ее развертывания.
В Zcash приватные ключи, используемые при запуске, и компьютеры, которые их обрабатывали, были уничтожены в ходе специальной церемонии.
Чем он отличается от других?
Стадия доверенной установки считается уязвимостью безопасности, потому что люди должны верить, что информация, использованная во время установки, была уничтожена должным образом.
StarkWare - это компания, разрабатывающая инструменты и программное обеспечение zk-STARKs, чтобы сделать блокчейны более приватными и масштабируемыми. Сооснователем был Алессандро Кьеза, один из исследователей, создавших zk-SNARKs.
Следующая загадка
Доказательство с нулевым разглашением (знанием) (Zero-knowledge proof) представляет собой криптографический протокол, позволяющий одной из сторон (проверяющему, стороне B) убедиться в том, что вторая сторона (доказывающая, сторона A) знает какое-либо утверждение, при этом проверяющий не получает никакой другой информации о самом утверждении. Другими словами, А доказывает знание секрета, не разглашая самого секрета.
Использовать доказательства с нулевым знанием для доказательства идентичности было впервые предложено Уриелем Файгом, Амосом Фиатом и Ади Шамиром. В данном случае пользователь доказывает знание своего закрытого ключа, который в данном случае выступает в роли секрета, не раскрывая его. Таким образом, он доказывает свою идентичность.
Доказательство с нулевым разглашением обладает тремя основными свойствами:
1. Полнота. Если доказывающий знает утверждение, то он сможет убедить в этом проверяющего.
2. Корректность. Если доказывающий не знает утверждение, то он может обмануть проверяющего только с пренебрежимо малой вероятности.
3. Нулевое разглашение. Проверяющий, даже если он ведет себя нечестно, не узнает ничего кроме самого факта, что утверждение известно доказывающему.
Пещера нулевого знания
Хорошо поясняют доказательство с нулевым знанием Жан-Жак Кискатер и Луи Гиллу с помощью истории о пещере Али-Бабы (см. рисунок). Чтобы пройти сквозь пещеру, необходимо открыть дверь между C и D. Дверь открывается только тогда, когда кто-нибудь произносит волшебные слова. Пусть Пегги знает волшебные слова и хочет доказать это Виктору, не раскрывая самих слов.
Вот как происходит доказательство с нулевым знанием в данном случае:
1. Виктор находится в точке А.
2. Пегги проходит весь путь по пещере до двери либо по проходу C, либо по проходу D. Виктор не видит в какую сторону пошла Пегги. После того, как Пегги исчезнет в пещере, Виктор переходит в точку В.
3. Виктор кричит Пегги, чтобы она вышла из пещеры либо из левого прохода, либо из правого прохода.
4. Пегги, при необходимости используя волшебные слова, чтобы отпереть дверь, выходит из пещеры из того прохода, из которого просил ее выйти Виктор.
5. Пегги и Виктор повторяют этапы 1-4 некоторое количество раз.
В случае когда Пегги не знает секрета, то она не сможет обмануть Виктора, если этапы доказательства (аккредитации) повторяются несколько раз подряд. Так как она может выйти только из того прохода, в который она зашла, в каждом раунде протокола вероятность угадать, с какой стороны Виктор попросит ее выйти, составляет 50 %. Соответственно, ее вероятность обмануть Виктора также равна 50 %. Однако, вероятность обмануть его в двух раундах составит уже 25 %, а в n раундах у нее есть только один шанс из 2^n. Виктор может уверенно предположить, что если все n (n=10-20) раундов доказательства Пегги правильны, то она действительно знает тайные слова, открывающие дверь между точками С и D.
Если Виктор записывает все, что происходит на видеокамеру, то данная видеозапись не является доказательством для третьей стороны. Пегги и Виктор могли заранее договориться о том, откуда Виктор будет просить ее выйти. Тогда она будет каждый раз выходить из указанного Виктором места, не зная волшебных слов. С другой стороны, Виктор может подделать видеозапись, оставив в ней только удачные попытки Пегги, вырезав все остальное.
Следует отметить, что аналогия с пещерой не совсем верна. Так как для доказательства знания слов Пегги может просто входить с одной стороны, при этом Виктор видит в какую сторону она пошла, и выходить с другой. Однако, это протокол отлично описывает доказательство с нулевым знанием с математической точки зрения.
Протокол Фиата-Шамира
Одним из наиболее известных протоколов идентификации личности с помощью доказательства с нулевым знанием является протокол, предложенный Амосом Фиатом и Ади Шамиром, стойкость которого основывается на сложности извлечения квадратного корня по модулю достаточно большого составного числа n, факторизация которого неизвестна.
Предварительно, перед самим доказательством доверенный центр T выбирает и публикует модуль достаточно большого числа n = p*q, разложить на множители которое трудно. При этом p, q – простые числа и держатся в секрете. Каждый пользователь A выбирает секретное s из интервала (1, n−1) взаимно простое с n. Затем вычисляется открытый ключ v = s^2 (mod n).
Полученное v регистрируется центром доверия в качестве открытого ключа пользователя A, а значение s является секретом A. Именно знание этого секрета s необходимо доказать A стороне В без его разглашение за t раундов. Каждая аккредитация состоит из следующих этапов:
1. А выбирает случайное r из интервала (1, n−1) и отсылает x = r^2 (mod n) стороне B.
2. B случайно выбирает бит e (0 или 1) и отсылает его A.
3. А вычисляет y = r*s^e (mod n) и отправляет его обратно к B.
4. Сторона B проверяет равенство y^2 ≡ x*v^e (mod n). Если оно верно, то происходит переход к следующему раунду протокола, иначе доказательство не принимается.
Выбор е из множества предполагает, что если сторона А действительно знает секрет, то она всегда сможет правильно ответить, вне зависимости от выбранного e. Допустим, что А хочет обмануть B, выбирает случайное r и отсылает x = r^2 / v, тогда если е=0, то А удачно возвращает B y = r, в случае же е=1, А не сможет правильно ответить, т.к. не знает s, а извлечь квадратный корень из v по модулю n достаточно сложно.
Вероятность того, что пользователь А не знает секрета s, но убеждает в обратном проверяющего B будет оцениваться вероятностью равной p = =2^(–t), где t – число аккредитаций. Для достижения высокой достоверности его выбирают достаточно большим (t = 20 − 40). Таким образом, B удостоверяется в знании А тогда и только тогда, когда все t раундов прошли успешно.
Для того чтобы этот протокол корректно выполнялся, сторона А никогда не должна повторно использовать значение x. Если бы А поступил таким образом, а B во время другого цикла отправил бы А на шаге 2 другой случайный бит r, то B бы имел оба ответа А. После этого B может вычислить значение s, и ему будет известен секретный ключ Алисы.
Следующая загадка
В доказательствах с нулевым разглашением основные роли выполняют проверяющие и верификаторы. Проверяющий должен доказать, что они знают секрет. Верификатор должен быть в состоянии проверить, что проверяющий говорит правду.
Это работает, потому что верификатор просит проверяющего сделать то, что может быть сделано, только если проверяющий определенно знает секрет.
Если проверяющий угадает, он или она в конечном итоге окажется ошибочным в результате проверок верификатора. Если секрет известен, то проверяющий будет проходить проверку верификаторов каждый раз без проблем.
Это как когда банк или учреждение запрашивает у вас письма с секретным словом для подтверждения вашей личности. Вы не говорите банку, что находится на вашем банковском счете, вы просто говорите им, что знаете последовательность секретной фразы.
Читайте также: