В криптографии, схема обязательств или битовая схема обязательств (англ. Commitment scheme) — это криптографический примитив, который позволяет зафиксировать какое-либо выбранное значение (выбранное утверждение, бит информации), сохраняя его скрытым для других, с возможностью позже раскрыть зафиксированное значение[1]. Схемы обязательств разработаны таким образом, что сторона не может изменить значение или утверждение после отправки, то есть схемы обязательств реализуют связывание данных. Схемы обязательства находят применение в ряде криптографических протоколов, включая безопасное подбрасывание монеты, доказательство с нулевым разглашением, протокол конфиденциального вычисления и др.
Чтобы представить механизм работы схемы, рассмотрим отправителя, помещающего сообщение в закрытый на замок ящик и передающего коробку получателю. Сообщение скрыто от получателя, который не может самостоятельно открыть замок. С того момента, когда коробка с сообщением оказалась у получателя, содержимое коробки не может быть изменено отправителем — коробка просто открывается, если позднее отправитель решит передать ключ получателю.
Взаимодействие двух сторон в схеме обязательства происходит в два этапа:
- фаза передачи «Commit» — посылку закрытой на ключ коробки от отправителя к получателю (обязательство),
- фаза раскрытия «Reveal» — более поздняя отправка ключа от коробки получателю и проверка содержимого (значение).
В простых схемах обязательства фаза передачи состоит из отправки одного сообщения от отправителя к получателю. Это сообщение называется обязательством. Важно, чтобы конкретное выбранное значение не могло быть известно получателю в этой фазе (это называется скрывающим свойством). Фаза простого раскрытия будет состоять из отправления одного сообщения от отправителя к получателю, за которым следует проверка обязательства, выполняемая получателем. Значение, выбранное на этапе передачи, должно быть единственным, которое отправитель может вычислить и которое проверяется на этапе раскрытия (это называется свойством связывания).
История
правитьКонцепция схем обязательств была, возможно, впервые формализована Жилем Брассаром, Дэвидом Чаумом и Клодом Крепо в 1988 году[2] как часть различных протоколов доказательства с нулевым разглашением NP класса, основанных на разных типах схем обязательств[3]. Концепция использовалась и ранее, но без формального рассмотрения. Понятие обязательств появлялось в работах Мануэля Блума[4] и др. или как часть, скажем, сигнатуры Лампорта исходной схемы одноразовой однобитовой подписи.
Применение
правитьПодбрасывание монеты
правитьПредположим, Алиса и Боб хотят разрешить спор путем подбрасывания монеты. Если они физически находятся в одном месте, процедура проходит так:
- Алиса высказывает предположение о результате броска монеты;
- Боб подбрасывает монету;
- Если предположение Алисы правильное, она выигрывает, иначе выигрывает Боб.
Если Алиса и Боб не находятся в одном месте, возникает проблема в разрешении данного спора. После того как Алиса сделала предположение и сказала его Бобу, он может соврать о результате броска монеты так, что итог станет для него выигрышным. Точно так же, если Алиса не объявляет о своем предположении Бобу, после того, как Боб подбрасывает монету и объявляет результат, Алиса может сообщить, что она предсказала тот результат, который был выигрышным для неё. Алиса и Боб могут использовать схему обязательства в данной процедуре, что позволит им обоим доверять результату:
- Алиса высказывает предположение о броске монеты, но отправляет Бобу только обязательство;
- Боб подбрасывает монету и сообщает результат Алисе;
- Алиса раскрывает свое предположение;
- Боб проверяет, что предположение Алисы соответствует её обязательствам;
- Если предположение Алисы совпадает с результатом броска монеты, о котором сообщил Боб, Алиса побеждает, иначе побеждает Боб.
Чтобы Боб мог искажать результаты в свою пользу, он должен взломать скрытое обязательство. Если схема обязательства построена хорошо, то Боб не может исказить результаты. Также Алиса не может повлиять результат, если она не может изменить значение, которое она предсказывает до броска и связывает обязательством[4][5].
Реальное применение этой проблемы существует, когда люди (часто в средствах массовой информации) принимают решение и дают ответ в «запечатанном конверте», который открывается позднее.
Доказательства с нулевым разглашением
правитьОдним из широко известных конкретных примеров является использование схемы обязательства в доказательствах с нулевым разглашением. В данных протоколах обязательства используются для двух основных целей: во-первых, чтобы позволить отправителю участвовать в схемах, где проверяющему будет предоставлен выбор того, что проверить, а отправитель покажет только то, что соответствует выбору проверяющего. Схемы обязательств позволяют отправителю заранее указывать всю информацию и раскрывать только то, что должно быть известно позже в доказательстве[6]. Обязательства также используются в доказательствах с нулевым разглашением проверяющим, который часто указывает свой выбор заранее в обязательстве. Это позволяет составлять доказательства с нулевым знанием параллельно, не раскрывая лишнюю информацию отправителя получателю[7].
Подтверждаемый секретный обмен
правитьДругое важное применение схема обязательства находит в реализации проверяемого разделения секрета, который является критически важным базовым блоком протокола конфиденциального вычисления. В схеме разделения секрета сообщение разделяется на части — «акции», и каждая из нескольких сторон получает «акции», которые должны быть скрыты от всех, кроме обладателя конкретной части. Секрет может воссоздать только коалиция участников из первоначальной группы, причём входить в коалицию должно не менее некоторого изначально известного количества участников. Совместное использование секретных данных лежит в основе многих протоколов для безопасных вычислений: например, для безопасного вычисления функции с некоторым общим вводом, где используются секретные общие ресурсы. Тем не менее, если злоумышленники будут генерировать общие ресурсы, может возникнуть уязвимость и необходимо будет проверять правильность этих ресурсов. В проверяемой схеме разделения секрета распространение секрета сопровождается обязательствами по отдельным акциям. Обязательства не раскрывают ничего, что могло бы помочь злоумышленникам, но позволяют каждой отдельной стороне проверить, верны ли их доли, и отсеять злоумышленников[8].
Построение
правитьСхема обязательства может быть либо полностью связывающей (Алиса не может изменить содержимое коробки после передачи, даже если у неё есть неограниченные вычислительные ресурсы), либо идеально скрывающей (Боб не может открыть коробку, пока Алиса не передаст ключ, даже если он имеет неограниченные вычислительные ресурсы), но не одновременно[9].
Квантовая схема обязательства
правитьВ квантовой криптографии возникает интересный вопрос: существуют ли на квантовом уровне безусловно безопасные битовые схемы обязательства, то есть протоколы, которые (по крайней мере асимптотически) являются связывающими и скрывающими, даже если нет никаких ограничений на вычислительные ресурсы? Есть надежда, что найдется способ использовать внутренние свойства квантовой механики, как, например, в протоколе квантового распределения ключей.[10]
В 1993 году был предложен протокол для реализации битовых обязательств в рамках квантовой механики, и безусловная безопасность этого протокола была общепринятой в течение достаточно долгого времени. Однако этот результат оказался неверным. Небезопасность этого протокола, называемого протоколом BCJL, была доказана осенью 1995. В 1996 году Доминик Майерс теоретически доказал, что реализовать безусловно безопасную схему невозможно. Любой такой протокол может быть сведен к протоколу, когда система находится в одном из двух чистых состояний после фазы передачи, в зависимости от бита, который Алиса хочет зафиксировать. Если протокол идеально скрывающий, то Алиса может унитарно преобразовать эти состояния друг в друга, используя свойства разложения Шмидта, эффективно подавляя свойство связывания[11].
Примечания
править- ↑ Goldreich O. Zero-Knowledge Proofs for NP: Commitment Schemes // Foundations of Cryptography Basic Tools: Volume 1. — Cambrige University Press, 2001. — С. 224. — 372 с. — ISBN 0-511-04120-9. — ISBN 0-521-79172-3.
- ↑ Brassard G., Chaum D., Crepeau C. Minimum Disclosure Proofs of Knowledge // Journal of Computer and System Sciences. — 1998. — Т. 37. — С. 157—158. — ISSN 0022-0000. Архивировано 27 сентября 2011 года.
- ↑ Proofs That Yield Nothing but Their Validity, 1991, с. 698.
- ↑ 1 2 Blum M. Coin flipping by telephone a protocol for solving impossible problems // ACM SIGACT News. — 1983. — Т. 15, вып. 1. — С. 23–27. — ISSN 0163-5700. — doi:10.1145/1008908.1008911. Архивировано 7 декабря 2018 года.
- ↑ Naor M. Bit Commitment Using Pseudorandomness // Journal of Cryptology. — 1991. — Январь (т. 4, вып. 2). — С. 152—153. — ISSN 0933-2790. — doi:10.1007/BF00196774.
- ↑ Proofs That Yield Nothing but Their Validity, 1991, с. 721.
- ↑ Goldreich O., Krawczyk H. On the Composition of Zero-Knowledge Proof Systems // SIAM Journal on Computing. — 1996. — Февраль (т. 25, вып. 1). — С. 172. — ISSN 0097-5397. — doi:10.1137/S0097539791220688.
- ↑ Gennaro R., Rabin M. O., Rabin T. Simplified VSS and Fast-track Multiparty Computations with Applications to Threshold Cryptography // Proceedings of the Seventeenth Annual ACM Symposium on Principles of Distributed Computing. — New York, NY, USA: ACM, 1998. — С. 2—4. — ISBN 978-0-89791-977-7. — doi:10.1145/277697.277716. Архивировано 7 мая 2021 года.
- ↑ Damgard I. B., Nielsen J. B. Perfect Hiding and Perfect Binding Universally Composable Commitment Schemes with Constant Expansion Factor // BRICS Report Series. — Denmark, 2001. — Октябрь. — С. 1. — ISSN 0909-0878. Архивировано 25 октября 2020 года.
- ↑ Unconditionally secure quantum bit commitment is impossible, 1997, с. 1.
- ↑ Unconditionally secure quantum bit commitment is impossible, 1997, с. 3—4.
Литература
править- Goldreich O., Micali S., Wigderson A. Proofs That Yield Nothing but Their Validity or All Languages in NP Have Zero-knowledge Proof Systems // J. ACM. — 1991. — Июль (т. 38, вып. 3). — С. 690–728. — ISSN 0004-5411. — doi:10.1145/116825.116852.
- Mayers D. Unconditionally secure quantum bit commitment is impossible // Physical Review Letters. — 1997. — Т. 78. — ISSN 3414-3417. — doi:10.1103/PhysRevLett.78.3414.