115
матически
без любого человеческого вмешательства, из-за чего CAPTCHA теряет
эффективность. Хотя можно пребегнуть к специальным мерам (например, SC воз-
вращает произвольное изображение вместо ошибки расшифровки), на самом деле
необходимо использовать
шифровальную схему, устойчивую к АВШ .
Упражнения
Докажите Предположение 3.6.
Докажите, что Определение 3.8 не удовлетворяется, если Π может зашиф-
ровать сообщения произвольной длины, и противник не ограничен условием
выдавать сообщения одинаковой
длины в эксперименте
Подсказка: Пусть q(n) — полиномиальное максимальное значе-
ние длины шифртекста, когда Π используется для шифрования еди-
ничного бита. Затем, рассмотрим противника, который выдает m0 ∈
{0, 1} и равномерное m1 ∈ {0, 1}q(n)+2 .
Скажем, что Π = (Gen, Enc, Dec), такое что k ∈ {0, 1}n, алгоритм Enck опреде-
лен только для сообщений максимально длины A(n) (для некоторого полиноми-
ального A). Постройте схему, удовлетворяющую Определение 3.8, даже когда
противник не ограничен условием выдавать сообщения одинаковой длины в
эксперименте
.
Докажите, что Определение 3.8 и 3.9 эквивалентны.
Пусть |tt(s)| = A(|s|) для некоторого A. Рассмотрим следующий эксперимент:
Достарыңызбен бөлісу: