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

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

Введение

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

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

| ВероятностьИкс∈U [C(Икс) = 1] - ВероятноИкс∈D [C(Икс)=1] | ≤ ε.

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

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

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

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

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

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

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

Рассматривать м + 1 промежуточные распределения ЧАСя: 0 ≤ я ≤ м, где сначала я биты выбираются из равномерного распределения, и последние м - я биты выбираются из вывода Г'л. Таким образом, ЧАС0 это полный результат Г'л и ЧАСм истинное равномерное распределение Uм. Следовательно, раздачи ЧАСя и ЧАСя + 1 будет отличаться только одним битом (бит номер я+1).

Теперь предположим, что Г'л не является псевдослучайным распределением; то есть существует некоторая схема C который может различать Г'л и Uм с преимуществом ε  =   1/поли(л). Другими словами, эта схема может различать ЧАС0 и ЧАСм. Следовательно, существует такой я что схема C может различать ЧАСя и ЧАСя + 1 по крайней мере ε / м. Обратите внимание, что поскольку м полиномиальны от л, тогда ε / м также полиномиален от л и это по-прежнему значимое преимущество.

Теперь предположим, что нам даны л + 1 биты, которые либо выводятся гл или полученный из равномерного распределения. Давайте повторно воспользуемся подходом построения больших псевдослучайных генераторов из экземпляров гл и построить строку псевдослучайных битов длины м-я-1 таким же образом Г'л был построен выше с использованием первого л даны биты как семя. Затем давайте создадим строку, состоящую из я биты, взятые из униформы, сцепленные с последним из заданных битов, за которыми следует созданный м-я-1 биты. В результате получается либо ЧАСя или ЧАСя + 1, поскольку я + 1 бит либо взят из мундира, либо из гл. Поскольку по предположению мы можем различать ЧАСя и ЧАСя + 1 с участием неотъемлемый преимущество, то мы можем различать U и гл, откуда следует, что гл не является псевдослучайным генератором, что противоречит гипотезе. Q.E.D.

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

где ты это строка я равномерно случайные биты, s это строка л равномерно случайные биты и y это строка л+1 равномерно случайный бит.

Потом,

Вероятноты[| Вероятноs [C ' (ты1, ..., тыя,Гл(s)) = 1] - Вероятноy [C ' (ты1, ..., тыя, y) = 1] | ] ≥ ε / м;

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

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

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

PRG ↔ OWF

Определения

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

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

Вероятность [ƒ (C(ƒ (Икс))) = ƒ (Икс)] ≤ ε.

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

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

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

Функция B: {0,1}п → {0,1} - это жесткий предикат для функции, если

  • B можно вычислить за полиномиальное время
  • для схемы любого размера полинома C и любые существенные ε = 1/поли(п), Вероятностьх ~ U[C(ƒ (Икс))  = B(Икс)] ≤ 1/2+ε

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

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

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

PRG → OWF

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

ƒ (Икс,y) → гл(Икс)

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

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

Вероятность [ƒ (C(ƒ (Икс,y))) = ƒ (Икс,y)] > ε

Затем мы можем создать следующий алгоритм, который будет различать гл от униформы, что противоречит гипотезе. В алгоритм будет входить 2n биты z и вычислить (Икс,y) = C(z). Если гл(Икс) = z алгоритм примет, иначе он отклонит.

Сейчас если z берется из равномерного распределения, вероятность, что алгоритм выше принимает ≤ 1/2л, поскольку размер изображения 1/2л размера прообраза. Однако если z был взят из вывода гл тогда вероятность принятия> ε по предположению о существовании цепи C. Следовательно, преимущество в том, что схема C имеет различие между униформой U и выход гл это> ε − 1/2л, которым нельзя пренебречь, что противоречит нашему предположению о гл являясь генератором псевдослучайных случаев. Q.E.D.

OWF → PRG

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

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

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

гл: {0,1}л→{0,1}л+1 = ƒ (Икс).B(Икс), где B является предикатом ƒ и "." является оператором конкатенации. Заметим, что по доказанной теореме нужно только показать существование генератора, который добавляет всего один псевдослучайный бит.

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

Сначала покажем, что если B является жестким предикатом для ƒ, то гл действительно псевдослучайно. Мы снова воспользуемся аргументом от противного.

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

Вероятнох ~ U [C(г(Икс)) = 1] - Вероятнох ~ U, Ь ~ U [C(x.b)=1]  ≥ ε

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

1. Для z = f (x) предположить бит b 2. Выполнить C на z.b3. ЕСЛИ C (z.b) = 14. вывод b5. ELSE6. выход 1-б

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

Тогда вероятность C ' угадывать B(Икс) правильно:

Вероятнох ~ U [C '(z)=B(Икс)] =

Prob [б=B(Икс) ∧ C(z.b) = 1] + вероятность [б≠B(Икс) ∧ C(z.b)=0] =

Prob [б=B(Икс)] ⋅ Вероятность [C(z.b)=1 | б=B(Икс)] + Вероятность [б≠B(Икс)] ⋅ Вероятность [C(z.b)=0 | б≠B(Икс)] =

1 / 2⋅Вероятность [C(z.b)=1 | б=B(Икс)] + 1 / 2⋅ Вероятность [C(z.b)=0 | б≠B(Икс)] =

(1−1 / 2) ⋅Вероятно [C(z.b)=1 | б=B(Икс)] + 1 / 2⋅ (1 − Prob [C(z.b)=1 | б≠B(Икс)]) =

1/2 + Вероятностьz.b ~ G (x) [C(z.b) = 1] −1 / 2⋅ (Вероятность [C(z.b)=1 | б=B(Икс)] + Вероятность [C(z.b)=1 | б≠B(Икс)]) =

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

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

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

Схема доказательства следующая:

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

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

использованная литература

  • W. Diffie, M.E. Hellman. «Новые направления в криптографии». IEEE Transactions по теории информации, ИТ-22, с. 644–654, 1976.
  • A.C. Yao. «Теория и применение секретных функций». 23-й симпозиум IEEE по основам компьютерных наук, 1982, с. 80–91.
  • М. Блюм и С. Микали «Как сгенерировать криптографически стойкие последовательности псевдослучайных битов». SIAM Журнал по вычислениям, v13, pp. 850–864, 1984.
  • Дж. Хастад, Р. Импальяццо, Л. А. Левин и М. Луби. «Генератор псевдослучайных ситуаций из любой односторонней функции». SIAM Журнал по вычислениям, v28 n4, pp.-1364-1396, 1999.