ИНФОРМАТИКА

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