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

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

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

1. Антон выбирает случайное число х и вычисляет значение y = f(x).

2. Антон посылает у Борису.

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

4. Антон информирует Бориса о том, какое число х он выбрал.

5. Борис проверяет, действительно ли f(x) = y, а также узнает, была ли верна его догадка.

Здесь все зависит от свойств однонаправленной функции f. Если Антон вдруг сможет найти два числа х и х' такие, что х является четным, а х' — нечетным, и при этом y = f(x) = f(x'), то Борис всегда будет в проигрыше. Необходимо также, чтобы наименее значимый бит f(x) не зависел от х. Например, если f(x) будет четным в 90 процентах всех случаев, когда х является четным, Антон будет брать верх над Борисом почти всегда.