Протокол доказательства с нулевым разглашением c. Протокол доказательства с нулевым разглашением: техническое описание. Протокол доказательства с нулевым разглашением: как это работает
Доказательство с нулевым разглашением должно обладать тремя свойствами:
- Полнота : если утверждение действительно верно, то доказывающий убедит в этом проверяющего.
- Корректность : если утверждение неверно, то даже нечестный доказывающий не сможет убедить проверяющего за исключением пренебрежимо малой вероятности.
- Нулевое разглашение : если утверждение верно, то любой даже нечестный проверяющий не узнает ничего кроме самого факта, что утверждение верно.
Общая структура доказательств с нулевым разглашением
Каждый раунд или аккредитация доказательства состоит из трёх этапов. Схематично их можно изобразить следующим образом:
Сначала A выбирает из заранее определенного множества некоторый элемент, который становится её секретом (закрытый ключ). На основе этого элемента вычисляется, а затем публикуется открытый ключ. Знание секрета определяет множество вопросов, на которые А всегда сможет дать правильные ответы. Затем A выбирает случайный элемент из множества, по определенным правилам (в зависимости от конкретного алгоритма) вычисляет доказательство и затем отсылает его B . После этого B выбирает из всего множества вопросов один и просит A ответить на него (вызов ). В зависимости от вопроса, А посылает B ответ . Полученной информации B достаточно, чтобы проверить действительно ли А владеет секретом. Раунды можно повторять сколько угодно раз, пока вероятность того, что A «угадывает» ответы не станет достаточно низкой.
Такая техника называется также «разрезать и выбрать» (cut-and-choose).
Пример
Назовем проверяющую сторону Петей, а доказывающую сторону Димой (в англоязычной литературе обычно используются пары Peggy (от prover ) и Victor (от verifier ). Допустим Диме известен Гамильтонов цикл в большом графе G . Пете известен граф G , но он не знает гамильтонова цикла в нём. Дима хочет доказать Пете, что он знает гамильтонов цикл, не выдавая при этом ни самого цикла, ни какой-либо информации о нём (возможно Петя хочет купить этот гамильтонов цикл у Димы, но перед этим удостовериться, что он у Димы действительно есть).
Для этого Петя и Дима совместно выполняют несколько раундов протокола:
В каждом раунде Петя выбирает новый случайный бит, который неизвестен Диме, поэтому чтобы Дима мог ответить на оба вопроса, нужно чтобы H был в самом деле изоморфен G и Дима должен знать гамильтонов цикл в H (а значит также и в G ). Поэтому после достаточного числа раундов, Петя может быть уверен в том, что у Димы действительно есть гамильтонов цикл в G . С другой стороны, Дима не раскрывает никакой информации о гамильтоновом цикле в G . Более того, Пете сложно будет доказать кому-либо ещё, что он сам или Дима знает гамильтонов цикл в G .
Предположим, что у Димы нет гамильтонова цикла в G и он хочет обмануть Петю. Тогда Диме необходим неизоморфный G граф G" , в котором он всё-таки знает гамильтонов цикл. В каждом раунде он может передавать Пете либо H" - изоморфный G" , либо H - изоморфный G . Если Петя попросит доказать изоморфизм и был передан H , то обман не вскроется. Аналогично, если он просит показать гамильтонов цикл и был передан H" . В таком случае вероятность того, что Дима все-таки обманет Петю после n раундов, равна 1/2 n , что может быть меньше любой заранее заданной величы при достаточном числе раундов.
Предположим, что Петя не узнал гамильтонов цикл, но хочет доказать Васе, что Дима его знает. Если Петя, например, заснял на видео все раунды протокола, Вася едва ли ему поверит. Вася может предположить, что Петя и Дима в сговоре и в каждом раунде Петя заранее сообщал Диме свой выбор случайного бита, чтобы Дима мог передавать ему H для проверок изоморфизма и H" для проверок гамильтонова цикла. Таким образом без участия Димы доказать, что он знает гамильтонов цикл, можно лишь доказав, что во всех раундах протокола выбирались действительно случайные биты.
Злоупотребления
Предложено несколько способов злоупотребления доказательством с нулевым разглашением:
См. также
- Протокол Гиллу-Кискатра
Литература
- A. Menezes, P.van Oorschot, S. Vanstone. Handbook of Applied Cryptography. - CRC Press, 1996. - 816 с. - ISBN 0-8493-8523-7
- Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. - М .: Триумф, 2002. - 816 с. - 3000 экз. - ISBN 5-89392-055-4
Wikimedia Foundation . 2010 .
- Фонвизина, Наталья Дмитриевна
- Чужумово
Смотреть что такое "Доказательство с нулевым разглашением" в других словарях:
доказательство с нулевым разглашением конфиденциальной информации - Непроницаемое доказательство знания; доказательство обладания какой либо информацией, без разглашения этой информации. Тематики защита информации EN zero knowledge proof …
итеративное доказательство с нулевым разглашением конфиденциальной информации - — Тематики защита информации EN zero knowledge iterative proofZKIP … Справочник технического переводчика
не итеративное доказательство с нулевым разглашением конфиденциальной информации - НДНР — [] Тематики защита информации Синонимы НДНР 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, и ему будет известен секретный ключ Алисы.
Заключение
Для таких реализаций, как интеллектуальные карточки, описанные протокол Фиата-Шамира не слишком подходит, так как обмены с внешним миром требуют времени, а хранение данных для каждой аккредитации может быстро исчерпать ограниченные возможности карточки. Поэтому Гиллу и Кискатр разработали алгоритм идентификации с нулевым знанием, больше подходящий для подобных приложений. Обмены между Пегги и Виктором, а также параллельные аккредитации в каждом обмене сведены к абсолютному минимуму: для каждого доказательства существует только один обмен, в котором - только одна аккредитация. Существует также схема Шнорра, которая является альтернативой схеме Гиллу-Кискатра и Фиата-Шамира. Если тема понравиться, то я напишу про них в следующем своем топике.Использование доказательства с нулевым разглашением конфиденциальной информации можно пояснить на конкретном примере. Предположим, что имеется пещера. Вход в пещеру находится в точке А, а в точке В пещера разветвляется на две половины - С и D. У пещеры есть секрет: только тот, кто знает волшебные слова, может открыть дверь, расположенную между С и D.
Антону волшебные слова известны, Борису - нет. Антон хочет доказать Борису, что знает волшебные слова, но так, чтобы Борис по-прежнему оставался в неведении относительно этих слов. Тогда Антон может воспользоваться следующим протоколом:
1. Борис стоит в точке А.
2. По своему выбору Антон подходит к двери либо со стороны точки С,
либо со стороны точки D.
3. Борис перемещается в точку В.
4. Борис приказывает Антону появиться или через левый проход к двери,
или через правый.
5. Антон подчиняется приказу Бориса, в случае необходимости используя
волшебные слова, чтобы пройти через дверь.
6. Шаги 1-5 повторяются n раз, где n - параметр протокола.
Допустим, что у Бориса есть видеокамера, с помощью которой он фиксирует все исчезновения Антона в недрах пещеры и все его последующие появления. Если Борис покажет записи всех n экспериментов, произведенных им совместно с Антоном, могут ли эти записи послужить доказательством знания Антоном волшебных слов для другого человека (например, для Владимира)?
Вряд ли. Владимир никогда не сможет удостовериться в том, что Антон каждый раз предварительно не сообщал Борису о своих намерениях, чтобы потом Борис приказывал ему выходить именно с той стороны двери, с какой Антон зашел. Или что из сделанной видеозаписи не вырезаны все неудачные эксперименты, в ходе которых Антон не смог выполнить распоряжения Бориса.
Это означает, что Борис не в состоянии убедить Владимира, лично не присутствовавшего при проведении экспериментов в пещере, в том, что Антон действительно подтвердил свое знание секрета. А значит использованный Антоном протокол доказательства характеризуется именно нулевым разглашением конфиденциальной информации. Если Антон не знает волшебные слова, открывающие дверь в пещере, то, наблюдая за Антоном, не сможет ничего узнать и Борис. Если Антону известны волшебные слова, то Борису не поможет даже подробная видеозапись проведенных экспериментов. Во-первых, поскольку при ее просмотре Борис увидит только то, что уже видел живьем. А во-вторых, потому что практически невозможно отличить сфальсифицированную Борисом видеозапись от подлинной.
Протокол доказательства с нулевым разглашением срабатывает в силу того, что не зная волшебных слов, Антон может выходить только с той стороны, с которой зашел. Следовательно лишь в 50% всех случаев Антон сумеет обмануть Бориса, догадавшись, с какой именно стороны тот попросит его выйти. Если количество экспериментов равно n, то Антон успешно пройдет все испытания только в одном случае из 2 n . На практике можно ограничиться n=16. Если Антон правильно исполнит приказ Бориса во всех 16-ти случаях, значит он и правда знает секрет волшебных слов.
Пример с пещерой является наглядным, но имеет существенный изъян. Борису значительно проще проследить, как в точке В Антон поворачивает в одну сторону, а потом появляется с противоположной стороны. Протокол доказательства с нулевым разглашением здесь попросту не нужен.
Поэтому предположим, что Антону известны не какие-то там волшебные слова, типа “Сезам, откройся”. Нет, Антон владеет более интересной информацией - он первым сумел найти решение этой труднорешаемой задачи. Чтобы доказать данный факт Борису, Антону совсем не обязательно всем и каждому демонстрировать свое решение. Ему достаточно применить следующий протокол доказательства с нулевым разглашением конфиденциальной информации:
1. Антон использует имеющуюся у него информацию и сгенерированное
случайное число, чтобы свести труднорешаемую задачу к другой труднорешаемой задаче, изоморфной исходной задаче. Затем Антон решает эту новую задачу.
2. Антон задействует протокол предсказания бита для найденного на
шаге 1 решения, чтобы впоследствии, если у Бориса возникнет необходимость ознакомиться с этим решением, Борис мог бы достоверно убедиться, что предъявленное Антоном решение действительно было получено им на шаге 1.
3. Антон показывает новую труднорешаемую задачу Борису,
4. Борис просит Антона или доказать, что две труднорешаемые задачи
(старая и новая) изоморфны, или предоставить решение, которое Антон должен был найти на шаге 1, и доказать, что это действительно решение задачи, к которой Антон свел исходную задачу на том же шаге.
5. Антон выполняет просьбу Бориса.
6. Антон и Борис повторяют шаги 1-6 n раз, где n - параметр
протокола.
Труднорешаемые задачи, способ сведения одной задачи к другой, а также случайные числа должны по возможности выбираться так, чтобы у Бориса не появилось никакой информации относительно решения исходной задачи даже после многократного выполнения шагов протокола.
Не все труднорешаемые задачи могут быть использованы при доказательстве с нулевым разглашением конфиденциальной информации, однако большинство из них вполне пригодны для таких целей. Примерами могут служить отыскание в связном графе цикла Гамильтона (замкнутого пути, проходящего через все вершины графа только один раз) и определение изоморфизма графов (два графа изоморфны, если они отличаются только названиями своих вершин).
Предположим, что Алиса знает доказательство некоторой теоремы и желает убедить Боба в том, что теорема верна. Конечно, Алиса может просто передать доказательство Бобу на проверку. Но тогда впоследствии Боб сможет сам, без помощи Алисы, доказывать третьим лицам эту теорему. А может ли Алиса убедить Боба так, чтобы он не получил при этом никакой информации, которая помогла бы ему восстановить доказательство теоремы? Этим двум, казалось бы взаимно исключающим требованиям, удовлетворяют протоколы доказательства с нулевым разглашением. Последнее понятие было введено Гольдвассер, Микали и Ракоффом в 1985 г. .
Рассматривается следующая модель протокола. В распоряжении Алисы и Боба имеются вероятностные машины Тьюринга соответственно. Вычислительные ресурсы, которые может использовать Алиса, неограничены, в то время как машина V работает за полиномиальное время. Машины имеют общую коммуникационную ленту для обмена сообщениями. После записи сообщения на коммуникационную ленту машина переходит в состояние ожидания и выходит из него, как только на ленту будет записано ответное сообщение. Машины имеют также общую входную ленту, на которую записано входное слово х. Утверждение, которое доказывает Алиса, суть где некоторый фиксированный (известный и Алисе, и Бобу) язык. Чтобы избежать тривиальности, язык должен быть трудным (например, NP-полным), иначе Боб сможет самостоятельно проверить, что По существу, протокол доказательства состоит в том, что Боб, используя случайность, выбирает некоторые вопросы, задает их Алисе и проверяет правильность ответов. Выполнение протокола завершается, когда машина V останавливается, при этом она выдает 1, если доказательство принято, и 0 - в противном случае.
Пусть две интерактивные, т. е. взаимодействующие через общую коммуникационную ленту, вероятностные машины Тьюринга. Через обозначается случайная величина - выходное слово машины А, когда А к В работают на входном слове х. Через обозначается длина слова х.
Определение 4. Интерактивным доказательством для языка называется пара интерактивных машин Тьюринга такая, что выполняются следующие два условия.
1. (Полнота). Для всех
2. (Корректность). Для любой машины Тьюринга для любого полинома и для всех достаточно большой длины
Полнота означает, что если входное слово принадлежит языку и оба участника, и Алиса, и Боб, следуют протоколу, то доказательство будет всегда принято. Требование корректности защищает Боба от нечестной Алисы, которая пытается обмануть его, «доказывая» ложное утверждение. При этом Алиса может каким угодно образом отклоняться от действий, предписанных протоколом, т. е. вместо машины Тьюринга использовать любую другую машину Требуется, чтобы вероятность обмана была в любом случае пренебрежимо малой.
Определение 5. Интерактивный протокол доказательства для языка называется доказательством с абсолютно нулевым разглашением, если, кроме условий 1 и 2, выполнено еще и следующее условие.
3. (Свойство нулевого разглашения). Для любой полиномиальной вероятностной машины Тьюринга V существует вероятностная машина Тьюринга работающая за полиномиальное в среднем время, и такая, что для всех
Машина называется моделирующей машиной для Предполагается, что математическое ожидание времени ее работы ограничено полиномом от длины х. Это означает, что в принципе может, в зависимости от того, какие значения примут используемые в ее работе случайные переменные, работать достаточно долго. Но вероятность того, что время ее работы превысит некоторую полиномиальную границу, мала. Для каждой машины V строится своя моделирующая машина; последняя может использовать V как подпрограмму. Через обозначается случайная величина - выходное слово машины когда на входе она получает слово х.
Свойство нулевого разглашения защищает Алису от нечестного Боба, который, произвольно отклоняясь от действий, предписанных протоколом (используя V вместо V), пытается извлечь из его выполнения дополнительную информацию. Условие 3 означает, что Боб может при этом получить только такую информацию, которую он смог бы вычислить и самостоятельно выполнения протокола) за полиномиальное время.
Приведем в качестве примера протокол доказательства с абсолютно нулевым разглашением для языка из работы Гольдрайха, Микали и Вигдерсона . Входным словом является пара графов и Здесь множество вершин, которое можно отождествить с множеством натуральных чисел множества ребер такие, что Графы называются изоморфными, если существует перестановка на множестве такая, что тогда и только тогда, когда (обозначается Задача распознавания изоморфизма графов - хорошо известная математическая задача, для которой на данный момент не известно полиномиальных алгоритмов. С другой стороны, неизвестно, является ли эта задача NP-полной, хотя есть веские основания предполагать, что не является.
Протокол IG
Пусть изоморфизм между Следующие четыре шага выполняются в цикле раз, каждый раз с независимыми случайными величинами.
1. Р выбирает случайную перестановку на множестве вычисляет и посылает этот граф
2. V выбирает случайный бит а и посылает его
3. Если то посылает V перестановку в противном случае - перестановку о
4. Если перестановка, полученная V, не является изоморфизмом между то V останавливается и отвергает доказательство. В противном случае выполнение протокола продолжается.
Если проверки п. 4 дали положительный результат во всех циклах, то V принимает доказательство.
Заметим, что если в протоколе IG машина получает изоморфизм в качестве дополнительного входного слова, то ей для выполнения протокола не требуются неограниченные вычислительные ресурсы. Более того, в этом случае может быть полиномиальной вероятностной машиной Тьюринга.
Теорема 2 (). Протокол IG является доказательством с абсолютно нулевым разглашением для языка ИЗОМОРФИЗМ ГРАФОВ.
Полнота протокола IG очевидна.
Для доказательства корректности достаточно заметить, что бит а, который V выбирает на шаге 2, указывает для какого из графов - или требуется продемонстрировать изоморфизм с графом Если не изоморфны, то может быть изоморфен, в лучшем случае, одному из них. Поэтому проверка п. 4 даст положительный результат с вероятностью 1/2 в одном цикле и с вероятностью во всех циклах.
Доказательство свойства нулевого разглашения значительно сложнее. Поэтому мы воспроизводим только основную идею. Прежде всего, заметим, что основная задача машины V - получить максимально возможную информацию об изоморфизме между Естественно предположить, что она, в отличие от V, будет выдавать в качестве выходного слова не один бит, а всю полученную в результате выполнения протокола информацию, включая содержимое своей случайной ленты, графы и перестановки, полученные соответственно на шагах 1 и 3 протокола IG. Моделирующая машина должна уметь строить такие же случайные строки, графы и перестановки, не зная при этом изоморфизм Поэтому пытается угадать тот бит а, который будет запросом машины V на шаге 2. Для этого выбирает случайный бит случайную перестановку и вычисляет Далее запоминает состояние машины V (включая содержимое случайной ленты) и вызывает ее как подпрограмму, подавал ей на вход граф Ответом машины V будет некоторый бит а. Если то моделирование в данном цикле завершено успешно, поскольку может продемонстрировать требуемый изоморфизм. Если же а то восстанавливает ранее сохраненное состояние машины V и повторяет попытку.
Если в определении свойства нулевого разглашения заменить равенство случайных величин требованием, чтобы их распределения вероятностей «почти не отличались», то получится другая разновидность доказательств - доказательства со статистически нулевым разглашением.
Еще один тип - доказательства с вычислительно нулевым разглашением. В этом случае требуется, чтобы моделирующая машина создавала распределение вероятностей, которое неотличимо от никаким полиномиальным вероятностным алгоритмом (неотличимость здесь определяется аналогично тому, как это делалось в определении псевдослучайного генератора).
Подчеркнем особо, что во всех трех определениях нулевого разглашения условия накладываются на действия моделирующей машины только на тех словах, которые принадлежат языку.
Помимо интереса к доказательствам с нулевым разглашением как к нетривиальному математическому объекту, они исследуются также и в связи с практическими приложениями. Наиболее естественный и важный тип таких приложений - протоколы аутентификации (см. главу 3). С помощью такого протокола Алиса может доказать Бобу свою аутентичность.
Предположим, например, что Алиса - это интеллектуальная банковская карточка, в которой реализован алгоритм а Боб - это компьютер банка, выполняющий программу Прежде чем начать выполнение каких-либо банковских операций, банк должен убедиться в подлинности карточки и идентифицировать ее владельца, или, говоря на языке криптографии, карточка должна пройти аутентификацию. В принципе для этой цели можно использовать приведенный выше протокол IG. В этом случае в памяти банковского компьютера хранится пара графов сопоставленная Алисе, а на интеллектуальной карточке - та же пара графов и изоморфизм Предполагается, что, кроме Алисы, этот изоморфизм никто не знает (кроме, быть может, Боба) и поэтому с помощью протокола IG карточка доказывает свою аутентичность. При этом свойство полноты означает, что карточка наверняка докажет свою аутентичность. Свойство корректности защищает интересы банка от злоумышленника, который, не являясь клиентом банка, пытается пройти аутентификацию, используя фальшивую карточку. Свойство нулевого разглашения защищает клиента от злоумышленника, который, подслушав одно или более выполнений протокола аутентификации данной карточки, пытается пройти аутентификацию под именем Алисы. Конечно, в данном случае бессмысленно доказывать, что пара графов принадлежит языку ИЗОМОРФИЗМ ГРАФОВ, поскольку она заведомо выбирается из этого языка. Вместо этого Алиса доказывает, что она знает изоморфизм Интерактивные доказательства такого типа называются доказательствами знания.
Для практического применения очень важным свойством протокола IG, как и других протоколов доказательства знания, является то, что алгоритм получивший в качестве дополнительного входа изоморфизм работает за полиномиальное время. Вместо протокола IG можно использовать, вообще говоря, любое другое доказательство с нулевым разглашением, в котором алгоритм обладает этим свойством. Но для реальных приложений протокол IG, как и большинство подобных протоколов, не эффективен: большое количество циклов, слишком длинные сообщения и т. д. Поиск более эффективных доказуемо стойких протоколов - одно из основных направлений исследований в данной области.
Пусть задана интерактивная система доказательства (P,V,S).
В определении интерактивной системы доказательства ранее не предполагалось, что V может быть противником (предполагалась только возможность существования нечестного участника Р"). Но V может оказаться противником, который хочет выведать у Р какую- либо новую полезную информацию об утверждении S. В этом слу-чае Р может не хотеть, чтобы это случилось в результате работы
протокола интерактивной системы доказательства. Таким
28 Запечников С. В. Криптографические протоколы и их прішеиеиие
образом приходим к идее протокола доказательства с нулевым раз-глашением знания (zero-knowledge proof). Нулевое разглашение зна-ния подразумевает, что в результате работы протокола интерактивной системы доказательства V не увеличит свои знания об утвер-ждении S, или, другими словами, не сможет извлечь никакой информации о том, почему S истинно.
Как и ранее, в протоколе предварительно формулируется неко-торое утверждение S, например о том, что некоторый объект w об-ладает свойством L: we L. В ходе протокола Р и V обмениваются сообщениями. Каждый из них может генерировать случайные числа и использовать их в своих вычислениях. В конце протокола V дол-жен вынести свое окончательное решение о том, является ли S ис-тинным или ложным.
Цель Р всегда состоит в том, чтобы убедить V в том, что S ис-тинно, независимо от того, истинно ли оно на самом деле или нет, т. е. Р может быть активным противником, а задача V - проверять аргументы Р. Цель участника V заключается в том, чтобы вынести решение, является ли S истинным или ложным. Как и ранее, V имеет полиномиально ограниченные вычислительные возможности, а именно время его работы ограничено некоторым полиномом от
длины доказываемого утверждения: tРассмотрим теперь примеры протоколов доказательства с нулевым разглашением знания.
1. «Задача о пещере Али-Бабы». Имеется пещера, план которой показан на рис. 1.2. Пещера имрет дверь с секретом между точками С и D. Каждый, кто знает волшебные слова, может открыть эту дверь и пройти из С в D или наоборот. Для всех остальных оба хода пещеры ведут в тупик.
Пусть Р знает секрет пещеры. Он хочет доказать V знание этого секрета, не разглашая волшебные слова. Вот протокол их общения:
V находится в точке А;
Р заходит в пещеру и добирается либо до точки С, либо до точки D\
После того как Р исчезает в пещере, V приходит в точку В, не зная, в какую сторону пошел Р\
V зовет Р и просит его выйти либо из левого, либо из правого коридора пещеры согласно желанию V;
Р выполняет это, открывая при необходимости дверь, если, конечно, он знает волшебные слова;
Р и V повторяют шаги (1) - (5) п раз.
После п раундов протокола вероятность сократится до 1/2".
2. Доказательство изоморфизма графов. Р хочет доказать V изо-морфизм графов Go и Gb ПустьG, = (p(G0):G0 = G, где ф - пре-образование изоморфизма; т - мощность множества N вершин графов. В табл. 1.4 приведен протокол доказательства данного утвер-ждения.
Поясним строение этого протокола. На шаге (1) участник Р создает случайный граф Я, изоморфный G\. На шаге (2) участник V, выбирая случайный бит а = {0Д}, тем самым просит доказать, что
Н ~G0 либо что Н « Gj. На шаге (3) участник Р посылает участни-ку V преобразование \|/, которое он строит таким образом, что при а = 1 в результате применения этого преобразования к графу Gu по-лучается граф F1 = TtG, = Н. а при а = 0 в результате применения этого преобразования к графу Ga получается граф F0 =
зо Запечников С. В. Криптографические протоколы и их применение
= 7i((p(G0))~7iG] = #, На шаге (4) участник V, выполняя проверку равенства графов, тем самым определяет, выполнено ли условие
Н = Fa. Шаги (1) - (4) повторяются т раз. Если во всех т раундах этого протокола результат проверки оказывается положительным, V принимает доказательство.
Таблица 1.4. Протокол доказательства изоморфизма графов
Р V
1 % - случайная перестановка вершин, вычисляет H = nGl
2 f п, если (а -1),
V = 1 / ч 1 л о ф, если (а = 0) -> т раз
4 Вычисляет граф \j/Ga и сравнивает: Н =\jfGa
5 Принимает доказательство тогда и только тогда, когда для Vm
Этот протокол действительно является протоколом с нулевым разглашением знаний, так как в случае изоморфных G0 ~ Gx участ-ник V не получает никакой информации, кроме изоморфизмов гра-фов G0 и G\ с какими-то их случайными перенумерациями, которые он мог бы получить и самостоятельно, выбирая случайный бит а и перенумеровывая случайным образом граф Ga .
3. Доказательство знания дискретного логарифма х числа X. Перед началом работы протокола задаются открытые величины: р,
q - простые числа, такие, что q\(p -1), элемент g е Z*, число X. До- ]. Базовые криптографические протоколы 31
называющему Р известна секретная величина x\xТаблица 1.5. Протокол доказательства знания дискретного логарифма
Р V
I r&RZ
М = g (mod р)
2 А. Доказательство знания представления числа у в базисе (zero- knowledge proof of knowledge of у representation). Перед началом работы протокола задаются открытые величины, известные всем уча-стникам: простые числа р, q, элементы y,gvg2,..., gk Є Gq. Доказы-вающему P известны секретные величины ара 2,...,ake ZQ: у =
= 8і" " 8г1""> знание которых он должен доказать V, не разгла-шая самих этих величин. Протокол представлен в табл. 1.6.
Таблица 1.6. Протокол доказательства знания представления
числа в базисе
Р V
1 rl.r2,...,rk. ЄІ{ Zq,
2 5. Доказательство знания представления множества чисел в соответствующих базисах (zero-knowledge proof of knowledge of equality of representation of all y(j) in the respective bases). Перед началом работы протокола задаются открытые величины, извест-
W I >\
ные всем участникам: простые числа р, q, элементы у, 82^є для некоторых (/). Доказывающему Р известны сек-ретные величины 0С[,а2,...,а,. є Zq, такие, что для V/ у^ =
= (і^) " 1 > знание которых он должен доказать V,
не разглашая самих этих величин. В табл. 1.7 приведен протокол, который решает эту задачу.
Таблица 1.7. Протокол доказательства знания множества чисел
в соответствующих базисах
Р V
1 rvr21...lrkeR ля У/
2 (АиП«іТ-(ьТ-
6. Доказательство знания мультипликативной связи «депониро-ванных» величин (zero-knowledge proof of knowledge of multiplicative rela-tion between committed values). Элемент X = gx циклической подгруп-пы простого порядка, в которой задача дискретного логарифмирования считается вычислительно-сложной, называется депонированной вели-чиной (committed value), представляющей секретную величину х. Пусть
d - неизвестный элемент, такой, что h = gd . Перед началом работы протокола задаются открытые величины: простые числа р, q, элементы А, В, С Є Gq . Доказывающему Р известны секретные величины
a, a, b, Ь, с, с, такие, что с = ab, A = gah"\ В = gbhb, С = gche. Знание их он и должен доказать V, не разглашая самих величин. В табл. 1.8 при-веден протокол такого доказательства.
Таблица 1.8. Протокол доказательства знания мультипликативной связи депонированных величин
Р V
1 М=і">/Ї, j Mt = gx-h*\ ¦ M2= Bx ¦ h"1
2 =CK-M2
разглашением знания
Таблица 1.9. Структура протоколов доказательства с нулевым
P S: x є L- доказываемое утверждение, h - dp, общедоступные параметры и величины, s - секретные данные дока-зывающего о том, почему S истинно, г- случайное число V
1 rp- случ.,
2 rv - случай-ное число,
с = ЛМ
Обобщим рассмотренные примеры и сформулируем ряд определений. В общем виде протокол интерактивного доказательства с ну-левым разглашением знания (табл. 1.9) состоит из четырех шагов:
Окончание табл. 1.9
Р S: хе L- доказываемое утверждение, h - др. общедоступные параметры и величины, s - секретные данные дока-зывающего о том, почему S истинно, г - случайное число V
3 R = f3(C,x)
4
доказывающий передает проверяющему так называемое сви-детельство (witness -W)- результат вычисления однонаправленной функции от секретной величины, знание которой он доказывает;
проверяющий посылает ему случайный запрос;
доказывающий отвечает на этот запрос, причем ответ зависит как от случайного запроса, так и от секретной величины, но из него вычислительно невозможно получить эту секретную величину;
получая ответ, V проверяет его соответствие «свидетельству», переданному на первом шаге.
Рассмотрим основные принципы построения доказательств с ну-левым разглашением знания: что подразумевает свойство нулевого разглашения знания.
В теории доказательств с нулевым разглашением знания Р и V рассматриваются как «черные ящики» (рис. 1.3).
Пусть \тр }, \}Пу } - совокупность всех сообщений, передаваемых от Р к V (соответственно от У к Р), каждое из которых является слу-чайной величиной, и, таким образом, {x,h,rv,{mp},{mv}} = = viewpy}
