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

Таким образом, приведенный выше пример иллюстрирует именно тот случай, в котором не блоб сам по себе (некий граф, который изоморфен и G, и Я) определяет некоторый бит информации, а, скорее, знание Алисы об этом блобе (фактический изоморфизм, известный Алисе, между этим графом и либо графом О, либо графом Я).

Более практичный, хотя в техническом отношении и более сложный пример такого же типа схемы битовых обязательств основан на предположении о трудности решения задачи дискретного логарифмирования (см. § 4.1) [112, 62]. Пусть р - большое простое число и пусть а является примитивным (первообразным) корнем по модулю р (порождающим Z* - мультипликативную группу обратимых элементов кольца классов вычетов по модулю р). Напомним, что для любого заданного целого числа у можно легко вычислить mod р, но до сих пор не известно никакого эффективного алгоритма обращения этой процедуры Более того, предположим, что вычисление у из. а, р и о mod р остгьется практически невыполнимым, даже если известно разложение числа р - 1.

Сначала Алиса и Боб договариваются о подходящем простом числе р, для которого им обоим известно разложение числа р - 1.

Они также договариваются об а, генераторе Zp. Благодаря своему знанию множителей р - 1, они оба могут с определенностью убедиться, что р и в самом деле простое число, а а является генератором Z* [236]. Указанные параметры ржа могут быть сделаны общедоступными в том смысле, что к ним можно предоставить доступ всем, кто згосочет принять участие в протоколах битовых обязательств. Вначале Боб выбирает, помимо всего прочего, случайное число s £ Zp такое, что s ф I, я передает его Алисе. Согласно нашему предположению, Алиса не может вычислить е, О е р - 2, для которого s = (mod р).

Затем, для того чтобы принять в качестве обязательства значение некоторого бита 6, Алиса выбирает случайным образом число у, лежащее в интервале от О до р - 2, и вычисляет X = sa mod p. После этого она передает х, которое и является блобом. Бобу, но сохраняет в секрете у в качестве своего удостоверения этого блоба, позволяющего ей открывать х как бит 6. Ясно, что как в качестве обязательства О, так и в качестве обязательства 1, Алисой может быть использован любой элемент Z*, который зависит только от ее знаний о нем. Более того, элементы Zp, получаюнщеся с помощью этого процесса, имеют равномерное распределение вероятностей, независящее от того бита, который Алиса пожелает взять в качестве обязательства. Следовательно, свойство (с) здесь также безусловно справедливо - блобы, принятые в качестве обязательств Алисой, не содержат никакой информации о том способе, которым она могла бы их раскрыть. Свойство (Ь) удовлетворяется в вычислительном смысле, потому что Алиса могла бы легко получить е (что, как мы предположили, является для нее практически неосуществимым) из знания Уо и yi таких, что = s • (mod р), поскольку тогда е = 2/1 - J/2 mod (р - 1). Наконец, свойство (d) выполняется, потому что Алиса выбирает у случайно.

Предположение о трудности решения задачи дискретного логарифмирования может также использоваться для реализации схемы битовых обязательств дуального типа [78]. Снова, пусть р - большое простое число, и пусть а является генератором Z*. Пусть и - наименьшее целое, такое, что 2" не делит р - 1- Для любого заданного s S Z* обозначим через hard{s) u-тый младший значащий бит единственного целого числа е, такого, что О ер - 2и8 = mod р. В предположении о сложности

задачи дискретного логарифмирования практически ничего невозможно узнать о hard{s) (при заданных лишь р, а и случайно выбранном s), потому что доказано, что решение этой задачи является столь же трудным, сколь и само дискретное логарифмирование (в сильном вероятностном смысле) [285] (хотя и - 1 младших значащих битов е могут быть легко вычислены для данного s).

Сначала Алиса и Боб договариваются о р и а точно так же, как и в предыдущем примере. Для того чтобы задаться некоторым битом Ь, Алиса случайным образом выбирает целое число у, лежащее на отрезке от О до р-2 и, кроме того, полагает 6 равным и-тому младшему значащему биту у. Затем она вычисляет блоб X = mod р и передает его Бобу. Ясно, что тогда свойства (а) и (d), определяюпще этот блоб, вьтолняются точно так же, как и в двух предыдущих реализациях битовых обязательств. Однако свойство (Ь) теперь справедливо безусловно, потому что а является генератором Z*. Следовательно, дискретный логарифм х определяется однозначно, а это значит, что также однозначно задается и и-тый младший значащий бит у. Наконец, свойство (с) выполняется с вычислительной точки зрения при сделанном ранее криптографическом предположении, так как бит, закодированный блобом S, суть ни что иное, как hard(s).

В [78] были предложены некоторые другие схемы битовых обязательств. Существует также реализация, которая остается нераскрываемой, даже если и Алиса, и Боб имеют неограниченные вычислительные ресурсы, но она основывается на постулатах квантовой физики. Кроме того, еще одно применение является безусловно нераскрываемым для всех сторон, которые взаимодействуют в многопользовательской среде (смотрите § 5) в предположении, что не более одной трети всех участников этого взаимодействия являются нечестными [111, 37].

§ 3. Доказательства с наименьшим pacKpbiTiieM

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

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