как Алиса (на другом конце пpoвoдaj говорит: «Ну, хорошо... Я бросаю... Орел! Ты проиграл!»

Затруднение в этом наивном протоколе, конечно же, состоит в том, что он позволяет Алисе подменить результат жеребьевки после того, как Боб сообщил ей о своем предположении. Для того чтобы предотвратить подобный вид мошенничества. Боб должен потребовать, чтобы Алиса сначала бросила монету и зафиксировала результат. Только после этого Боб мог бы высказать свою догадку. При реализации этой идеи возникают два требования, выполнение которых приводит к осуществимому на практике протоколу: Алиса не должна иметь возможности бросать жребий после того, как она услышит предположение Боба, а Боб в свою очередь не должен иметь возможности узнать, какупадет монета до того, как он объявит о своей догадке.

Пусть f:X-Y - однонаправленная функция и предположим, что X - это конечное множество натуральных чисел, среди которых содержится одинаковое количество четных и нечетных. В предположении, что Алиса и Боб заранее договорились о функции /, Блюмом и Микэли впервые был предложен следу-юищй протокол:

Алиса выбирает случайно число х £ X, затем вычисляет значение у = f{x) и предъявляет его Бобу;

Боб пытается отгадать, является ли число х четным или нечетным, и объявляет свою догадку Алисе;

Алиса сообщает Бобу, оказался он прав или нет, и доказывает ему это, раскрывая х;

Боб посредством проверки /(ж) = у либо подтверждает, либо опровергает честность Алисы.

Суть представленного протокола заключается в том, что Алиса связывает себя (в качестве обязательства) числом х, ввиду того что она сообщает Бобу значение y=f{x), однако Боб, зная у, не может вычислить х самостоятельно, потому что функция / является однонаправленной. (В § 2 мы предпримем более детальное обсуждение общего понятия подобного битового обяза-

тельства.) Интуитивно ясно, что этот протокол является конструктивным, хотя если функция / была выбрана недостаточно тщательно (даже если она и в самом деле однонаправленная), то он все равно оставляет дверь открытой для мощенничества как со стороны Алисы, так и со стороны Боба.

Если функция / не является взаимнооднозначной, то возможно, что Алиса знает такие числа х и х, для которых f{x) = f(x) и при этом сумма х + х которых нечетна (что заранее не включалось в определение однонаправленности). В таком случае она может объявить у = f(x), фактически не связывая себя обязательством ни посредством х, ни посредством х. Следовательно, если бы это было так, то Алиса могла бы смошенничать. С другой стороны, может быть так, что функция / взаимнооднозначна и что вычисление х из /(х) практически трудноосуществимо, но его то как раз делать заведомо и не обязательно, поскольку оказывается, что четность числа х может быть легко определена из вида самого значения f{x). Но даже, если бы четность х будет трудно определить в точности для данного значения /(ж), может статься, что ее можно угадать с вероятностью успеха более, чем 50%. В этой ситуации мог бы мошенничать Боб.

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

Алиса выбирает случайным образом какое-нибудь число Блюма п и некоторое х £ Z„, затем вычисляет у = х" mod п и г = 2/ mod п, после чего сообщает числа п и г Бобу;

Боб объявляет Алисе свое предположение о том, является ли число у чётным или нечетным;

Алиса раскрывает Бобу числа ж и у, а также позволяет ему убедиться в том, что п является числом Блюма;

Боб проверяет, что и в самом деле у = ж mod п, а z = y2 mod п.

Иными словами, Алиса передает Бобу квадратичный вычет z по модулю целого числа Блюма, а Боб проверяет, является ли его примитивный квадратный корень четным или нечетным. В

этом случае Боб, как мы уже видели в § 4.5, чтобы высказать свое предположение, не может найти ничего лучшего, чем бросить жребий. С другой стороны, критично, что п является целым числом Блюма, так как в противном случае могло бы быть так, что Z имеет два квадратных корня различной четности, оба из которых являются квадратичными вычетами. Вот почему Алиса должна позволить Вобу «убедиться в том, что п является целым числом Блюма». Для этого Алиса, может сообщить Вобу разложение п на множители (теперь для Боба будет уже слишком поздно использовать эту информацию, с тем чтобы повлиять на результат своего выбора). Если же Алиса хочет применять свое целое число Блюма п еще и для других целей или использовать его в нескольких жеребьевках, то она, для того чтобы убедить Боба в своей добропорядочности, может воспользоваться интерактивным протоколом минимального раскрытия [206]. Смотрите также § 3.

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

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