% 2. СхёМб! битовых обязательств

(написано вместе с Клодом Крепеу и Дэвидом Чауцом)

Понятие битового обязательства является сильным и общим примитивом для разработки секретных криптографических протоколов. Цель битового обязательства заключается в том, чтобы позволить Алисе взять на себя в качестве обязательства значение некоторого бита информации таким способом, который не позволяет Бобу узнать это значение без ее помощи, но который также не позволяет и самой Алисе его изменить. Если возможна нераскрываемая схема битовых обязательств, то бросание жребия (так, как оно описано в § 1) становится тривиальным в реализации: Алиса берет на себя в качестве обязательства значение некоторого случайно выбранного бита. Боб угадывает это значение и аннонсирует свою догадку, а Алиса показывает ему, догадался ли он на самом деле или нет. Более тщательно проработанное применение схемы битовых обязательств описывается в следующем параграфе.

Битовое обязательство реализуется посредством некоторого основного понятия, которое мы назовем <блобом-». Каждый блоб используется как обязательство либо О, либо 1. Из соображений общности мы не накладываем никаких ограничений на природу блобов. Они могут быть сделаны даже из «улыбки чеширского кота» (или из поляризованного фотона!), если это окажется полезным. Под словами: «Алиса берет (принимает на себя) в качестве обязательства некоторый блоб», или, короче: «Алиса задается некоторым блобом», мы понимаем, что Алиса хранит конкретное значение, соответствующее данному блобу «в уме» и во всех своих последующих действиях придерживается именно этого значения. Если блоб сам по себе может быть представлен в виде битовой строки, как оказывается в большинстве практических случаев, то демонстрацией принятия блоба в качестве обязательства может быть просто показ его в явном виде.

Абстрактными свойствами, которые определяют блобы, являются следующие:

(а) Алиса, может принять блобы в качестве обязательств: задаваясь некоторым блобом, она в сущности принимает в качестве обязательства некоторый бит.

(b) Алиса может раскрытъ любой блоб, который она приняла Б качестве обязательства. При этом сра может убедить Боба в том, что действительно задавалась именно указанным ею значением соответствующего бита информации, когда принимала в качестве обязательства данный блоб. Таким образом, никакой из блобов не может быть «раскрыт» ею и как О, и как 1.

(c) Боб не в состоянии узнать ничего о том, каким образом Алиса может раскрыть какой бы то ни было нераскрытый блоб, который она приняла как обязательство. Это остается справедливым даже после того, как другие блобы уже были раскрыты Алисой.

(d) Блобы не содержат никакой побочной информации: блобы сами по себе, так же как и тот процесс, посредством которого Алиса принимает их в качестве обязательств и раскрывает, не коррелируется никаким другим секретом, который она может захотеть утаить от Боба.

Рассмотрим следующую иллюстрацию реализации блоба. Когда Алиса хочет принять в качестве обязательства некоторый бит (свойство (а)), она пишет его значение на полу и до того, как Боб сможет его увидеть, заклеивает его непрозрачной липкой лентой. Тогда, с одной стороны. Боб не может сказать, какой бит скрыт под лентой (свойство (с)), а с другой - Алиса после этого в присутствии Боба уже не может изменить значение заклеенного бита. Для того чтобы «раскрыть блоб» (свойство (Ь)), Алиса позволяет Бобу отклеить ленту и взглянуть на этот бит. Свойство (d) удовлетворяется, если ни способ, с помощью которого значение бита было записано на полу, ни сама лента, ни ее местоположение не коррелируются никаким секретом, который Алиса могла бы захотеть скрыть от Боба.

Если блобы используются в рамках общепринятого криптографического протокола, в процессе которого происходит обмен электронными сообщениями, то сами они также должны быть представлены в цифровом виде. В этом случае, казалось бы, налицо явное противоречие между свойствами, которым должны удовлетворять блобы. Из свойства (Ь) следует, что блобы, которые Алиса может открыть как О, должны отличаться от тех.

которые она может открыть как 1. Но тогда что же воспрепятствует Бобу обнаружить это различие и нарушить, таким образом, свойство (с)?

Суть одного из возможных ответов на такой вопрос состоит в том, что значение принятого бита должно определяться не самим по себе блобом, а скорее знанием Алисы о нем. Если эту идею реализовать аккуратно, то для Боба становится невозможным узнать что бы то ни было о том, каким образом Алиса может раскрыть любой еще нераскрытый ею блоб, который она приняла в качестве обязательства. Причем можно добиться, что это будет справедливо в самом сильном теоретико-информационном смысле. Тем не менее дополнительные знания могут в принципе позволить Алисе нарушить свойство (Ь).

С другой стороны, если мы настаиваем на том, чтобы свойство (Ь) выполнялось безусловно, требуется принять двойственное решение, заключающееся в том, что блобы, используемые Алисой как обязательство О, должны быть отличимы от тех, которые она использует в качестве обязательства 1. В этом случае она неизбежно задается неким особым битом всякий раз, когда принимает в качестве обязательства некоторый блоб, и, как следствие этого, Боб может в принципе нарушить свойство (с). Несмотря на то, что оба подхода предоставляют возможность одной из сторон смошенничать, это может быть сделано вычислительно неосуществимым при соответствующих криптографических предположениях.

В качестве элементарного (хотя, быть может, и не очень надежного) примера рассмотрим два изоморфных графа G и Я, о которых Алиса и Боб условились заранее. Предположим, что Алиса убеждена в том, что они изоморфны, хотя в действительности и не знает никакого изоморфизма между ними. Более того, предположим, что она неспособна в вычислительном смысле найти такой изоморфизм за приемлемое время. (Давайте отложим до § 3 вопрос о том, каким образом Алиса может убедиться в том, что данные графы являются изоморфными, не узнав при этом самого изоморфизма.) В этих предположениях Алиса дого-варивгштся с Бобом, что любой граф, для которого она сможет указать изоморфизм с G (соответственно с Н) является принятием в качестве обязательства бита О (соответственно 1).

Что касается свойств, определяюпщх блобы, то в приведен-