15. Предсказание бита

Непревзойденный маг и волшебник Антон решает публично продемонстрировать свои необычайные интеллектуальные способности. Он точно знает. какую карту выберет из колоды Борис еще до того, как это сделает сам Борис! Поэтому Антон записывает название этой карты на листке бумаги, кладет листок в конверт и запечатывает его. Затем Антон передает запечатанный конверт на хранение кому-то из публики. "Возьми из колоды любую карту", — предлагает Антон Борису. Борис выбирает наугад карту и показывает зрителям: "Туз пик". Антон вскрывает конверт и извлекает из него листок бумаги, на котором, как все могут убедиться, черным по белому написано: "Туз пик". Шквал аплодисментов.

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

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

Антон может сделать предсказание, выполнив шаги протокола, который использует симметричную криптосистему:

1. Борис, генерирует случайную битовую строку S и посылает ее Антону.

2. Антон присоединяет бит b , значение которого он собирается предсказать, к S, шифрует полученную в результате битовую строку (S,b) при помощи симметричной криптосистемы E _K и некоторого секретного ключа К, а затем отсылает результат обратно Борису.

На этом завершается процесс предсказания. Поскольку Борис не может дешифровать полученное от Антона сообщение Е _K ( S , b ), то предсказание, сделанное Антоном, остается для Бориса тайной за семью печатями.

Теперь, если Антон пожелает ознакомить Бориса со своим предсказанием, они могут продолжить совместное выполнение следующих шагов протокола:

1. Антон посылает Борису ключ К.

2. С помощью К Борис расшифровывает Е _K ( S , b ) и узнает значение b . Чтобы убедиться в честности Антона, Борис проверяет, содержит ли открытый текст расшифрованного сообщения сгенерированную им случайную битовую строку S.

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

Предсказание бита с помощью однонаправленной функции

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

Антон генерирует две случайные битовые строки S ₁ и S _2;

Антон присоединяет к сгенерированным S ₁ и S ₂ бит b , значение которою собирается предсказать;

Антон вычисляет значение однонаправленной функции Н, используя в качестве аргумента битовую строку (S ₁ , S ₂ ,b), и вместе с S ₁ отсылает Борису полученный результат.

Теперь у Бориса имеется вся необходимая информация, которая не позволит Антону впоследствии изменить предсказанное значение b . Однако проверить правильность предсказания без участия Антона Борис не сможет. поскольку в этом случае ему придется вычислять H ^-1 (S ₁ ,S ₂ ,b).

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

1. Антон посылает Борису исходную битовую строку (S ₁ ,S ₂ ,b).

2. Борис вычисляет H(S ₁ ,S ₂ ,b), а затем сравнивает вычисленное значение и S ₁ со значением и случайной битовой строкой, присланными ему Антоном на шаге 3. В случае совпадения b действительно представляет собой значение, предсказанное Антоном на шаге 2.

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

Теперь, при предсказании бита с помощью однонаправленной функции. Борису уже не обязательно генерировать какие-либо случайные битовые строки, поскольку Антон использует для предсказания однонаправленную функцию и не сможет смошенничать, составив фальшивое сообщение (S ₁ S _{' 2 ,} b') такое, что H(S ₁ S _{2 ,} b') = H(S ₁ ,S ₂ ,b). Антон посылает Борису случайную битовую строку S ₁ чтобы у Антона не было возможности путем подбора S ₁ и S ₂ добиться, чтобы изменилось b и чтобы при этом было сохранено значение H(S ₁ ,S ₂ ,b), которое Антон ранее отослал Борису. Храня S ₁ в секрете от Бориса, Антон не дает Борису вычислить значения H(S ₁ ,S ₂ ,b) и H(S ₁ ,S ₂ ,b ' ), а затем определить b, сравнив эти значения с тем, что прислал ему Антон.

Предсказание с помощью генератора псевдослучайных битовых последовательностей

Для предсказания битового значения Антон может использовать генератор псевдослучайных битовых последовательностей:

1. Борис генерирует случайную битовую строку S _Б и посылает ее Антону.

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

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

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

2. Борис повторяет действия Антона, предпринятые им на шаге 2. чтобы убедиться в том, что Антон не смошенничал.

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