Построение псевдослучайных функций

290
tt мы могли бы определить, что Fk (i) (для 0 ≤ i < 2n) будет i-м n-битным блоком 
tt(k). Причина того, что это не работает, состоит в том, что F должна быть эф-
фективно вычисляемой; существует экспоненциальное множество блоков и нам 
требуется способ, вычислить i-й блок, не вычисляя все другие блоки.
Мы будем делать это, вычисляя «блоки» выходных данных, идя вниз по двоич-
ному дереву. Сначала проиллюстрируем конструкцию, показав псевдослучайную 
функцию, использующую 2-битные входы. Пусть tt будет псевдослучайным гене-
ратором с коэффициентом расширения 2n. Если использовать tt как в доказатель-
стве теоремы 7.20, то можно получить псевдослучайный генератор ttˆ с коэффи-
циентом расширения 4n , который использует три инициирования tt. (Мы создаем 
n дополнительных псевдослучайных битов каждый раз, когда применяется tt ). 
Если определить, что Fr (i) (где 0 ≤ i < 4 и i кодируется как 2-битная двоичная 
строка) будет i-м блоком ttˆ(k), то вычисление Fr (3) потребует вычисления всех 
ttˆ и, следовательно, трех инициализаций tt. Теперь покажем, как построить псев-
дослучайную функцию F, используя только две инициализации tt на любом входе.
Пусть tt0 и tt1 будут функциями, обозначающими первую и вторую половину 
выхода tt; т.е., tt(k) = tt0(k) « tt1(k), где |tt0(k)| = |tt1(k)| = |k|. Определим F следу-
ющим образом:
Fk (00) = tt0(tt0(k)) 
Fk (10) = tt0(tt1(k))
Fk (01) = tt1(tt0(k)) 
Fk (11) = tt1(tt1(k)).
Мы утверждаем, что четыре строки, приведенные выше, являются псевдос-
лучайными, даже если их рассматривать вместе. (Этого достаточно, чтобы 
доказать, что F –псевдослучайная). Интуитивно понятно, что это происходит 
потому, tt0(k)||tt1(k) = tt(k) – псевдослучайно и, следовательно, неотличимо от 
2n-битной строки k0||k1. Но тогда
tt0(tt0(k)) || tt1(tt0(k)) ||tt0(tt1(k)) || tt1(tt1(k)) неотличимо от
tt0(k0) || tt1(k0)|| tt0(k1) || tt1(k1) = tt(k0) || tt(k1).
Поскольку tt – это псевдослучайный генератор, приведенное выше неотличи-
мо от равномерной 4n-битной строки. Формальное доказательство использует 
гибридный аргумент.
Обобщая эту идею, мы можем получить псевдослучайную функцию на 
n-битных входах, определив
Fk (x) = ttxn (• • • ttx1 (k) • • • ),
где x = x1 • • • xn; см. конструкцию 7.21. Интуитивное понимание, почему дан-
ная функция псевдослучайная то же, что и ранее, но формальное доказатель-
ство осложняется тем фактом, что теперь имеется экспоненциальное множе-
ство рассматриваемых входов.

291
КОНСТРУКЦИЯ 7.21
Пусть tt будет псевдослучайным генератором с коэффициентом расширения 
A(n) = 2n, определим tt0, tt1 как в тексте. Для k∈{0,1}n, определим функцию 
Fk : {0,1} n → {0,1} n как
Fk(x1x2 • • • xn) = ttxn (• • • (ttx2 (ttx1 (k))) • • • ) .
Псевдослучайная функция из псевдослучайного генератора.
Полезно просмотреть эту конструкццию, как определяющую, для каждого 
ключа k∈{0, 1}n, полное двоичное дерево высоты n, в котором каждый узел 
содержит n-битное значение.
(См. рис. 7.2, в котором n = 3.) Корень имеет значение k, и для каждого вну-
треннего узла со значением kr его левый дочерний элемент имеет значение
tt0(kr), а его правый дочерний элемент имеет значение tt1(kr). Результат Fk (x) 
для x = x1 • • • xn определяется, тогда как значение на концевом узле, достиг-
нутом при движении по дереву в соответствии с битами x, где xi = 0 означает 
«иди налево» и xi = 1 означает «иди направо». (Эта функция определена только 
для входных данных длиной n, и поэтому только значения на концевых узлах 
всегда являются выходными данными). Размер дерева – степень n. Тем не ме-
нее, чтобы вычислить Fk (x) не нужно строить или сохранять все дерево; необ-
ходимы только n оценок tt.

жүктеу/скачать 6.4 Mb.

Достарыңызбен бөлісу: