4.10 Подбрасывание "честной" монеты

Настало время процитировать Джо Килиана (Joe Kilian) [831]:

Алиса и Боб хотели сыграть в "орла и решку", но монеты у них не было. Алиса предложила простой способ подбрасывать монетку мысленно.

"Сначала вы задумываете случайный бит, затем я задумаю случайный бит. Затем мы выполняем над битами "исключающее или", - предложила она.

"Но если один из нас не будет задумывать биты случайным образом?", - спросил Боб.

"Это не важно. Если хотя бы один из битов действительно случаен, то и "исключающее или" битов должно быть действительно случайным", - ответила Алиса, и после минутного раздумья Боб согласился.

Немного спустя Алиса и Боб наткнулись на книгу по искусственному интеллекту, лежащую на обочине дороги. Алиса, добропорядочная гражданка, сказала: "Один из нас должен подобрать эту книгу и сдать ее в бюро находок". Боб согласился, и предложил использовать их протокол подбрасывания монетки, что бы определить, кто унесет книгу.

"Если полученный бит будет 0, то ты возьмешь книгу, а если 1 - то я", - сказала Алиса. " Какой у тебя бит?"

Боб ответил: "1".

"Ну вот, и у меня такой же", - лукаво заметила Алиса. - "Я думаю, у тебя сегодня неудачный день".

Очевидно, у протокола подбрасывания монетки есть серьезный дефект. Хотя это правда, что "исключающее или" действительно случайного бита, x, и любого независимо распределенного бита, y, дает в результате действительно случайный бит, протокол Алисы не гарантирует, что два бита будут распределены независимо. На самом деле нетрудно убедиться, что не существует мысленного протокола, который позволит двум независимым сторонам подбрасывать "честную" монетку. Алиса и Боб горевали, пока не получили письмо от неизвестного студента с дипломом по криптографии. Информация в письме была слишком теоретической, чтобы ее можно было применить для чего-то земного, но конверт, в котором пришло письмо, оказался чрезвычайно полезным.

Когда Алиса и Боб в следующий раз захотели подбросить монетку, они изменили первоначальный протокол. Сначала бит задумал Боб, но вместо того, чтобы открыть его немедленно, он записывает свой бит на листке бумаги и кладет листок в конверт. Затем Алиса объявляет свой бит. Наконец, Алиса и Боб достают бит Боба из конверта и вычисляют случайный бит. Этот бит уже действительно случаен, независимо от честности играющих. Алиса и Боб получили работающий протокол, социально значимая мечта криптографов осуществилась, и все они жили долго и счастливо.

Эти конверты выглядят весьма похожими на blob-объекты вручения бита. Когда Мануэль Блам (Manuel Blum) столкнулся с проблемой подбрасывания "честной" монеты по модему [194], он решил ее, используя протокол вручения бита:

1. Алиса вручает случайный бит, используя любую из схем вручения бита, описанную в разделе 4.9.

2. Боб загадывает свой бит.

3. Алиса раскрывает бит Бобу. Боб выигрывает бросок, если он правильно загадал бит.

В общем случае, нам нужен протокол со следующими свойствами:

• Алиса должна "бросить монету" до того, как Боб загадает свой бит.

• Алиса не должна иметь возможности изменить результаты своего броска, узнав бит Боба.

• У Боба не должно быть возможности узнать результат броска перед тем, как он сделает свое предположение.

Существует несколько возможностей выполнить это.

Бросок монеты с помощью однонаправленных функций

Если Алиса и Боб договорятся об однонаправленной функции, протокол прост:

1. Алиса выбирает случайное число, x. Она вычисляет y=f(x), где f(x) - однонаправленная функция.

2. Алиса посылает y Бобу.

3. Боб предполагает, что x четно или нечетно, и посылает свое предположение Алисе.

4. Если предположение Боба правильно, результатом броска является "орел", если неправильно - то "решка". Алиса объявляет результат броска монеты и посылает x Бобу.

5. Боб проверяет, что y=f(x).

Безопасность этого протокола обеспечивается однонаправленной функцией. Если Алиса сможет найти x и x', такие что x - четно, а x' - нечетно, и y=f(x)= f(x'), то она каждый раз сможет обманывать Боба. Кроме того, наименьший значащий бит f(x) должен быть некоррелирован с x. В противном случае Боб сможет обманывать Алису, по крайней мере иногда. Например, если f(x) в 75 процентах случаев четна, если x, у Боба будет преимущество. (Иногда наименьший значащий бит не является лучшим выбором для использования в приложении, потому что его вычисление может оказаться слишком простым.)

Бросок монеты с помощью криптографии с открытыми ключами

Этот протокол работает как с криптографией с открытыми ключами, так и с симметричной криптографией. Единственное условие - переключение алгоритма. То есть:

В общем случае это свойство не выполняется для симметричных алгоритмов, но справедливо для некоторых алгоритмов с открытыми ключами (например, RSA с идентичными модулями). Этот протокол:

1. И Алиса, и Боб создают пары открытый ключ/закрытый ключ.

2. Алиса создает два сообщения, одно для "орла", а второе - для "решки". Эти сообщения должны включать некоторую случайную строку, чтобы она могла подтвердить их подлинность на последующих этапах протокола. Алиса шифрует оба сообщения своим открытым ключом и посылает их Бобу в произвольном порядке.

E_A(M₁), E_A(M₂)

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

E_В(E_A(M))

где M - M₁ или M₂.

2. Алиса, которая не может прочитать полученное сообщение, расшифровывает его своим закрытым ключом и посылает обратно Бобу.

D_A(E_В(E_A(M)))= E_В(M₁), если M = M₁, или E_В(M₂), если M = M₂.

3. Боб расшифровывает сообщение своим закрытым ключом, раскрывая результат броска монеты, и посылает расшифрованное сообщение Алисе.

D_В(E_В(M₁)) или D_В(E_В(M₂))

4. Алиса читает результат броска монеты и проверяет, что случайная строка правильна.

5. Алиса и Боб раскрывают пары своих ключей, чтобы каждый из сторон могла убедиться в отсутствии мошенничества.

Этот протокол самодостаточен. Любая сторона может немедленно обнаружить мошенничество другой, и не требуется третья сторона ни для участия в протоколе, ни в качестве арбитра после завершения протокола. Чтобы посмотреть, как это работает, давайте попытаемся смошенничать.

Если выиграть, смошенничав, хочет Алиса, у нее есть три возможных пути повлиять на результат. Во первых, она может зашифровать два сообщения для "орла" на этапе (2). Боб обнаружит это, когда Алиса раскроет свои ключи на этапе (7). Во вторых, она может использовать какой-то другой ключ для расшифровывания сообщения на этапе (4). Это приведет к бессмыслице, которую Боб и обнаружит на этапе (5). В третьих, она может объявить неправильным сообщение на этапе (6). Боб также обнаружит это на этапе (7), когда Алиса не сможет доказать, неправильность сообщения. Конечно, Алиса может отказаться от участия в протоколе на любом этапе, когда жульничество Алисы станет для Боба очевидным.

Если Боб захочет мошеннически выиграть, его положение ничуть не лучше. Он может неправильно зашифровать сообщение на этапе (3), но Алиса обнаружит обман, взглянув на заключительное сообщение на этапе (6). Он может заявить, что неправильно выполнил этап (5) из-за какого-то мошенничества со стороны Алисы, но эта форма жульничества вскроется на этапе (7). Наконец, он может послать Алиса сообщение о "решке" на этапе (5), независимо от расшифрованного сообщения, но Алиса сможет немедленно проверить достоверность сообщения на этапе (6).

Бросок монеты в колодец

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

Генерация ключей с помощью броска монеты

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