272
вать, то f (x) должна скрывать, по меньшей мере, один из битов xi своего прообраза
x, который, по-видимому, подразумевает, что исключающее ИЛИ для всех битов
x сложно вычислить. Несмотря на свою привлекательность, этот аргумент неве-
рен.
Чтобы увидеть это, допустим, что g - это односторонняя функция и определим
. Нетрудно показать, что f является односторонней. Тем не
менее очевидно, что f (x) не скрывает значение
потому, что это
часть его выхода; следовательно, hc(x) не является трудным предикатом f . Распро-
странив это, можно показать, что для любого фиксированного предиката hc имеется
односторонняя
функция f, для которой hc не является трудным предикатом f .
Тривиальные трудные предикаты. Некоторые функции имеют «тривиаль-
ные» трудные предикаты. Например,
пусть f - функция, которая сбрасывает
последний бит своего входа (i.e., f (x1 • • • xn) = x1 • • • xn−1).
Трудно опреде-
лить xn с учетом f (x) поскольку xn не зависит от выхода; таким образом, hc(x) =
xn является трудным предикатом f . Однако f не является односторонней. Когда
мы используем трудные предикаты для наших конструкций, становится ясно,
почему тривиальные трудные предикаты такого рода бесполезны.
От односторонних функций к псевдослучайности
Цель настоящей главы заключается в том, чтобы показать, как конструировать
псевдослучайные генераторы, функции и перестановки на основе односторон-
ней функции/перестановки. В этом разделе мы дадим обзор этих конструкций.
Подробности приведены в следующих разделах.
Трудный предикат из какой-либо односторонней функции. Первый этап
существует для того, чтобы показать, что трудный предикат существует для од-
носторонней функции. На самом деле, вопрос истинности этого утверждения
остается открытым; мы покажем что-то менее строгое, но достаточное для на-
ших целей. А именно, мы покажем, что задав одностороннюю функцию f можно
построить
другую одностороннюю функцию g, вместе с трудным предикатом g.
ТЕОРЕМА 7.5 (
теорема Голдрейха - Левина (Goldreich–Levin)) Предположим,
что существуют односторонние функции (соотв., перестановки). Тогда существует
односторонняя функция (соотв., перестановка) g и трудный предикат hc функции g.
Пусть f - односторонняя функция. Функции g и hc строятся следующим об-
разом: зададим g(x, r) (f (x), r), для |x| = |r|, и
определим
где xi (resp., ri)обозначает i-й бит x (соотв., r). Обратите внимание на то, что если
r является равномерным, то hc(x, r) выходы исключающего ИЛИ случайного
подмножества битов x. (Если ri = 1, то бит xi исключается в XOR, и в противо-
273
ложном случае нет). Теорема Голдрейха-Левина, по существу, утверждает, что
если f является односторонней функцией, то f (x) скрывает исключающее ИЛИ
случайного подмножества битов x.
Достарыңызбен бөлісу: