Бросание монеты
Для разрешения неожиданно возникшего спорного вопроса Антон и Борис решают бросить монету. Однако и у того, и у другого при себе не оказалось ни одной. Тогда они решают "бросить" монету в уме: сначала Антон загадает, что выпадет – "орел" или "решка", а потом Борис подумает и объявит, какой стороной упала "брошенная" им монета. Спрашивается: могут ли Антон и Борис сделать это так, чтобы полностью быть уверенными в том, что никто из них не смошенничал?
Могут, если воспользуются криптографическим протоколом, который заставит их действовать таким образом, что:
- Антону придется бросить монету прежде, чем Борис попытается предсказать, какой стороной она упадет;
- Антон не сможет изменить результат бросания монеты после того, как услышит, на какую сторону монеты сделал свою ставку Борис;
- Борис не узнает, что выпало – "орел" или "решка", до тех пор, пока не примет окончательное решение и не сообщит о нем Антону.
Бросание монеты с помощью предсказания бита
В этом случае криптографический протокол, которого должны придерживаться Антон и Борис при бросании монеты, выглядит следующим образом:
- Антон делает предсказание битового значения в соответствии с одной из схем, описанных в разделе "Предсказание бита".
- Борис пытается догадаться, какое значение предсказал Антон, и информирует о своей догадке Антона.
- Антон сообщает Борису предсказанное значение. Борис выигрывает, если его догадка была правильной.
Бросание монеты с помощью однонаправленной функции
Если Антон и Борис сумеют заранее договориться об использовании конкретной однонаправленной функции f(x), криптографический протокол бросания монеты будет выглядеть так:
- Антон выбирает случайное число х и вычисляет значение y=f(x).
- Антон посылает у Борису.
- Борис пытается догадаться, является ли х четным или нечетным числом, и сообщает о своей догадке Антону.
- Антон информирует Бориса о том, какое число х он выбрал.
- Борис проверяет, действительно ли f(x)=y, а также узнает, была ли верна его догадка.
Здесь все зависит от свойств однонаправленной функции f. Если Антон вдруг сможет найти два числа х и х' такие, что х является четным, а х' – нечетным, и при этом y=f(x)=f(x'), то Борис всегда будет в проигрыше. Необходимо также, чтобы наименее значимый бит f(x) не зависел от х. Например, если f(x) будет четным в 90 процентах всех случаев, когда х является четным, Антон будет брать верх над Борисом почти всегда.