Введение в современную криптографию


Эксперимент неразличимости



Pdf көрінісі
бет83/249
Дата14.06.2023
өлшемі6.4 Mb.
#475029
1   ...   79   80   81   82   83   84   85   86   ...   249
Криптография Катц

Эксперимент неразличимости 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).


Достарыңызбен бөлісу:
1   ...   79   80   81   82   83   84   85   86   ...   249




©dereksiz.org 2024
әкімшілігінің қараңыз

    Басты бет