Эта статья входит в число добротных статей

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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Под интерактивностью протокола подразумевается непосредственный обмен информацией сторонами[1][2].

Таким образом, рассматриваемый протокол требует наличия интерактивных исходных данных (interactive input) от Проверяющего, как правило, в виде задачи или проблемы. Цель легального Доказывающего (имеющего доказательство) в этом протоколе — убедить Проверяющего в том, что у него есть решение, не выдав при этом даже части «секретного» доказательства («нулевое разглашение»). Цель Проверяющего же — это удостовериться в том, что доказывающая сторона «не лжёт»[2][3].

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

Определение[править | править вики-текст]

Доказательство с нулевым разглашением — интерактивный вероятностный протокол, который позволяет доказать, что доказываемое утверждение верно, и Доказывающий знает это доказательство, в то же время не предоставляя никакой информации о самом доказательстве данного утверждения[7]. Данный криптографический протокол должен обладать тремя свойствами:

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

Доказательства с нулевым разглашением не являются доказательствами в математическом смысле этого термина, потому что есть некоторая небольшая вероятность, что обманом доказывающая сторона сможет убедить Проверяющего в ложном утверждении (ошибка корректности). Иными словами, доказательства с нулевым разглашением — это вероятностные доказательства, а не детерминированные. Тем не менее, есть методы, позволяющие уменьшить ошибку корректности до пренебрежимо малых значений[9][10].

Различные виды нулевого разглашения[править | править вики-текст]

Выполнение протокола доказательства с нулевым разглашением приводит к выводу результата Принять/Отклонить и также порождает стенограмму доказательства. Различные варианты нулевого разглашения могут быть определены путём формализации самого понятия и сравнения распространения информации различных моделей с протоколом следующими способами[11][12]:

  • Идеальный протокол нулевого разглашения — если случайные величины в стенограмме доказательства рассматриваемой модели являются равномерно распределенными и не зависят от общих входных данных[13]. Хорошей иллюстрацией будет пример Алисы и Боба в пещере.
  • Статистически нулевое разглашение[14] означает, что распределение не обязательно такое же, но они по крайней мере статистически близки[en], при этом статистическая разница есть незначительная функция[en][15].
  • С вычислительно нулевым разглашением называют такую модель, если не существует на данный момент такого эффективного алгоритма, который смог бы отличить распределение величин от распространения информации в идеальном протоколе[16].

История развития[править | править вики-текст]

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

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

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

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

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

  •  : доказательство (witness)
  •  : вызов (challenge)
  •  : ответ (response)

Сначала A выбирает из заранее определённого непустого множества некоторый элемент, который становится её секретом — закрытым ключом. По этому элементу вычисляется, а затем публикуется открытый ключ. Знание секрета определяет множество вопросов, на которые А всегда сможет дать правильные ответы. Затем A выбирает случайный элемент из множества, по определённым правилам (в зависимости от конкретного алгоритма) вычисляет доказательство и затем отсылает его B. После этого B выбирает из всего множества вопросов один и просит A ответить на него (вызов). В зависимости от вопроса, А посылает B ответ[24]. Полученной информации B достаточно, чтобы проверить действительно ли А владеет секретом. Раунды можно повторять сколько угодно раз, пока вероятность того, что A «угадывает» ответы, не станет достаточно низкой. Такой подход называется также «разрезать и выбрать» («cut-and-choose»), впервые использованный в криптографии Михаэлем Рабином[25][26].

Примеры[править | править вики-текст]

Пещера нулевого разглашения[править | править вики-текст]

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

Впервые данный пример был написан в хорошо известной работе по доказательству с нулевым разглашением «Как объяснить протокол доказательства с нулевым разглашением вашим детям» Жан-Жаком Кискатером (англ.)[27].

В данном случае Пегги выступает в качестве Доказывающего утверждение, и Виктор — в качестве Проверяющего (в англоязычной литературе обычно используются наименование сторон Peggy от «Prover» и Victor от «Verifier»). Пегги знает магическое слово («ключ»), ввод которого позволяет открыть ей дверь между C и D. Виктор хочет узнать, действительно ли Пегги знает пароль, при этом Пегги не хочет выдавать сам пароль. Пещера имеет круглую форму, как представлено на рисунке. Для того чтобы решить проблему, они поступают следующим способом. Пока Виктор находится в точке А, Пегги идёт к двери, и после того, как она исчезает из виду, Виктор идёт к разветвлению, то есть в точку B, и кричит откуда: «Пегги нужно выйти справа» или «Пегги нужно выйти слева». Получаем каждый раз вероятность того, что Пегги не знает пароль, равна 50 %. Если же повторить процесс k раз, то вероятность будет . При 20 же повторениях эта вероятность будет порядка 10-6, что является достаточным для справедливости предположения о том, что Пегги знает ключ[27].

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

Гамильтонов цикл для больших графов[править | править вики-текст]

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

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

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

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

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

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

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

Применение на практике[править | править вики-текст]

Теорема, гласящая, что для любой NP-полной задачи существует доказательство с нулевым разглашением, при этом, если использовать односторонние функции, можно создать корректные криптографические протоколы, была доказана Одедом Голдрейхом[en], Сильвио Микали и Ави Вигдерсоном[17][31]. То есть, можно доказать любому скептику, что обладаешь доказательством некоей математической теоремы, не раскрывая самого доказательства. Это тоже показывает, как может быть использован данный протокол в практических целях[11].

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

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

Злоупотребления[править | править вики-текст]

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

Проблема гроссмейстера[править | править вики-текст]

В данном примере некоторая сторона может доказать владение секретом, не обладая им на самом деле или, другими словами, может имитировать то лицо, которому на самом деле принадлежит секрет[34]. В настоящее время предложен способ решения проблемы Томасом Бетом[de] и Иво Десмедтом[en][35].

Обман с несколькими личностями[править | править вики-текст]

Если сторона сможет создать несколько секретов, то соответственно она также сможет создать «несколько личностей», одну из которых никогда пусть не будет использовать. Такая возможность позволяет, например, совершить преступление и безнаказанно скрыться. Затем, во время совершения преступления, сторона идентифицирует себя никогда не используемой личностью. После преступления личность никогда больше не используется. Таким образом, выследить преступника практически невозможно. Данное злоупотребление обходится, если заранее не допустить возможность создания ещё одного секрета[36].

Обман, выполненный мафией[править | править вики-текст]

Ещё один пример, когда одна сторона выдает себя за другую. Пусть имеется 4 участника: A, B, C, D. Причём B и С сотрудничают между собой («принадлежат одной мафии»). А доказывает свою личность B, а С хочет выдать себя за A перед D. B владеет рестораном, принадлежащим мафии, С — также представитель мафии, D — ювелир. A и D не знают о предстоящем мошенничестве. В момент, когда A готов заплатить за обед и идентифицировать себя перед B, B извещает С о начале мошенничества. Это возможно благодаря наличию радиоканала между ними. В это время С выбирает бриллиант, который хочет купить, и D начинает идентифицировать личность С, который выдает себя за A. С передаёт вопрос по протоколу B, а тот в свою очередь, задаёт его А. Ответ передаётся в обратном порядке. Таким образом А заплатит не только за обед, но и за дорогой бриллиант. Как видно из вышеописанного, существуют определённые требования для подобного мошенничества. Когда А начинает доказывать свою личность перед B, а С — перед D, B и С должны быть точно синхронизированы. То есть данное злоупотребление тоже решается. Например, если в магазине ювелира будет клетка Фарадея, то «мафиози» не смогут обмениваться сообщениями[37].

Возможные атаки[править | править вики-текст]

Атака на основе подобранного шифротекста[править | править вики-текст]

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

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

Атака на мультипротокольную систему нулевого знания[править | править вики-текст]

Тида и Ямамото предложили такую реализацию протокола нулевого знания, которая значительно повышает скорость доказательств обладанием нулевым знанием при одновременном доказательстве сразу нескольких утверждений и, как следствие, производительность всей системы в целом[40]. Ключевой особенностью является ограничение на количество итераций для доказательства. Как было показано в работе К. Пэна[41], данный алгоритм оказался полностью неустойчивым к следующей атаке. Используя несколько правильно подобранных итераций, злоумышленник может пройти верификацию и нарушить главные положения о протоколе. Причём было показано, что данная атака всегда осуществима на такую систему.

Атака с помощью квантового компьютера[править | править вики-текст]

В 2005 году Джоном Ватрусом[en] было показано, что не все системы с нулевым знанием являются устойчивыми к атакам с помощью квантового компьютера. Однако было доказано, что можно всегда построить такую систему, которая будет устойчива против квантовых атак, в предположении, что существуют квантовые системы с «сокрытием обязательств»[42].

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

  1. Goldreich, 2013.
  2. 1 2 Шнайер, 2002, pp. 87-92.
  3. Goldwasser, Micali, Rackoff, 1989, pp. 186-189.
  4. Santis, Micali, Persiano, 1988.
  5. Blum, Feldman, Micali, 1988.
  6. Шнайер, 2002, pp. 90-91.
  7. Blum, 1988, p. 1444.
  8. Menezes et al, 1996, pp. 406-408.
  9. Шнайер, 2002, pp. 86-89.
  10. Goldwasser, Micali, Rackoff, 1989, pp. 188-189.
  11. 1 2 Шнайер, 2002, pp. 91-92.
  12. Мао, 2005, pp. 683-696.
  13. Мао, 2005, pp. 684-688.
  14. Sahai, Vadhan, 2003.
  15. Мао, 2005, p. 696.
  16. Мао, 2005, pp. 692-696.
  17. 1 2 3 Goldreich, Micali, Wigderson, 1986.
  18. Goldwasser, Micali, Rackoff, 1989.
  19. Goldwasser, Micali, Rackoff, 1989, pp. 198-205.
  20. Goldwasser, Micali and Rackoff Receive Gödel Prize in 1993. ACM Sigact (1993).
  21. Goldwasser, Micali Receive ACM Turing Award for Advances in Cryptography. ACM. Проверено 13 марта 2013.
  22. Goldwasser, Micali, 1982.
  23. Мао, 2005, pp. 524-528.
  24. Мао, 2005, pp. 678-682.
  25. M.O.Rabin. Digital signatures. — Foundations of Secure Computation. — New York: Academic Press, 1978. — С. 155-168. — ISBN 0122103505.
  26. Шнайер, 2002, pp. 87-89.
  27. 1 2 Quisquater et al, 1990.
  28. Шнайер, 2002, pp. 87-88.
  29. 1 2 3 4 Blum, 1988.
  30. Шнайер, 2002, pp. 89-90.
  31. Goldreich, Micali, Wigderson, 1987.
  32. Шнайер, 2002, p. 92.
  33. Fiat, Shamir, 1987.
  34. Шнайер, 2002, pp. 92-93.
  35. Beth, Desmedt, 1991.
  36. Шнайер, 2002, pp. 93-94.
  37. Шнайер, 2002, p. 93.
  38. Rackoff, Simon, 1992.
  39. Naor, Yung, 1990.
  40. Chida, Yamamoto, 2008.
  41. Peng, 2012.
  42. Watrous, 2006.

Литература[править | править вики-текст]

книги и монографии
статьи