116
Докажите обратное Теореме 3.18. А именно, покажите, что если tt — не псев-
дослучайный генератор, то Конструкция 3.17 не имеет неотличимых шифрова-
ний при наличии перехватчика.
(а) Определите понятие неотличимости для шифрования нескольких различ-
ных сообщений, в котором схема не должна скрывать, зашифровано ли одно и
то же сообщение дважды.
(b)
Покажите, что Конструкция 3.17 не удовлетворяет ваше определение.
(c) Дайте конструкцию схемы детерминистского шифрования (без сохране-
ния состояния), которая удовлетворяет ваше определение.
Докажите безусловно существование псевдослучайной функции F:
{0, 1}* × {0, 1}* → {0, 1}* с Akey (n) = n и Ain(n) = O(log n).
Подсказка: Вычислите равномерную функцию с логарифмической длиной
аргумента.
Пусть F — псевдослучайная функция, сохраняющая длину. Для следующих
конструкций функции с ключом F r : {0, 1}n × {0, 1}n−1 → {0, 1}2n, укажите,
является ли F r псевдослучайной функцией с ключом. Если является, докажите
это.
Если нет, покажите атаку.
(a) F k r (x) F k (0||x) || F k (1||x).
(b) F k r (x) F k (0||x) ||F k (x||1).
Предположим, что псевдослучайные функции существуют. Докажите, что су-
ществует схема шифрования, имеющая несколько неразличимых шифрований
при наличии перехватчика (т.е. она удовлетворяет Определение 3.19), но она не
является устойчивой против АВОТ (т.е. она не удовлетворяет Определение 3.22).
Достарыңызбен бөлісу: