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

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

Дополнительную теорию и применения подписей с обнаружением подделки можно найти в [1239, 1241, 730, 731].

4.8 Вычисления с зашифрованными данными

Алиса хочет знать решение для некоторой функции f(x) для некоторого конкретного значения x. К несчастью, ее компьютер сломан. Боб хочет вычислить для нее значение f(x), но Алиса не хочет, чтобы Боб знал ее x. Как Алисе позволить Бобу провести вычисление )и не сообщить ему x?

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

4.9 Вручение битов

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

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

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

Боб: "Подберите-ка для меня пяток акций. Если на них удастся заработать, я передам свой бизнес вам."

Алиса: "Если я подберу пять акций для вас, вы сможете вложить в них деньги, не заплатив мне. Почему бы мне не показать вам пять акций, которые я подобрал в прошлом мес яце?"

Боб: "Откуда я знаю, что вы не подменили результаты вашего выбора, узнав настоящие. Если вы сообщите мне о своем выборе сейчас, я буду уверен, что вы не подмените результат. Я не буду вкладывать деньги в эти акции, пока я не оплачу ваши услуги. Поверьте мне."

Алиса: "Я лучше покажу вам свою подборку акций за прошлый месяц. Я не подменяла их. Поверьте мне."

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

Вручение битов с помощью симметричной криптографии

Этот протокол вручения битов использует симметричную криптографию :

(1)Боб генерирует строку случайных битов, R, и посылает ее Алисе.

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

EK(R,b)

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

Когда для Алисы придет время раскрыть свой бит, протокол продолжается :

(3)Алиса передает Бобу ключ.

(4) Боб расшифровывает сообщения, узнавая бит. Он проверяет свою случайную строку, убеждаясь в пр а-вильности бита.

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

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

Этот протокол использует однонаправленные функции:

(1)Алиса создает две случайных строки битов, Ri и R2. Ri, R2

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

(Ri, R2, Ъ)

(3)Алиса вычисляет однонаправленную функцию для сообщения и посылает результат вместе с одной из случайных строк Бобу.

H(Ri, R2, Ъ), Ri

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

Когда для Алисы придет время раскрыть свой бит, протокол продолжается :

(4)Алиса отправляет Бобу первоначальное сообщение. (Ri, R2, Ъ)

(5)Боб вычисляет однонаправленную функцию для сообщения и сравнивает его и Ri со значением однонаправленной функции и случайной строкой, полученными на этапе (3). Если они совпадают, то бит прав и-лен.

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

Не нужна и случайная строка Боба, так как результат Алисиного вручения - это сообщение, обработанное однонаправленной функцией. Алиса не может смошенничать и подобрать другое сообщение (Ri, R2, Ъ), для которого H(Ri, R2, Ъ)= H(Ri, R2, Ъ). Посылая Бобу Ri, она вручает значение b. Если Алиса не сохранит в секрете R2, то Боб получит возможность вычислить H(Ri, R2, Ъ) и H(Ri, R2, Ъ), получая возможность увидеть, что же он получил от Алисы.

Вручение бита с помощью генератора псевдослучайной последовательности

Этот протокол даже проще [1137]:

(1)Боб создает строку случайных битов и посылает ее Алисе. Rb

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

(a)выход генератора, если бит Боба равен 0, или

(b)XOR выхода генератора и бита Боба, если Бит Боба равен 1. Когда для Алисы придет время раскрыть свой бит, протокол продолжается :

(3)Алиса посылает Бобу свою стартовую последовательность.

(4)Боб выполняет этап (2), убеждаясь, что Алиса действует честно.

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

Blob-объекты

Строки, которые Алиса посылает Бобу для вручения бита, иногда называют blob-объектами. Blob-объект -это последовательность битов, хотя протоколы этого и не требуют. Как сказал Жиль Брассар (Gilles Brassard), "Они могли бы быть сделаны и из волшебной пыли, если бы это было полезным " [236]. Blob-объекты обладают следующими четырьмя свойствами:

1.Алиса может вручить blob-объекты. Вручая blob-объект, она вручает бит.

2.Алиса может открыть любой blob-объект, который она вручила. Когда она открывает blob-объект, она может убедить Боба в значении бита, который был вручен вместе с blob-объектом. Следовательно, она не может открыть произвольный blob-объект, например, ноль или единицу.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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