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

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

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

2. Антон вычисляет случайное начальное значение для генератора

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

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

1. Антон высылает Борису случайное начальное значение, вычисленное

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

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

убедиться в том, что Антон не смошенничал.

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