Введение в современную криптографию
Увеличение коэффициента расширения
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
- Бұл бет үшін навигация:
- ТЕОРЕМА 7.20
- ДОКАЗАТЕЛЬСТВО
| Увеличение коэффициента расширения
Теперь покажем, что коэффициент расширения псевдослучайного генератора может быть увеличен на любую требуемую (полиномиальную) величину. Это означает, что предыдущая конструкция с коэффициентом расширения A(n) = n + 1 достаточна для построения псевдослучайного генератора с произвольным (полиномиальным) коэффициентом расширения. ТЕОРЕМА 7.20 Если существует псевдослучайный генератор tt с коэффи- циентом расширения n + 1, то для любого полинома poly существует псевдос- лучайный генератор ttˆ с коэффициентом расширения poly(n). ДОКАЗАТЕЛЬСТВО Сначала рассмотрим построение псевдослучайного генератора ttˆ , который выводит n + 2 битов.ttˆ работает следующим образом: При заданном начальном значении s ∈ {0, 1}n вычисляется t1 := tt(s), чтобы получить n + 1 псевдослучайных битов. Затем начальные n биты из t1 снова ис- пользуются в качестве начального значения для tt; результирующие n +1 битов, последовательно соединенных с последним битом t1, что дает (n + 2)-битный выход. (См. рис. 7.1). Второе применение tt использует псевдослучайное на- чальное значение, а не случайное. Доказательство, которое мы приведем далее, показывает, что это не влияет на псевдослучайность вывода. Теперь докажем, что ttˆ является псевдослучайным генератором. Определим три последовательности распределений {H0}n=1,..., {H1}n=1,... и {H2}n=1,..., где каждое из H0, и Hn является распределением строк длиной n + 2. В распре- делении Hn выбирается равномерная строка t0 ∈ {0, 1}n, и выход – это ttˆ(t0). В распределении n, выбирается равномерная строка t1 ∈ {0, 1}n+1и анализируется как s1||σ1 (где s1 –начальные n битов t1 и σ1 – конечный бит). Выход равен t2 := tt(s1)||σ1. В распределении H2, выход является равномерной строкой t2∈{0, 1}n+2. Обозначим как t2 ← Hi процесс генерации (n + 2)-битной строки t2 в соответ- ствии с распределением Hi . Зафиксируем произвольный вероятностный полиномиально-временной от- личительный признак D. Сначала покажем, что существует пренебрежимо ма- лая функция neglr, такая что 285 Чтобы убедиться в этом, рассмотрим полиномиально-временной отличитель- ный признак Dr , который на входе t1 ∈ {0, 1}n+1, анализирует t1 как s1||σ1 с |s1| = n, вычисляет t2 := tt(s1)||σ1, и выводит D(t2). Очевидно, что Dr действует в течение полиномиального времени. Заметим, что: 1. Если t1 –равномерно, то распределение по t2 , сгенерированое Dr точно такое, как распределение H1n. Таким образом, 2. Если t1 = tt(s) для равномерного s ∈ {0, 1}n, то распределение по t2, сгене- рированное Dr то же, что и в распределении H0 n. То есть, Псевдослучайность tt предполагает, что существует пренебрежимо маля функция neglr с Выражение (7.4) соблюдается.Далее мы утверждаем, что существует прене- брежимо малая функция neglrr, такая что Чтобы убедиться в этом, рассмотрим полиномиально-временной отличи- тельный признак Drr , что на входе w ∈ {0, 1}n+1, выбирает равномерное σ1 ∈ {0, 1}, задает t2 := w||σ1 и выводит D(t2). Если w равномерное, то такое же и t2; поэтому, С другой стороны, если w = tt(s) для равномерного s ∈ {0, 1}n, то t2 распреде- ляется так же в соответствии с H1 и, таким образом Как и ранее, псевдослучайность tt предполагает выражение (7.5). 286 Сложив все вместе, имеем используя выражения (7.4) и (7.5). Так как D был произвольным полиноми- ально-временным отличительным признаком, это доказывает, что ttˆ является псевдослучайным генератором. жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|