Теорема о псевдослучайном генераторе

В теории сложности вычислений и криптографии существование псевдослучайных генераторов связано с существованием односторонних функций посредством ряда теорем, которые в совокупности называются теоремой о псевдослучайном генераторе .

Введение

Псевдослучайность

Распределение считается псевдослучайным , если никакие эффективные вычисления не могут отличить его от истинного равномерного распределения с существенным преимуществом . Формально семейство распределений D _n является псевдослучайным , если для любого полиномиального размера схемы C и любого ε обратно полиномиального по n

|Вероятность _{x ∈ U} [ C ( x )=1] − Вероятность _{x ∈ D} [ C ( x )=1] | ≤ ε .

Псевдослучайные генераторы

Функция G _l : {0,1} ^л → {0,1} ^м, где l < m — генератор псевдослучайных чисел, если:

G _l можно вычислить за время, полиномиальное по l
G _l ( x ) является псевдослучайным, когда x равномерно случайен.

Один дополнительный псевдослучайный бит подразумевает полиномиально большее количество псевдослучайных битов.

Можно показать, что если существует псевдослучайный генератор G _l : {0,1} ^л → {0,1} ^{л +1}, т. е. генератор, который добавляет только один псевдослучайный бит, то для любого m = поли ( l ) существует псевдослучайный генератор G' _l : {0,1} ^л → {0,1} ^м.

Идея доказательства заключается в следующем: первые s бит из равномерного распределения U _l выбираются и используются в качестве начального числа для первого экземпляра G _l , который, как известно, является генератором псевдослучайных чисел. Далее вывод первого экземпляра G _l делится на две части: первые l бит передаются во второй экземпляр G _l в качестве начального числа, а последний бит становится первым битом вывода. Повторение этого процесса m раз дает на выходе m псевдослучайных битов.

Можно показать, что такой G' _l , состоящий из m экземпляров G _l , действительно является генератором псевдослучайных чисел, используя гибридный подход и доказательство от противного следующим образом:

Рассмотрим m+1 промежуточных распределений H _i : 0 ≤ i ≤ m , где первые i бит выбираются из равномерного распределения, а последние m − i бит выбираются из выходных данных G' _l . Таким образом, H ₀ — это полный выход G' _l , а H _m — истинно равномерное распределение U _m . Следовательно, распределения Hi _i и Hi ₊₁ будут отличаться только одним битом (номер бита + 1).

Теперь предположим, что G'l _{не является} псевдослучайным распределением; существует некоторая схема C , которая может различать G'l _и т. е . Um ₎ с преимуществом ε = 1/ poly ( l . Другими словами, эта схема может различать H ₀ и H _m . Следовательно, существует такой i , что схема C может различать Hi _по и Hi ₊₁ крайней мере на ε/m . Обратите внимание: поскольку m полиномиальны по l , то ε/m также является полиномиальным по l и по-прежнему является немаловажным преимуществом.

Теперь предположим, что нам даны l+1 бит, которые либо являются выходными данными G _l , либо взяты из равномерного распределения. Давайте повторно воспользуемся подходом построения больших псевдослучайных генераторов из экземпляров G _l и создадим строку псевдослучайных битов длины m-i-1 таким же образом, как G' _l был построен выше, используя первые l заданных битов в качестве начального числа. Затем давайте создадим строку, состоящую из i бит, взятых из униформы, объединенных с последним из заданных битов, за которыми следуют созданные m-i-1 бит. В результате получается либо H _i, либо H _i+1 , поскольку бит i+1 извлекается либо из Uniform, либо из G _l . Поскольку по предположению мы можем различать H _i и Hi ₊₁ с немалой выгодой, то мы можем различать U и G _l , что означает, что G _l не является псевдослучайным генератором, что противоречит гипотезе. КЭД

Теперь давайте проиллюстрируем, что если схема различения G _l и U _l+1 существует, то ей не нужно подбрасывать случайные монеты. Как мы показали выше, если существует схема C для различения G' _l и U _m , где m = поли ( l ), то существует схема C' для различения G _l и U _l+1 , использующая i случайных битов. Для этой схемы C' : | Вероятность _{u, s} [ C' ( ты ₁ ,...,u _i ,G _l ( s )) знак равно 1 ] - Вероятность _{u, y} [ C' ( ты ₁ ,>,...,u _i ,y ) = 1] | ≥ ε / м ,

где u — строка из i равномерно случайных битов, s — строка из l равномерно случайных битов, а y — строка из l +1 равномерно случайных битов.

Затем,

Prob _u[ | Prob _s [ C' ( u ₁,...,u _i,G _l( s )) = 1] - Prob _y [ C' ( u ₁,...,u _i,y ) = 1] | ] ≥ ε / m ;

Это означает, что существует некоторая фиксированная строка u из i бит, которую можно использовать в качестве «совета» схеме C' для различения G _l и U _l+1 .

Существование псевдослучайных генераторов

Существование псевдослучайных генераторов связано с существованием односторонних функций и жестких предикатов . Формально, генераторы псевдослучайных чисел существуют тогда и только тогда, когда существуют односторонние функции или

ПРГ ↔ ОВФ

Определения

Односторонние функции

Интуитивно односторонние функции — это функции, которые легко вычислить, но трудно обратить. Другими словами, сложность (или размер схемы) функции намного меньше, чем сложность ее обратной. Формально: Функция ƒ: {0,1} ^н → {0,1} ^н является ( S , ε ) односторонним , если для любой схемы C размера ≤ S ,

Prob[ƒ( C (ƒ( x ƒ( x )] ≤ ε ))) =

Более того, ƒ является односторонней функцией, если

ƒ можно вычислить за полиномиальное время
ƒ — ( поли ( n ), 1/ поли ( n )) односторонний

Жесткий предикат

Функция Б : {0,1} ^н → {0,1} является жестким предикатом для функции ƒ, если

B можно вычислить за полиномиальное время
для любой схемы C полиномиального размера и любого непренебрежимо малого ε = 1/ poly ( n ), Prob _x~U [ C (ƒ( x )) = B ( x )] ≤ 1/2+ ε

Другими словами, трудно предсказать B ( x ) по функции ƒ ( x ).

Доказательство

Здесь дается схема доказательства. Пожалуйста, смотрите ссылки для подробных доказательств.

ПРГ → ОВФ

Рассмотрим псевдослучайный генератор G _l : {0,1} ^л → {0,1} ^2л. Давайте создадим следующую одностороннюю функцию ƒ: {0,1} ^н → {0,1} ^н который использует первую половину вывода G _l в качестве своего вывода. Формально,

ƒ( Икс , y ) → G _л ( Икс )

Ключевое наблюдение, оправдывающее такой выбор, заключается в том, что размер вселенной прообраза равен 2 ^н и является пренебрежимо малой частью образа функции размера 2 ^2н.

Чтобы доказать, что ƒ действительно является односторонней функцией, построим аргумент от противного. Предположим, что существует схема C , которая инвертирует ƒ с преимуществом ε :

Prob[ƒ( C (ƒ( x , y ))) = ƒ( x , y )] > ε

Тогда мы сможем создать следующий алгоритм, который отличит G _l от равномерного, что противоречит гипотезе. Алгоритм возьмет на вход 2n бит z и вычислит ( x , y ) = C ( z ). Если G _l ( x ) = z , алгоритм примет, в противном случае — отклонит.

Теперь, если z получено из равномерного распределения, вероятность того, что приведенный выше алгоритм примет, составляет ≤ 1/2. ^л, поскольку размер прообраза равен 1/2 ^л размера изображения. Однако, если z был взят из выхода G _l , то вероятность принятия > ε в силу предположения о существовании схемы C . Следовательно, преимущество схемы C в различении однородного U и выхода G _l составляет > ε − 1/2. ^л, что немаловажно и, таким образом, противоречит нашему предположению о том, что G _l является псевдослучайным генератором. КЭД

ОВФ → ПРГ

Для этого случая мы докажем более слабую версию теоремы:

Односторонняя перестановка → генератор псевдослучайных чисел

Односторонняя перестановка — это односторонняя функция, которая также является перестановкой входных битов. Генератор псевдослучайных чисел можно построить из односторонней перестановки ƒ следующим образом:

Г _л : {0,1} ^л→{0,1} ^{л +1} = ƒ( х ). B ( x ), где B — это предикат ƒ и "." является оператором конкатенации. Заметим, что по доказанной выше теореме достаточно показать существование генератора, добавляющего всего один псевдослучайный бит.

Жесткий предикат → PRG

Во-первых, давайте покажем, что если B является жестким предикатом для ƒ, то G _l действительно псевдослучайный. Опять же, мы будем использовать аргумент от противного.

Предположим, что G _l не является генератором псевдослучайных чисел; то есть существует схема C полиномиального размера, которая отличает G _l ( x ) =ƒ ( x ). B ( x ) из U _l+1 с преимуществом ≥ ε , где ε немаловажно. Обратите внимание: поскольку ƒ( x ) является перестановкой, то если x взят из равномерного распределения, то так же и если ƒ( x ). Следовательно, U _l+1 эквивалентно ƒ( x ). b , где b немного нарисовано независимо от равномерного распределения. Формально,

Вероятность _x~U [ C ( G ( x ))=1] − Вероятность _x~U,b~U [ C ( xb )=1] ≥ ε

Построим следующий алгоритм C' :

1. Given z=f(x) guess bit b 
2. Run C on z.b
3. IF C(z.b)=1
4.     output b
5. ELSE
6.     output 1-b

Учитывая выходной сигнал ƒ, алгоритм сначала угадывает бит b, подбрасывая случайную монету, т. е. Prob[ b =0] = Prob[ b =1] = 0,5. Затем алгоритм (схема) C запускается на f(x).b , и если результат равен 1, b выводится обратное значение b , в противном случае возвращается .

Тогда вероятность того, что C' правильно угадает B ( x ), равна:

Вероятность _x~U [ C' ( z ) = B ( x )] =

Вероятность[ b знак равно B ( x ) ∧ C ( zb )=1] + Вероятность [ б ≠ B ( x ) ∧ C ( zb )=0] =

Вероятность[ б знак равно B ( x )]⋅Вероятность[ C ( zb )=1 | б = B ( x )] + Вероятность [ б ≠ B ( x )]⋅ Вероятность [ C ( zb )=0 | б ≠ B ( Икс )] знак равно

1/2⋅Prob[ C ( zb )=1 | б = B ( x )] + 1/2⋅Prob[ C ( zb )=0 | б ≠ B ( Икс )] знак равно

(1−1/2)⋅Prob[ C ( zb )=1 | б = B ( x )] + 1/2⋅(1−Prob[ C ( zb )=1 | b ≠ B ( x )]) =

1/2+Вероятность _z.b~G(x) [ C ( zb )=1] - 1/2⋅(Вероятность[ C ( zb )=1 | b = B ( x )]+Вероятность [ C ( zb )=1 | b ≠ B ( x )]) =

1/2+Вероятность _z.b~G(x) [ C ( zb )=1] - Вероятность _z.b~U [ C ( zb )=1] ≥ 1/2+ ε

Это означает, что схема C' может предсказать B ( x ) с вероятностью более 1/2 + ε , а это означает, что B не может быть жестким предикатом для ƒ, и гипотеза противоречит. КЭД

OWP → жесткое предикат

Схема доказательства такова:

Если ƒ{0,1} ^н→{0,1} ^н является односторонней перестановкой, то и ƒ'{0,1} ^2н→{0,1} ^2н, где ƒ'( x , y )=ƒ( x ). й по определению. Тогда B ( x , y )= x ⋅ y является жестким предикатом для ƒ', где ⋅ векторов является скалярным произведением . Чтобы доказать, что это действительно жесткое ядро, давайте предположим обратное и покажем противоречие с гипотезой об однонаправленности ƒ. Если B не является жестким предикатом, то существует схема C , которая предсказывает его, поэтому

Вероятность _x,y [ C (ƒ( x ), y )= x ⋅ y ] ≥ 1/2+ ε . Этот факт можно использовать для восстановления x , умело создавая перестановки y , которые изолируют биты в x . Фактически, для постоянной доли x существует алгоритм с полиномиальным временем, который перечисляет O (1/ ε ²) кандидаты, которые включают все действительные x . Таким образом, алгоритм может инвертировать ƒ( x ) за полиномиальное время для немалой доли x , что противоречит гипотезе.

Ссылки

В. Диффи, М. Е. Хеллман. «Новые направления в криптографии». Транзакции IEEE по теории информации , IT-22, стр. 644–654, 1976.
АС Яо. «Теория и применение функций-лазеек». 23-й симпозиум IEEE по основам информатики , стр. 80–91, 1982 г.
М. Блюм и С. Микали «Как генерировать криптографически стойкие последовательности псевдослучайных битов». SIAM Journal on Computing , т. 13, стр. 850–864, 1984.
Дж. Хастад, Р. Импальяццо, Л. А. Левин и М. Луби. «Псевдослучайный генератор любой односторонней функции». SIAM Journal on Computing , v28 n4, стр.-1364-1396, 1999.