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

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

rАнтон генерирует две случайные битовые строки S₁и S₂;

r Антон присоединяет к сгенерированным S₁ и S₂ бит b, значение

которого собирается предсказать;

rАнтон вычисляет значение однонаправленной функции Н, используя в

качестве аргумента битовую строку (S₁, S₂,b), и вместе с S₁ отсылает

Борису полученный результат.

Теперь у Бориса имеется вся необходимая информация, которая не позволит Антону впоследствии изменить предсказанное значение b. Однако проверить правильность предсказания без участия Антона Борис не сможет, поскольку в этом случае ему придется вычислять Н^-1(S₁, S₂, b).

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

1. Антон посылает Борису исходную битовую строку (S₁, S₂, b).

2. Борис вычисляет H(S₁, S₂, b), а затем сравнивает вычисленное значение

и S₁ со значением и случайной битовой строкой, присланными ему Антоном на шаге 3. В случае совпадения b действительно представляет собой значение, предсказанное Антоном на шаге 2.

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

Теперь, при предсказании бита с помощью однонаправленной функции, Борису уже не обязательно генерировать какие-либо случайные битовые строки, поскольку Антон использует для предсказания однонаправленную функцию и не сможет смошенничать, составив фальшивое сообщение (S₁,S’₂,b’) такое, что H(S₁,S’₂,b’) = H(S₁,S₂,b). Антон посылает Борису случайную битовую строку S₁, чтобы у Антона не было возможности путем подбора S₁ и S₂ добиться, чтобы изменилось b и чтобы при этом было сохранено значение H(S₁,S₂,b), которое Антон ранее отослал Борису. Храня S₂ в секрете от Бориса, Антон не дает Борису вычислить значения H(S₁,S₂,b) и H(S₁,S₂,b’), а затем определить b, сравнив эти значения с тем, что прислал ему Антон.