В криптографии, схе́ма обяза́тельств или би́товая схе́ма обяза́тельств (англ. commitment scheme) — это криптографический примитив, который позволяет зафиксировать какое-либо выбранное значение (выбранное утверждение, бит информации), сохраняя его скрытым для других, с возможностью позже раскрыть зафиксированное значение[1]. Схемы обязательств разработаны таким образом, что сторона не может изменить значение или утверждение после отправки, то есть схемы обязательств реализуют связывание данных. Схемы обязательства находят применение в ряде криптографических протоколов, включая безопасное подбрасывание монеты, доказательство с нулевым разглашением, протокол конфиденциального вычисления и др.
Чтобы представить механизм работы схемы, рассмотрим отправителя, помещающего сообщение в закрытый на замок ящик и передающего коробку получателю. Сообщение скрыто от получателя, который не может самостоятельно открыть замок. С того момента, когда коробка с сообщением оказалась у получателя, содержимое коробки не может быть изменено отправителем — коробка просто открывается, если позднее отправитель решит передать ключ получателю.
Взаимодействие двух сторон в схеме обязательства происходит в два этапа:
В простых схемах обязательства фаза передачи состоит из отправки одного сообщения от отправителя к получателю. Это сообщение называется обязательством. Важно, чтобы конкретное выбранное значение не могло быть известно получателю в этой фазе (это называется скрывающим свойством). Фаза простого раскрытия будет состоять из отправления одного сообщения от отправителя к получателю, за которым следует проверка обязательства, выполняемая получателем. Значение, выбранное на этапе передачи, должно быть единственным, которое отправитель может вычислить и которое проверяется на этапе раскрытия (это называется свойством связывания).
Концепция схем обязательств была, возможно, впервые формализована Жилем Брассаром, Дэвидом Чаумом и Клодом Крепо в 1988 году[2] как часть различных протоколов доказательства с нулевым разглашением NP класса, основанных на разных типах схем обязательств[3]. Концепция использовалась и ранее, но без формального рассмотрения. Понятие обязательств появлялось в работах Мануэля Блума[4] и др. или как часть, скажем, сигнатуры Лампорта исходной схемы одноразовой однобитовой подписи.
Предположим, Алиса и Боб хотят разрешить спор путем подбрасывания монеты. Если они физически находятся в одном месте, процедура проходит так:
Если Алиса и Боб не находятся в одном месте, возникает проблема в разрешении данного спора. После того как Алиса сделала предположение и сказала его Бобу, он может соврать о результате броска монеты так, что итог станет для него выигрышным. Точно так же, если Алиса не объявляет о своем предположении Бобу, после того, как Боб подбрасывает монету и объявляет результат, Алиса может сообщить, что она предсказала тот результат, который был выигрышным для неё. Алиса и Боб могут использовать схему обязательства в данной процедуре, что позволит им обоим доверять результату:
Чтобы Боб мог искажать результаты в свою пользу, он должен взломать скрытое обязательство. Если схема обязательства построена хорошо, то Боб не может исказить результаты. Также Алиса не может повлиять на результат, если она не может изменить значение, которое она предсказывает до броска и связывает обязательством[4][5].
Реальное применение этой проблемы существует, когда люди (часто в средствах массовой информации) принимают решение и дают ответ в «запечатанном конверте», который открывается позднее.
Одним из широко известных конкретных примеров является использование схемы обязательства в доказательствах с нулевым разглашением. В данных протоколах обязательства используются для двух основных целей: во-первых, чтобы позволить отправителю участвовать в схемах, где проверяющему будет предоставлен выбор того, что проверить, а отправитель покажет только то, что соответствует выбору проверяющего. Схемы обязательств позволяют отправителю заранее указывать всю информацию и раскрывать только то, что должно быть известно позже в доказательстве[6]. Обязательства также используются в доказательствах с нулевым разглашением проверяющим, который часто указывает свой выбор заранее в обязательстве. Это позволяет составлять доказательства с нулевым знанием параллельно, не раскрывая лишнюю информацию отправителя получателю[7].
Другое важное применение схема обязательства находит в реализации проверяемого разделения секрета, который является критически важным базовым блоком протокола конфиденциального вычисления. В схеме разделения секрета сообщение разделяется на части — «акции», и каждая из нескольких сторон получает «акции», которые должны быть скрыты от всех, кроме обладателя конкретной части. Секрет может воссоздать только коалиция участников из первоначальной группы, причём входить в коалицию должно не менее некоторого изначально известного количества участников. Совместное использование секретных данных лежит в основе многих протоколов для безопасных вычислений: например, для безопасного вычисления функции с некоторым общим вводом, где используются секретные общие ресурсы. Тем не менее, если злоумышленники будут генерировать общие ресурсы, может возникнуть уязвимость и необходимо будет проверять правильность этих ресурсов. В проверяемой схеме разделения секрета распространение секрета сопровождается обязательствами по отдельным акциям. Обязательства не раскрывают ничего, что могло бы помочь злоумышленникам, но позволяют каждой отдельной стороне проверить, верны ли их доли, и отсеять злоумышленников[8].
Схема обязательства может быть либо полностью связывающей (Алиса не может изменить содержимое коробки после передачи, даже если у неё есть неограниченные вычислительные ресурсы), либо идеально скрывающей (Боб не может открыть коробку, пока Алиса не передаст ключ, даже если он имеет неограниченные вычислительные ресурсы), но не одновременно[9].
В квантовой криптографии возникает интересный вопрос: существуют ли на квантовом уровне безусловно безопасные битовые схемы обязательства, то есть протоколы, которые (по крайней мере асимптотически) являются связывающими и скрывающими, даже если нет никаких ограничений на вычислительные ресурсы? Есть надежда, что найдётся способ использовать внутренние свойства квантовой механики, как, например, в протоколе квантового распределения ключей[10].
В 1993 году был предложен протокол для реализации битовых обязательств в рамках квантовой механики, и безусловная безопасность этого протокола была общепринятой в течение достаточно долгого времени. Однако этот результат оказался неверным. Небезопасность этого протокола, называемого протоколом BCJL[11], была доказана осенью 1995. В 1996 году Доминик Майерс (англ. Dominic Mayers) теоретически доказал, что реализовать безусловно безопасную схему невозможно. Любой такой протокол может быть сведен к протоколу, когда система находится в одном из двух чистых состояний после фазы передачи, в зависимости от бита, который Алиса хочет зафиксировать. Если протокол идеально скрывающий, то Алиса может унитарно преобразовать эти состояния друг в друга, используя свойства разложения Шмидта, эффективно подавляя свойство связывания[12].