Одна из основных задач криптографии представляет собой двустороннюю интерактивную игру, в которой один участник (доказывающая сторона) доказывает другому участнику (проверяющей стороне) истинность утверждения, не раскрывая сущности доказательства. В этом случае проверяющий не может самостоятельно оценить истинность утверждения, поскольку ему неизвестна информация, доступная доказывающему. Эта игра называется протоколом (системой) интерактивного доказательства или IP-протоколом (interactive proof - IP). Доказательство, осуществляемое IP-протоколом, можно назвать “секретным доказательством” (“proof in the dark”). Секретность этого доказательства состоит в том, что, во-первых, проверяющая сторона, убедившись в истинности доказываемого утверждения, не способна самостоятельно повторить доказательство, и, во-вторых, после завершения протокола никто из посторонних не способен понять ни одного сообщения, которыми обменивались доказывающая и проверяющая стороны.
Представим себе, что утверждение, которое необходимо доказать, не раскрывая сущности доказательства, является решением какой-либо знаменитой нерешенной математической задачи. В этом случае доказывающая сторона, опасающаяся плагиата, может пожелать скрыть технические детали доказательства от потенциально нечестного рецензента. Для этого она должна провести “секретное” доказательство, убедив рецензента (играющего роль проверяющей стороны в IP-протоколе) в корректности выводов, не давая никакой дополнительной информации.
Во многих реальных приложениях существуют намного более серьезные основания для проведения “секретных” доказательств. Как правило, IP-протоколы применяются для аутентификации сущностей. В отличие от обычных протоколов аутентификации , в которых пользователи ставят цифровые подписи, в IР-протоколе доказывающая сторона, подлежащая аутентификации , не желает, чтобы сообщения стали доступными кому-либо, кроме проверяющей стороны, и выполняет “секретную” аутентификацию . Кроме того, IP-протоколы часто применяются для того, чтобы доказать, что часть скрытой информации имеет определенную структуру. Это необходимо в некоторых секретных приложениях (например, при проведении электронных аукционов), в которых скрытый номер (лот) должен находиться в допустимом диапазоне (например, необходимо доказать, что х > у без раскрытия значений и , представляющих собой предложения цены).
Рассматривая IP-протоколы, необходимо изучить два вопроса.
- Вопрос 1. Сколько информации получит проверяющая сторона в ходе интерактивного доказательства ?
- Вопрос 2. Сколько раундов должна выполнить доказывающая сторона, чтобы убедить проверяющего?
Идеальным ответом на первый вопрос был бы “нисколько”, или “нуль”. IP- протокол, обладающий таким свойством, называется протоколом с нулевым разглашением или ZK-протоколом (zero-knowledge - ZK). Второй вопрос важен не только для практических приложений, но и для теории вычислительной сложности, поскольку решение этой проблемы связано с получением более низкой оценки сложности.
История развития
Доказательство нулевым разглашением был придумано и разработано следующими учеными: Шафи Гольдвассером, Сильвио Микалием и Чарльз Реккофом, и опубликовано ими в статье «Знание и сложность интерактивной системы с доказательством» в 1985 году. Эта работа представила иерархию интерактивных систем с доказательством, основываясь на объеме информации о доказательстве, которой необходимо передать от доказывающего до проверяющего. Ими так же было предложено первое доказательство конкретно поставленного доказательства с нулевым разглашением - квадратичного вычета по модулю m. Впоследствии, дополнив свою работу, они выиграли первую премию Геделя в 1993 году.
Продолжение...
Нулевое разглашение
Вычислительная модель
Обозначим основную модель протокола интерактивных доказательств через (Р,V), где Р - доказывающая (prover), а V - проверяющая сторона (verifier). Как правило, протокол (Р,V) предназначен для проверки принадлежности определенного предложения языку, заданному над алфавитом {0,1}*.
Пусть L - язык над алфавитом {0,1}*. Стороны Р и V получают образец хϵL, представляющий собой общие входные данные (common input). Доказательство принадлежности образца обозначается как (Р,V)(x). Обе стороны протокола связаны каналом связи, через который они обмениваются информацией.
Результат работы протокола записывается в следующем виде: (Р,V)(x) ϵ {Принять, Отклонить}.
Эти два значения означают, что проверяющая сторона либо подтверждает, либо опровергает утверждение хϵL, высказанное доказывающей стороной Р. Поскольку система (Р,V) является вероятностной, при каждом х результат (Р,V)(x) является случайной величиной, зависящей от общих входных данных х, закрытых входных данных (private input) пользователя Р и некоторых случайных входных данных (random input), общих для пользователей Р и Q.
Поскольку протокол (Р,V) является двусторонней игрой, естественно предположить, что каждая сторона стремится получить дополнительное преимущество. С одной стороны, доказывающая сторона Р должна быть заинтересована в результате принятия x, даже если оно не принадлежит L. Доказывающая сторона, руководствующаяся такой жульнической стратегией (cheating prover), обозначается как Р’. С другой стороны, проверяющая сторона V должна быть заинтересована в раскрытии информации о закрытых входных данных игрока Р. Проверяющая сторона, следующая такой нечестной стратегии (dishonest verifier), обозначается как V’.
Предположим, что на вопрос 1 существует идеальный ответ (Р,V) - протокол с нулевым разглашением, т.е. пользователь V (или V’) убеждается в корректности утверждения пользователя Р, не узнав ничего нового о его закрытых входных данных.
Для того чтобы протокол (Р,V) обладал этим свойством, необходимо ограничить вычислительную мощь пользователя V (или V’) полиномом, зависящим от размера его входной информации. Очевидно, что без этого ограничения нельзя гарантировать нулевое разглашение, поскольку пользователь V, обладающий неограниченными вычислительными ресурсами может самостоятельно раскрыть секретные входные данные пользователя Р.
Формальное определение протоколов интерактивного доказательства
Дадим определение протокола интерактивного доказательства .
Пусть L - язык, заданный над алфавитом (0,1}*. IР-протокол (Р,V) называется системой интерактивного доказательства для языка L, если
и
где числа Ɛ и ϐ являются константами, удовлетворяющими условиям
Ɛϵ(1/2;1], ϐϵ Тематики защита информации Синонимы НДНР EN non iterative zero knowledge proofNIZK … Справочник технического переводчика
Криптография - Немецкая криптомашина Lorenz использовалась во время Второй мировой войны для шифрования самых секретных сообщений Криптография (от др. греч … Википедия
Список алгоритмов - Эта страница информационный список. Основная статья: Алгоритм Ниже приводится список алгоритмов, группированный по категориям. Более детальные сведения приводятся в списке структур данных и … Википедия
Криптограф - Немецкая криптомашина Lorenz, использовалась во время Второй мировой войны для шифрования самых секретных сообщений Криптография (от греч. κρυπτός скрытый и γράφω пишу) наука о математических методах обеспечения конфиденциальности… … Википедия
Программируемые алгоритмы - Служебный список статей, созданный для координации работ по развитию темы. Данное предупреждение не устанавл … Википедия
SRP - Secure Remote Password Protocol (SRPP) протокол парольной аутентификации, устойчивый к прослушиванию и MITM атаке и не требующий третьей доверенной стороны. SRP содержит некоторые элементы из других протоколов обмена ключами и идентификации … Википедия
Протокол Фиата - Протокол Фиата Шамира это один из наиболее известных протоколов идентификации с нулевым разглашением (Zero knowledge protocol). Протокол был предложен Амосом Фиатом (англ. Amos Fiat) и Ади Шамиром (англ. Adi Shamir) Пусть А… … Википедия
Протокол Фиата-Шамира - Протокол Фиата Шамира это один из наиболее известных протоколов идентификации с нулевым разглашением (Zero knowledge protocol). Протокол был предложен Амосом Фиатом(англ. Amos Fiat) и Ади Шамиром(англ. Adi Shamir) Пусть А знает некоторый… … Википедия
Доказательство с нулевым разглашением (знанием) (Zero-knowledge proof) представляет собой криптографический протокол, позволяющий одной из сторон (проверяющему, стороне B) убедиться в том, что вторая сторона (доказывающая, сторона A) знает какое-либо утверждение, при этом проверяющий не получает никакой другой информации о самом утверждении. Другими словами, А доказывает знание секрета, не разглашая самого секрета.
Использовать доказательства с нулевым знанием для доказательства идентичности было впервые предложено Уриелем Файгом, Амосом Фиатом и Ади Шамиром. В данном случае пользователь доказывает знание своего закрытого ключа, который в данном случае выступает в роли секрета, не раскрывая его. Таким образом, он доказывает свою идентичность.
Доказательство с нулевым разглашением обладает тремя основными свойствами:
1. Полнота. Если доказывающий знает утверждение, то он сможет убедить в этом проверяющего.
2. Корректность. Если доказывающий не знает утверждение, то он может обмануть проверяющего только с пренебрежимо малой вероятности.
3. Нулевое разглашение. Проверяющий, даже если он ведет себя нечестно, не узнает ничего кроме самого факта, что утверждение известно доказывающему.
Доказательство имеет форму интерактивного протокола. Это означает, что сторона B задает ряд вопросов доказывающему, которые если знает секрет, то ответит на все вопросы правильно. Если секрет стороне A неизвестен, но она хочет убедить в обратном проверяющего, у нее есть некоторая вероятность (может быть 50 %, как в примерах в данном топике) ответить правильно на вопрос. Однако, после некоторого количества вопросов (10 - 20) проверяющий с достаточно высокой вероятностью убеждается в том, что доказывающий не знает секрет. При этом, ни один из ответов не дает никаких сведений о самом секрете.
Пещера нулевого знания
Хорошо поясняют доказательство с нулевым знанием Жан-Жак Кискатер и Луи Гиллу с помощью истории о пещере Али-Бабы (см. рисунок). Чтобы пройти сквозь пещеру, необходимо открыть дверь между 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, и ему будет известен секретный ключ Алисы.
