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

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.

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

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