Введение в современную криптографию
Эксперимент неразличимости
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
| Эксперимент неразличимости PRG PRGA,G(n):
(a) Выбирается единообразный бит b ∈ {0, 1}. Если b = 0, то выбрать единообразный r ∈ {0, 1}A(n); если b = 1, то выбрать единообразный s ∈ {0, 1}n и установить r := tt(s). (b) Противник A получает r, и выдает бит br. (c) Исход эксперимента является 1 , если br = b, и 0 в противном случае. Предоставьте определение псевдослучайного генератора на основе этого эксперимента, и докажите, что ваше определение эквивалентно Определению 3.14. (То есть, покажите, что tt удовлетворяет ваше определение тогда и только тогда, когда оно удовлетворяет Определение 3.14.) Пусть tt будет псевдослучайным генератором с коэффициентом расширения A(n) > 2n. В каждом из следующих случаев, скажите, обязательно ли ttr — псевдослучайный генератор. Если да, предоставьте доказательство. Если нет, предоставьте контрпример. (a) Определите ttr(s) tt(s1 • • • s|n/2J), где s = s1 • • • sn. (b) Определите ttr(s) tt .0|s|»s.. (c) Определите ttr(s) tt(s) « tt(s + 1). 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). жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|