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

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

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

2. Антон присоединяет бит b, значение которого он собирается

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

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

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

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

2. С помощью К Борис расшифровывает E_K (S,b) и узнает значение b.

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

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

―

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