В теории сложности вычислений и криптографии существование псевдослучайных генераторов связано с существованием односторонних функций посредством ряда теорем, которые в совокупности называются теоремой о псевдослучайных генераторах .
Вступление
Псевдослучайность
Распределение считаются псевдослучайным , если нет эффективного вычисления не может отличить его от истинного равномерного распределения по не- незначительного преимущества . Формально семейство распределений D n является псевдослучайным, если для любой схемы C полиномиального размера и любого ε обратно полиномиально от n
- | Вероятность x ∈ U [ C ( x ) = 1] - Вероятность x ∈ D [ C ( x ) = 1] | ≤ ε .
Псевдослучайные генераторы
Функция G l : {0,1} l → {0,1} m , где l < m - псевдослучайный генератор, если:
- G l можно вычислить за время, полиномиальное от l
- G l ( x ) является псевдослучайным, когда x равномерно случайный.
Один дополнительный псевдослучайный бит подразумевает полиномиально больше псевдослучайных битов.
Можно показать, что если существует псевдослучайный генератор G l : {0,1} l → {0,1} l +1 , т.е. генератор, который добавляет только один псевдослучайный бит, то для любого m = poly ( l ) существует псевдослучайный генератор G ' l : {0,1} l → {0,1} m .
Идея доказательства заключается в следующем: первые 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 0 - это полный выход G ' l, а H m - истинное равномерное распределение U m . Следовательно, распределения H i и H i + 1 будут отличаться только одним битом (номер бита i +1).
Теперь предположим, что G ' l не является псевдослучайным распределением; то есть существует некая схема C, которая может различать G ' l и U m с преимуществом ε = 1 / poly ( l ). Другими словами, эта схема может различать H 0 и H m . Следовательно, существует такое i, что схема C может различать H i и H i + 1 не менее чем на ε / m . Обратите внимание: поскольку m полиномиальны от l , то ε / m также полиномиально от l и по-прежнему является значительным преимуществом.
Теперь предположим, что нам даны l + 1 бит, которые либо выводятся G l, либо взяты из равномерного распределения. Давайте повторно воспользуемся подходом построения больших псевдослучайных генераторов из экземпляров G l и построим строку псевдослучайных битов длины m − i − 1 таким же образом, как G ' l был построен выше, используя первые l заданных битов в качестве начального числа. Затем давайте создадим строку, состоящую из i битов, взятых из uniform, сцепленных с последним из заданных битов, за которыми следуют созданные m-i-1 биты. В результате получается либо H i, либо H i + 1 , поскольку бит i + 1 либо взят из uniform, либо из G l . Поскольку по предположению мы можем различать H i и H i + 1 с заметным преимуществом, то мы можем различать U и G l , что означает, что G l не является псевдослучайным генератором, что противоречит гипотезе. QED
Теперь давайте проиллюстрируем, что, если существует, схема для различения G l и U l + 1 не должна подбрасывать случайные монеты. Как мы показали выше, если существует схема C для различения G ' l и U m , где m = poly ( l ), то существует схема C' для различения G l и U l + 1, которая использует i случайных битов. Для этой схемы C ' : | Вероятность u, s [ C ' ( u 1 , ..., u i , G l ( s )) = 1] - Вероятность u, y [ C' ( u 1 ,>, ..., u i , y ) = 1] | ≥ ε / м ,
где u - строка из i равномерно случайных битов, s - строка из l равномерно случайных битов, а y - строка из l +1 равномерно случайных битов.
Потом,
Prob u [| Вероятность s [ C ' ( u 1 , ..., u i , G l ( s )) = 1] - Вероятность y [ C' ( u 1 , ..., u i , y ) = 1] | ] ≥ ε / м ;
Это означает, что существует некоторая фиксированная строка u из i битов, которую можно использовать в качестве «совета» для схемы C ' для различения G l и U l + 1 .
Существование псевдослучайных генераторов
Существование псевдослучайных генераторов связано с существованием односторонних функций и жестких предикатов . Формально псевдослучайные генераторы существуют тогда и только тогда, когда существуют односторонние функции, или
PRG ↔ OWF
Определения
Односторонние функции
Интуитивно понятные односторонние функции - это функции, которые легко вычислить и которые сложно инвертировать. Другими словами, сложность (или размер схемы) функции намного меньше, чем у ее обратной. Формально: Функция ƒ: {0,1} п → {0,1} п представляет собой ( S , ε ) в одну сторону , если для любой схемы C размером ≤ S ,
Вероятность [ƒ ( C (ƒ ( x ))) = ƒ ( x )] ≤ ε .
Более того, ƒ - односторонняя функция, если
- ƒ можно вычислить за полиномиальное время
- ƒ является ( poly ( n ), 1 / poly ( n )) односторонним
Жесткий предикат
Функция B : {0,1} n → {0,1} является жестким предикатом для функции ƒ, если
- B можно вычислить за полиномиальное время
- для любой схемы C полиномиального размера и любого значимого ε = 1 / poly ( n ), Prob x ~ U [ C (ƒ ( x )) = B ( x )] ≤ 1/2 + ε
Другими словами, трудно предсказать B ( x ) по функции ƒ ( x ).
Доказательство
Здесь дается схема доказательства. Пожалуйста, смотрите ссылки для подробных доказательств.
PRG → OWF
Рассмотрим псевдослучайный генератор G l : {0,1} l → {0,1} 2l . Давайте создадим следующую одностороннюю функцию ƒ: {0,1} n → {0,1} n, которая использует первую половину вывода G l в качестве вывода. Формально,
ƒ ( х , у ) → G l ( х )
Ключевое наблюдение, которое оправдывает такой выбор, состоит в том, что изображение функции имеет размер 2 n и составляет незначительную часть вселенной предварительного изображения размером 2 2 n .
Чтобы доказать, что ƒ действительно односторонняя функция, давайте построим аргумент от противного. Предположим, что существует схема C, которая инвертирует ƒ с преимуществом ε :
Вероятно [ƒ ( C (ƒ ( x , y ))) = ƒ ( x , y )]> ε
Тогда мы можем создать следующий алгоритм, который будет отличать G l от равномерного, что противоречит гипотезе. Алгоритм примет на вход 2n бит z и вычислит ( x , y ) = C ( z ). Если G l ( x ) = z, алгоритм примет, в противном случае он отклонит.
Теперь, если z извлекается из равномерного распределения, вероятность, которую принимает вышеупомянутый алгоритм, составляет ≤ 1/2 l , поскольку размер изображения составляет 1/2 l размера предварительного изображения. Однако, если г был составлен из выходного сигнала G л , то вероятность принятия является> ε по предположению о существовании цепи C . Следовательно, преимущество схемы C в различении однородного U и выходного сигнала G l составляет> ε - 1/2 l , что не является незначительным и, таким образом, противоречит нашему предположению о том, что G l является псевдослучайным генератором. QED
OWF → PRG
В этом случае мы докажем более слабую версию теоремы:
Односторонняя перестановка → псевдослучайный генератор
Односторонняя перестановка - это односторонняя функция, которая также является перестановкой входных битов. Псевдослучайный генератор может быть построен из односторонней перестановки ƒ следующим образом:
G l : {0,1} l → {0,1} l +1 = ƒ ( x ). B ( x ), где B - жесткий предикат of и "." является оператором конкатенации. Обратите внимание, что по доказанной выше теореме нужно только показать существование генератора, который добавляет всего один псевдослучайный бит.
Жесткий предикат → 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. Для z = f (x) предположить бит b 2. Запустите C на zb3. ЕСЛИ C (zb) = 14. выход b5. ИНАЧЕ6. вывод 1-б
Учитывая результат, алгоритм сначала угадывает бит 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 ≠ B ( x ) ∧ C ( zb ) = 0] =
Вероятность [ b = B ( x )] ⋅ Вероятность [ C ( zb ) = 1 | b = B ( x )] + Вероятность [ b ≠ B ( x )] ⋅ Вероятность [ C ( zb ) = 0 | b ≠ B ( x )] =
1 / 2⋅ Вероятность [ C ( zb ) = 1 | b = B ( x )] + 1 / 2⋅ Вероятность [ C ( zb ) = 0 | b ≠ B ( x )] =
(1−1 / 2) ⋅ Вероятность [ C ( zb ) = 1 | b = 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 не может быть жестким предикатом для ƒ, и гипотеза противоречит. QED
OWP → жесткий предикат
Схема доказательства такова:
Если ƒ {0,1} n → {0,1} n - односторонняя перестановка, то также и ƒ '{0,1} 2n → {0,1} 2n , где ƒ' ( x , y ) = ƒ ( х ). y по определению. Тогда B ( x , y ) = x ⋅ y - жесткий предикат для ƒ ', где ⋅ - векторное скалярное произведение . Чтобы доказать, что это действительно хардкор, давайте предположим иное и покажем противоречие с гипотезой об односторонности ƒ. Если B не является жестким предикатом, то существует схема C, которая его предсказывает, поэтому
Вероятно, x, y [ C (ƒ ( x ), y ) = x ⋅ y ] ≥ 1/2 + ε . Этот факт можно использовать для восстановления x , умело построив перестановки y, которые изолируют биты в x . Фактически, для постоянной доли x существует алгоритм полиномиального времени, который перечисляет O (1 / & epsilon 2 ) кандидатов, которые включают все действительные x . Таким образом, алгоритм может инвертировать ƒ ( x ) за полиномиальное время для неотъемлемой части x , что противоречит гипотезе.
Рекомендации
- W. Diffie, ME Hellman. «Новые направления в криптографии». IEEE Transactions по теории информации , IT-22, стр. 644–654, 1976.
- AC Yao. «Теория и применение секретных функций». 23-й симпозиум IEEE по основам информатики , стр. 80–91, 1982.
- М. Блюм и С. Микали "Как сгенерировать криптографически стойкие последовательности псевдослучайных битов". SIAM Journal on Computing , v13, pp. 850–864, 1984.
- Дж. Хастад, Р. Импальяццо, Л. А. Левин и М. Луби. «Генератор псевдослучайных ситуаций из любой односторонней функции». SIAM Journal on Computing , v28 n4, pp.-1364-1396, 1999.