Доказательство с нулевым разглашением

В криптографии Доказательство с нулевым разглашением (информации) (англ. Zero-knowledge proof) — это интерактивный протокол, позволяющий одной из сторон (проверяющему, verifier) убедиться в достоверности какого-либо утверждения (обычно математического), не получив при этом никакой другой информации от второй стороны (доказывающего, prover). При этом, когда возможность доказать утверждение требует некоторой секретной информации со стороны доказывающего, подразумевается, что проверяющий не сможет доказать утверждение кому-либо еще. А под интерактивностью подразумевается непосредственное взаимодействие сторон. Обратите внимание, что сам термин применяется только в случае, если утверждение доказано, и доказывающий имеет необходимую информацию. В противном случае утверждение не будет доказано в рамках данного протокола, так как в итоге проверяющий дополнительно узнал бы, что доказывающий имеет познания об искомой информации. Это частный случай хорошо иллюстрирует суть понятия: доказать, что человек обладает определенными сведениями в большинстве случаев тривиально, если один имеет право просто раскрыть информацию; вся сложность состоит в том, чтобы доказать, что у тебя есть информация, не раскрывая ее.

Для рассматриваемого протокола требуется наличие интерактивных исходных данных (interactive input) от проверяющего, как правило, в виде задачи или проблемы, такой что, в итоге убедят проверяющего, что у доказывающего есть информация для доказательства утверждения. Это достаточно очевидное высказывание, так как в противном случае проверяющий смог бы записывать выполнение протокола и доказать это кому-то другому, что противоречит тому, что для доказательства утверждения требуется знания некоторых секретных данных со стороны доказывающего.

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

Формальное определение

Доказательство с нулевым разглашением должно обладать тремя свойствами:

1. Полнота: если утверждение действительно верно, то доказывающий убедит в этом проверяющего.
2. Корректность: если утверждение неверно, то даже нечестный доказывающий не сможет убедить проверяющего за исключением пренебрежимо малой вероятности.
3. Нулевое разглашение: если утверждение верно, то любой даже нечестный проверяющий не узнает ничего кроме самого факта, что утверждение верно.

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

Доказательства с нулевым разглашением нашли применение в криптографических протоколах чтобы убедиться в том, что другая сторона следует протоколу честно. На практике доказательства с нулевым разглашением также используются в протоколах конфиденциального вычисления.

Различные виды нулевого разглашения

Различные варианты нулевого разглашения могут быть определены путем формализации самого понятия и сравнения распространения информации различных моделей с протоколом следующими способами:

• Идеальный протокол нулевого разглашения — если распространение информации в рассматриваемой модели точно такое же как и в протоколе. Хорошей иллюстрацией будет пример Алисы и Боба в пещере.
• Статистически нулевое разглашение, означает, что распределение не обязательно такое же, но они по крайней мере статистически близки (statistically close), при этом статистическая разница есть незначительная функция (negligible function).
• Вычислительно нулевым разглашением называется такая модель, если не существует такого эффективного алгоритма, который смог бы различить эти два распределения.

История развития

Шафи Гольдвассер

Доказательство нулевым разглашением был придумано и разработано следующими учеными: Шафи Гольдвассер, Сильвио Микалием и Чарльз Реккофом, и опубликовано ими в статье «Знание и сложность интерактивной системы с доказательством» в 1985 году. Эта работа представила иерархию интерактивных систем с доказательством, основываясь на объеме информации о доказательстве, которой необходимо передать от доказывающего до проверяющего. Ими так же было предложено первое доказательство конкретно поставленного доказательства с нулевым разглашением — квадратичного вычета по модулю m. Впоследствии, дополнив свою работу, они выиграли первую премию Геделя в 1993 году.

Исследования в области доказательства с нулевым разглашением были мотивированы созданием новой системы аутентификации, при которой одна сторона хочет доказать свою подлинность другой стороне при этом не выдавая саму тайну. Один из самых интересных применений доказательства с нулевым разглашением в криптографических протоколах является обеспечение «честного поведения», сохраняя при этом конфиденциальность. При этом в рамках этого протокола пользователь так и будет поступать, сохраняя с своих тайн. Все данные аспекты были описаны в новаторской работе Сильвио Микалия, Одеда Голдрейха и Ави Вигдерсона и использованы в протоколе конфиденциального вычисления.

В дальнейшем криптосистема Гольдвассер — Микали, основанная на рассматриваемом интерактивном протоколе, являющееся криптографической системой с открытым ключом, разработанная Шафи Гольдвассер и Сильвио Микали в 1982 году, является первой схемой вероятностного шифрования с открытым ключом, доказуемо стойкая при стандартных криптографических предположениях. Была высоко оценена жюри: Гольдовассер и Микали стали лауреатами Премии Тьюринга за 2012 год, за создание криптосистемы с вероятностным шифрованием, отмеченная в номинации как новаторская работа, оказавшая существенное влияние на современную криптографию. Однако, криптосистема является неэффективной, так как шифртекст может быть в сотни раз длиннее, чем шифруемое сообщение. Для доказательства свойств стойкости криптосистемы Голдвассер и Микали ввели широко используемое понятие семантической стойкости.

Общая структура доказательств с нулевым разглашением

Каждый раунд или аккредитация доказательства состоит из трёх этапов. Схематично их можно изобразить следующим образом:

• $A\Rightarrow B$ : доказательство (witness)
• $A\Leftarrow B$ : вызов (challenge)
• $A\Rightarrow B$ : ответ (response)

Сначала A выбирает из заранее определенного множества некоторый элемент, который становится её секретом (закрытый ключ). На основе этого элемента вычисляется, а затем публикуется открытый ключ. Знание секрета определяет множество вопросов, на которые А всегда сможет дать правильные ответы. Затем A выбирает случайный элемент из множества, по определенным правилам (в зависимости от конкретного алгоритма) вычисляет доказательство и затем отсылает его B. После этого B выбирает из всего множества вопросов один и просит A ответить на него (вызов). В зависимости от вопроса, А посылает B ответ. Полученной информации B достаточно, чтобы проверить действительно ли А владеет секретом. Раунды можно повторять сколько угодно раз, пока вероятность того, что A «угадывает» ответы не станет достаточно низкой.

Такая техника называется также «разрезать и выбрать» (cut-and-choose).

Пример

Пещера нулевого разглашения

Пещера нулевого разглашения.

Впервые данный пример был написан в хорошо известной работе по доказательству с нулевым разглашением “Как объяснить протокол доказательства с нулевым разглашением вашим детям” Жак-Жаком Кискатером.

В данном случае Пегги выступаете в качестве доказывающего утверждение и Виктор в качестве проверяющего. У Пегги есть магические слова (ключ), который позволяет открыть дверь между C и D. Виктор хочет узнать действительно ли Пегги знает пароль, при этом Пегги не хочет выдавать сам пароль. Соответственно пещера имеет круглую форму, как представлено на картинке. Для того, чтобы решить проблему они поступают следующим способом. Пока Виктор находится в точке А, Пегги идет к двери, и после того как она исчезает из виду, Виктор идет к разветвлению, то есть в B и кричит откуда Пегги нужно выйти. Получаем каждый раз шанс того, что Пегги знает пароль равен 50%. Если же повторить процесс k раз, то вероятность будет 1 к 2^k. При 20 же повторениях этот шанс будет порядка 1 к 1млн, что является достаточным в справедливости утверждения.

Если Боб запишет все происходящие на камеру, то полученная видеозапись не будет являться доказательством для какой либо другой стороны. Ведь они могли договориться, откуда будет выходить Пегги. Соответственно она сможет найти выход, не зная при этом самого ключа. Существует еще один способ, Боб просто вырезает все неудачные попытки Пегги. Все выше написанные заключения доказывают, что пример с пещерой удовлетворяют формальному определение: полноте, корректности и нулевому разглашению.

Гамильтонов цикл для больших графов

Граф додекаэдра с выделенным циклом Гамильтона

Данный пример был придуман Мануэлем Блюмом и описан в его работе в 1986 году. Назовем проверяющую сторону Петей, а доказывающую сторону Димой (в англоязычной литературе обычно используются пары Peggy (от prover) и Victor (от verifier). Допустим Диме известен Гамильтонов цикл в большом графе G. Пете известен граф G, но он не знает гамильтонова цикла в нём. Дима хочет доказать Пете, что он знает гамильтонов цикл, не выдавая при этом ни самого цикла, ни какой-либо информации о нём (возможно Петя хочет купить этот гамильтонов цикл у Димы, но перед этим удостовериться, что он у Димы действительно есть).

Для этого Петя и Дима совместно выполняют несколько раундов протокола:

• Вначале Дима создает граф H, изоморфный G. Преобразовывание гамильтонова цикла между изоморфными графами — тривиальная задача, поэтому если Диме известен гамильтонов цикл в G, то он также знает гамильтонов цикл в H.
• Дима передает граф H Пете.
• Петя выбирает случайный бит b ← {0,1}
  • Если b=0, то Петя просит Диму доказать изоморфизм G u H, то есть предоставить соответствие вершин этих двух графов. Петя может проверить, действительно ли G u H изоморфны.
  • Если b=1, то Петя просит Диму показать гамильтонов цикл в H. Для задачи изоморфизма графов на данный момент не доказана ни её принадлежность классу $P$, ни её $NP$-полнота, поэтому будем здесь считать, что невозможно из гамильтонова цикла в H вычислить гамильтонов цикл в G.

В каждом раунде Петя выбирает новый случайный бит, который неизвестен Диме, поэтому чтобы Дима мог ответить на оба вопроса, нужно чтобы H был в самом деле изоморфен G и Дима должен знать гамильтонов цикл в H (а значит также и в G). Поэтому после достаточного числа раундов, Петя может быть уверен в том, что у Димы действительно есть гамильтонов цикл в G. С другой стороны, Дима не раскрывает никакой информации о гамильтоновом цикле в G. Более того, Пете сложно будет доказать кому-либо ещё, что он сам или Дима знает гамильтонов цикл в G.

Предположим, что у Димы нет гамильтонова цикла в G и он хочет обмануть Петю. Тогда Диме необходим неизоморфный G граф G' , в котором он всё-таки знает гамильтонов цикл. В каждом раунде он может передавать Пете либо H'  — изоморфный G' , либо H — изоморфный G. Если Петя попросит доказать изоморфизм и был передан H, то обман не вскроется. Аналогично, если он просит показать гамильтонов цикл и был передан H' . В таком случае вероятность того, что Дима все-таки обманет Петю после n раундов, равна 1/2ⁿ, что может быть меньше любой заранее заданной величы при достаточном числе раундов.

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

Применение на практике

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

Блюмом (M.Blum) было доказано, что любую математическую теорему можно представить как граф, такой, что доказательство теоремы будет эквивалентно доказательству существования в нем гамильтонова цикла. Теорема, гласящая, что для любого NP-полной задачи существует доказательство с нулевым разглашением, при этом, если использовать односторонние функции, можно создать очень хорошие алгоритмы шифрования, была доказана. То есть можно доказать всему миру, что знаешь доказательство математической теоремы, не раскрывая самого доказательства. И это тоже показывает, как может быть использован данный протокол в практических целях.

Следующий метод, где может быть использовано доказательство с нулевым разглашением, является определения идентичности, при этом закрытый ключ у Пегги является так называемым показателем "идентичности", и использую рассматриваемый протокол, можно доказать свою идентичность. То есть по сути, можно доказать свою личность без использования различных физический устройств и данных (символов), таких как паспорта, различные снимки человека (сетчатки глаза, пальцев рук, лица и т.д.), а принципиально другим образом. Это действительно стоящие применение протокола. Однако, к сожалению, он имеем ряд недостатков, которые могут применены для обхода защиты. Выше описанные метод был впервые предложен Амосом Фиатом, Ади Шамиром и Уриелем Файгом в 1987 году.

Злоупотребления

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

• Проблема гроссмейстера — в данном примере некоторая сторона может доказать владение секретом, не обладая им на самом деле или, другими словами, может имитировать то лицо, которому на самом деле принадлежит секрет. В настоящее время предложен способ решения проблемы Томасом Бетом (T. Beth) и Иво Десмедтом (Y. Desmedt).
• Обман с несколькими личностями — если сторона сможет создать несколько секретов, то соответственно она также сможет создать «несколько личностей», одну из которых никогда пусть не будет использовать. Такая возможность позволяет, например, совершить преступление и безнаказанно скрыться. Затем, во время совершения преступления сторона идентифицирует себя никогда не используемой личностью. После преступления личность никогда больше не используется. Таким образом, выследить преступника практически невозможно. Данное злоупотребление обходится, если заранее не допустить возможность создания еще одного секрета.
• Обман, выполненный мафией — Тут так же сторона выдает себя за другую. Более подробно звучит следующим образом. Пусть имеется 4 участника: A, B, C, D. Причем B и С сотрудничают между собой («принадлежат одной мафии»). А доказывает свою личность B, а С хочет выдать себя за A перед D. B владеет рестораном, принадлежащим мафии, С — также представитель мафии, D — ювелир. A и D не знают о предстоящем мошенничестве. В момент, когда A готов заплатить за обед и идентифицировать себя перед B, B извещает С о начале мошенничества. Это возможно, благодаря наличию радио-канала между ними. В это время, С выбирает бриллиант, который хочет купить, и D начинает идентифицировать личность С(а на самом деле A). С передает вопрос по протоколу B, а тот, в свою очередь, задает его А. Ответ передается в обратном порядке. Таким образом, А заплатит не только за обед, но и за дорогой бриллиант. Как видно из вышеописанного, существуют определенные требования для подобного мошенничества. Когда А начинает доказывать свою личность перед B, а С — перед D должны быть точно синхронизированы. То есть данное злоупотребление так же решается. Если в магазине ювелира будет клетка Фарадея, то мафиози не смогут обмениваться сообщениями.

Возможные атаки

Атака на основе подобранного шифротекста

Данная атака осуществима при использования не интерактивного метода взаимодействия в протоколе нулевого разглашения. При использования такого протокола возникает несколько проблем, во первых нужно решить как нужно осуществлять взаимодействие, и при этом должны быть сохранены фундаментальные особенности самого протокола: полнота, корректность и "нулевое разглашение". Помимо того, что можно достаточно просто доказать нулевое знание другой стороне, если можно прослушивать канал, то есть столкнутся с проблемой гроссмейстера. Так вот сама атака заключается в следующем: злоумышленник, используя сложность доказательства обладанием знания, включает "атакающий" шифротекст, подсовывая его в кучу других шифротекстов, которые должны быть расшифрованы. Данная атака называется “playback” атака

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

См. также

• Схема Шнорра
• Протокол Фиата-Шамира
• Протокол Фейга-Фиата-Шамира
• Протокол Гиллу-Кискатра
• Криптографическая хеш-функция
• Атака на основе подобранного шифротекста
• Криптосистема с открытым ключом

Литература

• 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.
• Y.Desmedt, C.Goutier, S.Bengio, «Special Uses and Abuses of the Fiat-Shamir Passport Protocol», Advances in Cryptology CRYPTO’87 Proceeding, Springer-Verlag, 1988, pp.21-39.
• T.Beth and Y.Desmedt, «Identification Tokens-or: Solving the Chess Grandmaster Problem», Advances in Cryptology CRYPTO '90 Proceedings, Springer-Verlag, 1991, pp. 169—176.
• Daniel Bleichenbacher. Chosen Ciphertext Attacks Against Protocols Based on the RSA Encryption Standard PKCS #1. — Bell Laboratories
• Саломаа А. Криптография с открытым ключом. — М.: Мир, 1995. — 318 с. — ISBN 5-03-001991-X.
• A. J. Menezes, P. C. van Oorschot, S. A. Vanstone. Handbook of Applied Cryptography. — 1997. — ISBN 0-8493-8523-7.
• Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. — М.: Триумф, 2002. — 816 с. — 3000 экз. — ISBN 5-89392-055-4.

Ссылки

• How to construct zero-knowledge proof systems for NP
• Lecture: Computational Zero Knowledge by Madhur Tulsiani
• A gentle introduction to zero-knowledge proofs with applications to cryptography
• Salil Vadhan, Vadhan’s phd thesis on statistical zero knowledge
• Theory of Computing Course, Cornell University 2009, Zero knowledge proofs
• A Study of Perfect Zero-Knowledge Proofs by Lior Malka in 2008 Scientific work