4. Протоколы типа «подбрасывание монеты по телефону»

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

неосторожности «выпустит информацию из рук» преждевременно, то в обмен он может получить совсем не то, о чем договаривались, или вообще не получить ничего: проблемы здесь те же, что и в «протоколе» обмена расписки на ассигнации у Чичикова и Собакевича.

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

Если же Алиса и Боб удалены друг от друга и могут общаться лишь по каналу связи, то задача о жребии, на первый взгляд, кажется неразрешимой. В самом деле, если, следуя обычной процедуре подбрасывания монеты, первый ход делает Алиса, которая выбирает один из возможных вариантов — «орел» или «решка», то Боб всегда может объявить тот исход, который ему выгоден.

Тем не менее, эта задача была решена Блюмом [14]. Любопытно, что даже в заголовке своей работы Блюм охарактеризовал предложенный им метод как метод «решения нерешаемых задач».

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

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

Ниже мы излагаем криптографическую реализацию той же идеи, основанную на задаче дискретного логарифмирования, и используем при этом обозначения из раздела 2.