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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Данный пример был придуман Мануэлем Блюмом и описан в его работе в 1986 году[9]. Назовем проверяющую сторону Петей, а доказывающую сторону Димой (в англоязычной литературе обычно используются пары 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/2n, что может быть меньше любой заранее заданной величы при достаточном числе раундов.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  1. A.De Santis, S. Micali, and G.Persiano, "Non-Interactive Zero-Knowledge Proof Systems, " Advances in Cryptology CRYPTO '87 Proceedings,Springer Verlag, 1988, pp. 52-72
  2. M.Blum, P. Feldman, and S.Micali, "Non Interactive Zero-Knowledge and Its Applications, "Proceedings of the 20th ACM Symposilzm on Theory of Computing, 1988, pp. 103—112.
  3. Blum, Manuel (1988). «Non-Interactive Zero-Knowledge and Its Applications»: 103–112. DOI:10.1145/62212.62222.
  4. Sahai, Amit, and Salil Vadhan. 2003. A complete problem for statistical zero knowledge. Journal of the Association for Computing Machinery 50, no. 2: 196—249
  5. Goldwasser, S.; Micali, S. & Rackoff, C. (1989), "«The knowledge complexity of interactive proof systems»", SIAM Journal on Computing (Philadelphia: Society for Industrial and Applied Mathematics) . — Т. 18 (1): 186–208, ISSN 1095-7111, doi:10.1137/0218012, <http://crypto.cs.mcgill.ca/~crepeau/COMP647/2007/TOPIC02/GMR89.pdf> 
  6. Oded Goldreich, Silvio Micali, and Avi Wigderson. . Proofs that Yield Nothing But their Validity or All Languages in NP have Zero-Knowledge Proofs. Journal of the ACM, Vol. 38, No. 3, July 1991, pages 691—729.
  7. Goldwasser, Micali Receive ACM Turing Award for Advances in Cryptography. ACM. Проверено 13 марта 2013.
  8. Quisquater, Jean-Jacques; Guillou, Louis C.; Berson, Thomas A. (1990). "How to Explain Zero-Knowledge Protocols to Your Children". Advances in Cryptology - CRYPTO '89: Proceedings 435: 628–631.
  9. M.Blum, "How to Prove a Theorem So No One Else Can Claim It, " Proceedings of the International Congress of Mathematicians, Berkeley, CA, 1986, pp. 1444—1451
  10. O.Goldreich, S.Micali, and A.Wigderson, "How to Prove All NP Statements in Zero Knowledge and Methodology of Cryptographic Protocol Design, " Advances in Cryptology CRYPTO ’86 Proceedings, Springer-Verlag, 1987, pp 171—185
  11. A.Fiat and A. Shamir, "How to Prove Yourself: Practical Solutions to Identification and Signature Problems," Advances in Cryptology CRYPTO '86 Proceedings, Springer-Verlag, 1987, pp. 186-194.
  12. A.Fiat and A. Shamir, "Unforgeable Proofs of Identify," Proceeding of security 87, Paris, 1987, pp. 147-153.
  13. T. Beth, Y. Desmedt Identification Tokens - or: Solving the Chess Grandmaster Problem (англ.) // Proceedings of the 10th Annual International Cryptology Conference on Advances in Cryptology. — London, UK: Springer-Verlag, 1990. — С. 169—177. — ISBN 3-540-54508-5.
  14. Charles, Rackoff & Daniel R., Simon (1992), "«Non-Interactive Zero-Knowledge Proof of Knowledge and Chosen Ciphertext Attack»", Advances in Cryptology (Toronto, Canada: CRYPTO) . — Т. 556 (1): 433-444, ISSN 978-3-540-46766-3, <http://link.springer.com/chapter/10.1007%2F3-540-46766-1_35> 
  15. M. Naor and M. Yung, Public-Key Cryptosysiems Provably Secure Against Chosen Ciphertext Attach, Proc. 22nd ACM Symp on Theory of Computing (1990), pp. 427-437.
  16. Chida, K., Yamamoto, G.: `Batch processing for proofs of partial knowledge and its applications', IEICE Trans. Fundam., 2008, (1), p. 150-159
  17. Peng, Kun. "Attack against a batch zero-knowledge proof system." IET Information Security 6.1 (2012): 1-5.
  18. Watrous J. Zero-knowledge against quantum attacks //SIAM Journal on Computing. – 2009. – Т. 39. – №. 1. – С. 25-58.

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

Ссылки[править | править вики-текст]