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

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

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

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

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

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

Определение

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

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

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

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

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

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

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

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

В 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 раундов, равна , что может быть меньше любой заранее заданной величины при достаточном числе раундов .

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

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

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

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

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

Доказательства с нулевым разглашением применяются в блокчейнах криптовалют Zcash , Byzantium (форк Ethereum ), Zerocoin и других. Созданы реализации протоколов доказательства с нулевым разглашением, в частности, Software Development Kit QED-IT. Голландский банк ING создал свой вариант протокола, ZKRP ( Zero-Knowledge Range Proof ), и применил его для доказательства наличия у клиента достаточного размера заработной платы без раскрытия её истинного размера .

Наибольшее распространение получили протоколы zk-SNARKs, именно протоколы такого класса используются в ZCash, Zcoin и в протоколе Metropolis блокчейна Ethereum .

Аббревиатура zk-SNARK расшифровывается как (англ.) zero-knowledge succinct non-interactive argument of knowledge — краткий неинтерактивный аргумент знания с нулевым разглашением . Алгоритм zk-SNARK состоит из генератора ключей, доказывающего и верификатора, обязательно поддерживает нулевое знание, имеет краткость (вычисляется за короткое время), является неинтерактивным (верификатор получает только одно сообщение от доказывающего) .

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

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

Проблема гроссмейстера

В данном примере некоторая сторона может доказать владение секретом, не обладая им на самом деле или, другими словами, может имитировать то лицо, которому на самом деле принадлежит секрет . В настоящее время предложен способ решения проблемы и .

Обман с несколькими личностями

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

Обман, выполненный мафией

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

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

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

Данная атака осуществима при использовании неинтерактивного метода взаимодействия в протоколе нулевого разглашения.

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

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

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

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

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

Атака с помощью квантового компьютера

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

См. также

Примечания

  1. .
  2. , pp. 87—92.
  3. , pp. 186—189.
  4. .
  5. .
  6. , pp. 90—91.
  7. .
  8. .
  9. , p. 1444.
  10. , pp. 406—408.
  11. , pp. 86—89.
  12. , pp. 188—189.
  13. , pp. 91—92.
  14. , pp. 683—696.
  15. , pp. 684—688.
  16. .
  17. , p. 696.
  18. , pp. 692—696.
  19. .
  20. .
  21. , pp. 198—205.
  22. . ACM Sigact (1993). Архивировано из 8 декабря 2015 года.
  23. . ACM. Дата обращения: 13 марта 2013. Архивировано из 16 марта 2013 года.
  24. .
  25. , pp. 524—528.
  26. . Дата обращения: 17 мая 2021. 3 июня 2021 года.
  27. , pp. 678—682.
  28. M.O.Rabin. . — Foundations of Secure Computation. — New York: Academic Press, 1978. — С. 155—168. — ISBN 0122103505 . 21 ноября 2015 года.
  29. , pp. 87—89.
  30. .
  31. , pp. 87—88.
  32. .
  33. , pp. 89—90.
  34. .
  35. , p. 92.
  36. .
  37. .
  38. , pp. 92—93.
  39. .
  40. , pp. 93—94.
  41. , p. 93.
  42. .
  43. .
  44. .
  45. .
  46. .

Литература

книги и монографии
статьи
  • Goldwasser S. , Micali S. (англ.) // : Proceedings of the fourteenth annual ACM symposium on Theory of computing — New York City: ACM , 1982. — P. 365—377. — ISBN 978-0-89791-070-5
  • Blum M. (англ.) // : International Congress of Mathematicians. Berkeley, California, USA, August 3-11, 1986, Proceedings / A. Gleason — Providence: AMS , 1988. — P. 1444—1451. — 1850 p. — ISBN 978-0-8218-0110-9
  • Goldreich O. , Micali S. , Wigderson A. (англ.) // : 27th Annual Symposium on Foundations of Computer Science, Toronto, Canada, 27-29 October 1986. Proceedings IEEE Computer Society , 1986. — P. 174—187. — ISBN 978-0-8186-0740-0
  • Goldreich O. , Micali S. , Wigderson A. (англ.) : Extended Abstract // : 6th Annual International Cryptology Conference, Santa Barbara, California, USA, 1986, Proceedings / — Berlin, Heidelberg, New York City, London: , 1987. — P. 171—185. — 490 p. — ( ; Vol. 263) — ISBN 978-3-540-18047-0 — ISSN ; —
  • , Shamir A. (англ.) // : 6th Annual International Cryptology Conference, Santa Barbara, California, USA, 1986, Proceedings / — Berlin, Heidelberg, New York City, London: , 1987. — P. 186—194. — 490 p. — ( ; Vol. 263) — ISBN 978-3-540-18047-0 — ISSN ; —
  • , , (англ.) // : A Conference on the Theory and Applications of Cryptographic Techniques, Santa Barbara, California, USA, August 16-20, 1987, Proceedings / C. Pomerance — Berlin: , 1987. — P. 21—39. — ( ; Vol. 293) — ISBN 978-3-540-18796-7 — ISSN ; —
  • , Micali S. , (англ.) // : A Conference on the Theory and Applications of Cryptographic Techniques, Santa Barbara, California, USA, August 16-20, 1987, Proceedings / C. Pomerance — Berlin: , 1988. — P. 52—72. — ( ; Vol. 293) — ISBN 978-3-540-18796-7 — ISSN ; —
  • Blum M. , , Micali S. (англ.) // : Proceedings of the twentieth annual ACM symposium on Theory of computing — New York City: ACM , 1988. — P. 103—112. — ISBN 978-0-89791-264-8
  • Goldwasser S. , Micali S. , (англ.) // / M. Sudan — , 1989. — Vol. 18, Iss. 1. — P. 186—208. — ISSN ; —
  • , , , , , , , , , (англ.) // : 9th Annual International Cryptology Conference, Santa Barbara, California, USA, August 20-24, 1989, Proceedings / G. Brassard — Berlin, Heidelberg, New York City, London: , 1990. — P. 628—631. — ( ; Vol. 435) — ISBN 978-0-387-97317-3 — ISSN ; —
  • , (англ.) // : Proceedings of the twenty-second annual ACM symposium on Theory of computing — New York City: ACM , 1990. — P. 427—437. — ISBN 978-0-89791-361-4
  • , (англ.) // : 10th Annual International Cryptology Conference, Santa Barbara, California, USA, August 11-15, 1990, Proceedings / A. J. Menezes , S. A. Vanstone — Berlin, Heidelberg, New York City, London: , 1991. — P. 169—176. — ( ; Vol. 537) — ISBN 978-3-540-54508-8 — ISSN ; —
  • , (англ.) // : 11th Annual International Cryptology Conference, Santa Barbara, California, USA, 1991, Proceedings / — Berlin, Heidelberg, New York City, London: Springer Science+Business Media , 1992. — P. 433—444. — 484 p. — ( ; Vol. 576) — ISBN 978-3-540-55188-1 — ISSN ; —
  • (англ.) // : 18th Annual International Cryptology Conference Santa Barbara, California, USA August 23–27, 1998 Proceedings / — Berlin, Heidelberg, New York City, London: , 1998. — P. 1—12. — 524 p. — ( ; Vol. 1462) — ISBN 978-3-540-64892-5 — ISSN ; —
  • , (англ.) // Journal of the ACM / — New York City: Association for Computing Machinery , 2003. — Vol. 50, Iss. 2. — P. 196—249. — ISSN ; —
  • (англ.) // : Proceedings of the thirty-eighth annual ACM symposium on Theory of computing ACM , 2005. — Vol. 39, Iss. 1. — P. 25–58. — ISBN 978-1-59593-134-4 — —
  • , (англ.) // — 2008. — Vol. E91-A, Iss. 1. — P. 150—159. — ISSN ; ; —
  • (англ.) // — , 2012. — Vol. 6, Iss. 1. — P. 1—5. — ISSN ; —

Ссылки

  • Губанова, Л. : [ 21 января 2021 ] // 101 Blockchains. — 2018. — 21 декабря.
  • // Chain Media. — 2017. — 21 ноября.
  • : [ 21 июля 2020 ] // ForkLog. — 2019. — 21 мая.


Источник —

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