Доказа́тельство с нулевы́м разглаше́нием (информа́ции) в криптографии () — интерактивный криптографический протокол, позволяющий одной из взаимодействующих сторон («The verifier» — проверяющей) убедиться в достоверности какого-либо утверждения (обычно математического), не имея при этом никакой другой информации от второй стороны («The prover» — доказывающей). Причём последнее условие является необходимым, так как обычно доказать, что сторона обладает определёнными сведениями в большинстве случаев тривиально, если она имеет право просто раскрыть информацию. Вся сложность состоит в том, чтобы доказать, что у одной из сторон есть информация, не раскрывая её содержания. Протокол должен учитывать, что доказывающий сможет убедить проверяющего только в случае, если утверждение действительно доказано. В противном случае сделать это будет невозможно, или крайне маловероятно из-за вычислительной сложности.
Под интерактивностью протокола подразумевается непосредственный обмен информацией сторонами.
Таким образом, рассматриваемый протокол требует наличия интерактивных исходных данных (interactive input) от проверяющего, как правило, в виде задачи или проблемы. Цель легального доказывающего (имеющего доказательство) в этом протоколе — убедить проверяющего в том, что у него есть решение, не выдав при этом даже части «секретного» доказательства («нулевое разглашение»). Цель проверяющего же — это удостовериться в том, что доказывающая сторона «не лжёт».
Также были разработаны протоколы доказательства с нулевым разглашением, для которых не требовалось наличия интерактивных исходных данных, при этом доказательство которых, как правило, опирается на предположение об идеальной криптографической хеш-функции, то есть предполагается, что выход однонаправленной хеш-функции невозможно предсказать, если неизвестен её вход.
Доказательство с нулевым разглашением используется в нескольких блокчейнах, кроме того, находит применение для проверки наличия сведений без передачи самих сведений.
Определение Доказательство с нулевым разглашением — интерактивный вероятностный протокол, который позволяет доказать, что доказываемое утверждение верно, и Доказывающий знает это доказательство, в то же время не предоставляя никакой информации о самом доказательстве данного утверждения. Данный криптографический протокол должен обладать тремя свойствами: Полнота: если утверждение действительно верно, то Доказывающий убедит в этом Проверяющего с любой наперед заданной точностью. Корректность: если утверждение неверно, то любой, даже «нечестный», Доказывающий не сможет убедить Проверяющего за исключением пренебрежимо малой вероятности. Нулевое разглашение: если утверждение верно, то любой, даже «нечестный», Проверяющий не узнает ничего кроме самого факта, что утверждение верно.
Доказательства с нулевым разглашением не являются доказательствами в математическом смысле этого термина, потому что есть некоторая небольшая вероятность, что обманом доказывающая сторона сможет убедить Проверяющего в ложном утверждении (ошибка корректности). Иными словами, доказательства с нулевым разглашением — это вероятностные доказательства, а не детерминированные. Тем не менее, есть методы, позволяющие уменьшить ошибку корректности до пренебрежимо малых значений.
Различные виды нулевого разглашения Выполнение протокола доказательства с нулевым разглашением приводит к выводу результата Принять/Отклонить и также порождает стенограмму доказательства. Различные варианты нулевого разглашения могут быть определены путём формализации самого понятия и сравнения распространения информации различных моделей с протоколом следующими способами: Идеальный протокол нулевого разглашения — если случайные величины в стенограмме доказательства рассматриваемой модели являются равномерно распределенными и не зависят от общих входных данных. Хорошей иллюстрацией будет пример Пегги и Виктора в пещере. Статистически нулевое разглашение означает, что распределение не обязательно такое же, но они по крайней мере , при этом статистическая разница есть . С вычислительно нулевым разглашением называют такую модель, если не существует на данный момент такого эффективного алгоритма, который смог бы отличить распределение величин от распространения информации в идеальном протоколе.
История развития
В 1986 году в работе Сильвио Микали, Одеда Голдрейха и Ави Вигдерсона было описано применение доказательств с нулевым разглашением для создания криптографических протоколов, которые должны обеспечивать «честное поведение» сторон, сохраняя при этом конфиденциальность.
Доказательство с нулевым разглашением было придумано и разработано следующими учёными: Шафи Гольдвассер, Сильвио Микали и Чарльзом Реккофом, и опубликовано ими в статье «Знание и сложность интерактивной системы с доказательством» в 1989 году. Эта работа представила иерархию интерактивных систем с доказательством, основываясь на объёме информации о доказательстве, который необходимо передать от Доказывающего до Проверяющего. Ими также было предложено первое доказательство конкретно поставленного доказательства с нулевым разглашением — квадратичного вычета по некоторому модулю m. Впоследствии, дополнив свою работу, они были удостоены первой премии Гёделя в 1993 году.
В дальнейшем криптосистема Гольдвассер — Микали, основанная на рассматриваемом интерактивном протоколе, являющаяся криптографической системой с открытым ключом, разработанная Шафи Гольдвассер и Сильвио Микали в 1982 году, является первой схемой вероятностного шифрования с открытым ключом, доказуемо стойкая при стандартных криптографических предположениях. Предложенная система была высоко оценена жюри: Гольдовассер и Микали стали лауреатами Премии Тьюринга за 2012 год, за создание криптосистемы с вероятностным шифрованием, отмеченная в номинации как новаторская работа, оказавшая существенное влияние на современную криптографию. Однако, криптосистема является неэффективной, так как порождаемый ею шифротекст может быть в сотни раз длиннее, чем шифруемое сообщение.
Для доказательства свойств стойкости криптосистемы Голдвассер и Микали ввели понятие семантической стойкости.
В 2021 году Ласло Ловас и Ави Вигдерсон были удостоены Абелевской премии, за их работы в области теоретической информатики, внёсшие важнейший вклад в развитие теории сложности вычислений, теории графов, методы распределенных вычислений и концепцию доказательств с нулевым разглашением.
Общая структура доказательств с нулевым разглашением Каждый раунд, или аккредитация доказательства, состоит из трёх этапов. Схематично их можно изобразить следующим образом: : доказательство (witness) : вызов (challenge) : ответ (response)
Сначала A выбирает из заранее определённого непустого множества некоторый элемент, который становится её секретом — закрытым ключом. По этому элементу вычисляется, а затем публикуется открытый ключ. Знание секрета определяет множество вопросов, на которые А всегда сможет дать правильные ответы. Затем A выбирает случайный элемент из множества, по определённым правилам (в зависимости от конкретного алгоритма) вычисляет доказательство и затем отсылает его B. После этого B выбирает из всего множества вопросов один и просит A ответить на него (вызов). В зависимости от вопроса, А посылает B ответ. Полученной информации B достаточно, чтобы проверить действительно ли А владеет секретом. Раунды можно повторять сколько угодно раз, пока вероятность того, что A «угадывает» ответы, не станет достаточно низкой. Такой подход называется также «разрезать и выбрать» («cut-and-choose»), впервые использованный в криптографии Михаэлем Рабином.
Примеры
Пещера нулевого разглашения
Впервые данный пример был написан в хорошо известной работе по доказательству с нулевым разглашением «Как объяснить протокол доказательства с нулевым разглашением вашим детям» .
В данном случае Пегги выступает в качестве Доказывающего утверждение, и Виктор — в качестве Проверяющего (в англоязычной литературе обычно используются наименование сторон Пегги и Виктор (от «Prover» и «Verifier» соответственно). Пегги знает магическое слово («ключ»), ввод которого позволяет открыть ей дверь между C и D. Виктор хочет узнать, действительно ли Пегги знает пароль, при этом Пегги не хочет выдавать сам пароль. Пещера имеет круглую форму, как представлено на рисунке. Для того чтобы решить проблему, они поступают следующим способом. Пока Виктор находится в точке А, Пегги идёт к двери, и после того, как она исчезает из виду, Виктор идёт к разветвлению, то есть в точку B, и кричит оттуда: «Пегги нужно выйти справа» или «Пегги нужно выйти слева». Получаем каждый раз вероятность того, что Пегги не знает пароль, равна 50 %. Если же повторить процесс k раз, то вероятность будет . При 20 же повторениях эта вероятность будет порядка 10−6, что является достаточным для справедливости предположения о том, что Пегги знает ключ.
Если Виктор запишет все происходящее на камеру, то полученная видеозапись не будет являться доказательством для какой-либо другой стороны. Ведь они могли заранее сговориться, откуда будет выходить Пегги. Соответственно, она сможет найти выход, не зная при этом самого ключа. Существует ещё один способ: Виктор просто вырезает все неудачные попытки Пегги. Эти описанные выше действия доказывают, что пример с пещерой удовлетворяет свойствам: полноты, корректности и нулевому разглашению.
Гамильтонов цикл для больших графов
Этот пример был придуман Мануэлем Блюмом и описан в его работе в 1986 году. Назовём проверяющую сторону Виктор, а доказывающую сторону Пегги. Допустим, Пегги известен гамильтонов цикл в большом графе G. Виктору известен граф G, но он не знает гамильтонова цикла в нём. Пегги хочет доказать Виктору, что она знает гамильтонов цикл, не выдавая при этом ни самого цикла, ни какой-либо информации о нём (возможно Виктор хочет купить информацию об этом гамильтоновом цикле у Пегги, но перед этим желает удостовериться, что Пегги действительно знает его).
Для этого Виктор и Пегги совместно выполняют несколько раундов протокола: Вначале Пегги создаёт граф H, изоморфный G. Преобразование гамильтонова цикла между изоморфными графами — тривиальная задача, поэтому если Пегги известен гамильтонов цикл в G, то она также знает гамильтонов цикл в порождаемом графе H. Пегги передаёт граф H Виктору. Виктор выбирает случайный бит b {0, 1}. Если b = 0, то Виктор просит Пегги доказать изоморфизм G и H, то есть предоставить взаимнооднозначное соответствие вершин этих двух графов. Виктор может проверить, действительно ли G и H изоморфны. Если b = 1, то Виктор просит Пегги указать гамильтонов цикл в H. Для задачи изоморфизма графов на данный момент не доказана ни её принадлежность классу , ни её -полнота, поэтому будем здесь считать, что невозможно из гамильтонова цикла в H вычислить гамильтонов цикл в изоморфном G.
В каждом раунде Виктор выбирает новый случайный бит, который неизвестен Пегги, поэтому, чтобы Пегги могла ответить на оба вопроса, нужно чтобы H был в самом деле изоморфен G, и Пегги должна знать гамильтонов цикл в H (а значит также и в G). Поэтому после достаточного числа раундов, Виктор может быть уверен в том, что у Пегги действительно есть знание о гамильтоновом цикле в G. С другой стороны, Пегги не раскрывает никакой информации о гамильтоновом цикле в G. Более того, Виктору сложно будет доказать кому-либо ещё, что он сам или Пегги знают гамильтонов цикл в G.
Предположим, что Пегги неизвестен гамильтонов цикл в G, но она хочет обмануть Виктора. Тогда Пегги необходим неизоморфный G граф G′, в котором она всё-таки знает гамильтонов цикл. В каждом раунде она может передавать Виктору либо H′ — изоморфный G′, либо H — изоморфный G. Если Виктор попросит доказать изоморфизм графов, и ему был передан H, то обман не вскроется. Аналогично, если он просит показать гамильтонов цикл, и ему был передан H′. В таком случае вероятность того, что Пегги всё-таки обманет Виктора после k раундов, равна , что может быть меньше любой заранее заданной величины при достаточном числе раундов.