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

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

В литературе было рассмотрено множество различных классов статистических тестов, в том числе класс всех булевых схем заданного размера. Неизвестно, существуют ли хорошие псевдослучайные генераторы для этого класса, но известно, что их существование в определенном смысле эквивалентно (недоказанным) нижним оценкам схемы в теории вычислительной сложности . Следовательно, построение псевдослучайных генераторов для класса булевых схем заданного размера опирается на недоказанные в настоящее время предположения о надежности.

Определение [ править ]

Позвольте быть классом функций. Эти функции представляют собой статистические тесты, которые генератор псевдослучайных ошибок пытается обмануть, и обычно это алгоритмы . Иногда статистические тесты также называют противниками или отличителями . ^[1] ${\ displaystyle {\ mathcal {A}} = \ {A: \ {0,1 \} ^ {n} \ to \ {0,1 \} ^ {*} \}}$

Функция с является псевдослучайным генератором против с уклоном , если для каждого дюйма , то статистическое расстояние между распределениями и самым большим , где это равномерное распределение на . ${\ Displaystyle G: \ {0,1 \} ^ {\ ell} \ к \ {0,1 \} ^ {n}}$ ${\ displaystyle \ ell \ leq n}$ ${\ displaystyle {\ mathcal {A}}}$ ${\ displaystyle \ epsilon}$ ${\ displaystyle A}$ ${\ displaystyle {\ mathcal {A}}}$ ${\ Displaystyle А (G (U _ {\ ell}))}$ ${\ displaystyle A (U_ {n})}$ ${\ displaystyle \ epsilon}$ ${\ displaystyle U_ {k}}$ ${\ Displaystyle \ {0,1 \} ^ {к}}$

Величина называется длиной начального числа, а величина - отрезком генератора псевдослучайных чисел. ${\ displaystyle \ ell}$ ${\ displaystyle n- \ ell}$

Псевдослучайный генератор против семейства противников со смещением - это семейство псевдослучайных генераторов , в котором псевдослучайный генератор против со смещением и длиной начального числа . ${\ displaystyle ({\ mathcal {A}} _ {n}) _ {n \ in \ mathbb {N}}}$ ${\ Displaystyle \ epsilon (п)}$ ${\ Displaystyle (G_ {п}) _ {п \ in \ mathbb {N}}}$ ${\ displaystyle G_ {n}: \ {0,1 \} ^ {\ ell (n)} \ к \ {0,1 \} ^ {n}}$ ${\ displaystyle {\ mathcal {A}} _ {n}}$ ${\ Displaystyle \ epsilon (п)}$ ${\ Displaystyle \ ell (п)}$

В большинстве приложений семейство представляет некоторую модель вычислений или некоторый набор алгоритмов , и каждый заинтересован в разработке псевдослучайного генератора с малой длиной начального числа и смещением, и таким образом, чтобы выходной сигнал генератора мог быть вычислен с помощью такого же алгоритма. . ${\ displaystyle {\ mathcal {A}}}$

В криптографии [ править ]

В криптографии класс обычно состоит из всех схем полиномиального размера на входе и с однобитовым выходом, и каждый заинтересован в разработке генераторов псевдослучайных ситуаций, которые вычисляются с помощью алгоритма с полиномиальным временем и чье смещение незначительно в размере схемы. Эти псевдослучайные генераторы иногда называют криптографически безопасными псевдослучайными генераторами (CSPRG) . ${\ displaystyle {\ mathcal {A}}}$

Неизвестно, существуют ли криптографически безопасные генераторы псевдослучайных сигналов. Доказать, что они существуют, сложно, поскольку из их существования следует, что P ≠ NP , что широко считается, но, как известно, является открытой проблемой. Существование криптографически безопасных генераторов псевдослучайных сигналов также широко распространено ^{[ цитата необходима ],} и они необходимы для многих приложений в криптографии .

Теорема о псевдослучайном генераторе показывает, что криптографически безопасные псевдослучайные генераторы существуют тогда и только тогда, когда существуют односторонние функции .

Использует [ редактировать ]

Генераторы псевдослучайных сигналов находят множество применений в криптографии. Например, генераторы псевдослучайных ситуаций являются эффективным аналогом одноразовых планшетов . Хорошо известно, что для того, чтобы зашифровать сообщение m таким образом, чтобы зашифрованный текст не содержал информации об открытом тексте, используемый ключ k должен быть случайным по строкам длиной | m |. Идеально безопасное шифрование очень дорого с точки зрения длины ключа. Длина ключа может быть значительно уменьшена с помощью генератора псевдослучайных ситуаций, если безупречная безопасность заменена семантической безопасностью . Распространенные конструкции потоковых шифров основаны на генераторах псевдослучайных случаев .

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

В 1980-х годах при моделировании в физике начали использовать псевдослучайные генераторы для создания последовательностей с миллиардами элементов, и к концу 1980-х годов появились доказательства того, что несколько распространенных генераторов давали неверные результаты в таких случаях, как свойства фазового перехода 3D- модели Изинга и формы агрегатов с ограниченной диффузией. Затем, в 1990-х годах, различные идеализации физических симуляций - на основе случайных блужданий , корреляционных функций , локализации собственных состояний и т. Д. - использовались в качестве тестов псевдослучайных генераторов. ^[2]

Тестирование [ править ]

NIST объявил о тестировании SP800-22 на случайность, чтобы проверить, производит ли псевдослучайный генератор случайные биты высокого качества. Юнгге Ван показал, что тестирования NIST недостаточно для обнаружения слабых генераторов псевдослучайных ситуаций, и разработал метод статистического тестирования на основе расстояния LILtest. ^[3]

Для дерандомизации [ править ]

Основное применение псевдослучайных генераторов заключается в дерандомизации вычислений, основанных на случайности, без искажения результата вычисления. Физические компьютеры - это детерминированные машины, и получение истинной случайности может быть проблемой. Генераторы псевдослучайных ситуаций могут использоваться для эффективного моделирования рандомизированных алгоритмов с использованием небольшой или нулевой случайности. В таких приложениях класс описывает рандомизированный алгоритм или класс рандомизированных алгоритмов, которые нужно моделировать, и цель состоит в том, чтобы разработать «эффективно вычислимый» псевдослучайный генератор против ${\ displaystyle {\ mathcal {A}}}$ ${\ displaystyle {\ mathcal {A}}}$ длина семян как можно короче. Если требуется полная дерандомизация, полностью детерминированное моделирование продолжается путем замены случайного входа в рандомизированный алгоритм псевдослучайной строкой, созданной псевдослучайным генератором. Моделирование делает это для всех возможных начальных чисел и соответствующим образом усредняет выходные данные различных прогонов рандомизированного алгоритма.

Конструкции [ править ]

Для полиномиального времени [ править ]

Фундаментальный вопрос в теории сложности вычислений состоит в том, можно ли детерминированно смоделировать все алгоритмы рандомизации с полиномиальным временем для решения задач за полиномиальное время. Существование такого моделирования будет означать , что BPP = P . Чтобы выполнить такое моделирование, достаточно построить псевдослучайные генераторы для семейства F всех схем размера s ( n ), входы которых имеют длину n и выводят один бит, где s ( n ) - произвольный многочлен, длина начального числа псевдослучайного генератора O (log n) и его смещение равно ⅓.

В 1991 году Ноам Нисан и Ави Вигдерсон предоставили кандидатный генератор псевдослучайных сигналов с этими свойствами. В 1997 году Рассел Импальяццо и Ави Вигдерсон доказали, что конструкция Нисана и Вигдерсона является псевдослучайным генератором, предполагающим, что существует проблема решения, которая может быть вычислена за время 2 ^{O ( n )} на входах длины n, но требует наличия схем размером 2 ^{Ом ( п )} .

Для логарифмического пробела [ править ]

Хотя для доказательства того, что генератор Нисана – Вигдерсона работает для машин с ограничением по времени, необходимы недоказанные предположения о сложности схемы, естественно ограничить класс статистических тестов так, чтобы нам не приходилось полагаться на такие недоказанные предположения. Один класс, для которого это было сделано, - это класс машин, рабочее пространство которых ограничено . Используя повторный трюк возведения в квадрат, известный как теорема Сэвича , легко показать, что каждое вероятностное вычисление в лог-пространстве можно смоделировать в пространстве . Ноам Нисан (1992) показал, что эта дерандомизация может быть достигнута с помощью псевдослучайного генератора длины начального числа, который обманывает всех. ${\ Displaystyle О (\ журнал п)}$ $O(\log ^{2}n)$ $O(\log ^{2}n)$ $O(\log n)$ -космические машины. Генератор Нисана был использован Саксом и Чжоу (1999), чтобы показать, что вероятностные вычисления в лог-пространстве могут детерминированно моделироваться в пространстве . Этот результат по-прежнему является наиболее известным результатом дерандомизации для машин с общим лог-пространством в 2012 году. $O(\log ^{1.5}n)$

Для линейных функций [ править ]

Когда статистические тесты состоят из всех многомерных линейных функций над некоторым конечным полем , говорят о генераторах с эпсилон-смещением . Конструкция Наора и Наора (1990) достигает длины семян , которая является оптимальной с точностью до постоянных факторов. Псевдослучайные генераторы для линейных функций часто служат строительным блоком для более сложных псевдослучайных генераторов. $\mathbb {F}$ $\ell =\log n+O(\log(\epsilon ^{-1}))$

Для полиномов [ править ]

Виола (2008) доказывает, что суммирование генераторов малого смещения обманывает многочлены степени . Длина семян составляет . $d$ $d$ $\ell =d\cdot \log n+O(2^{d}\cdot \log(\epsilon ^{-1}))$

Для схем постоянной глубины [ править ]

Цепи постоянной глубины, которые производят один выходной бит. ^{[ необходима цитата ]}

Ограничения вероятности [ править ]

Существование псевдослучайных генераторов, используемых в криптографии и универсальной алгоритмической дерандомизации, не доказано, хотя их существование широко распространено ^{[ цитата необходима ]} . Доказательства их существования предполагают доказательства нижних оценок схемной сложности некоторых явных функций. Такие нижние границы схемы не могут быть доказаны в рамках естественных доказательств, предполагающих существование более сильных вариантов криптографических генераторов псевдослучайных сигналов ^{[ ссылка ]} .

Ссылки [ править ]

^ Кац, Джонатан (2014-11-06). Введение в современную криптографию . Линделл, Иегуда (второе изд.). Бока-Ратон. ISBN 9781466570269. OCLC 893721520 . CS1 maint: discouraged parameter (link)
^ Вольфрам, Стивен (2002). Новый вид науки . Wolfram Media, Inc. стр. 1085 . ISBN 978-1-57955-008-0.
^ «Методы статистического тестирования псевдослучайной генерации» .

Санджив Арора и Боаз Барак, Вычислительная сложность: современный подход , Cambridge University Press (2009), ISBN 9780521424264 .
Одед Голдрайх , Вычислительная сложность: концептуальная перспектива , Cambridge University Press (2008), ISBN 978-0-521-88473-0 .
Одед Голдрайх , Основы криптографии: основные инструменты , Cambridge University Press (2001), ISBN 9780521791724 .
Наор, Иосиф; Наор, Мони (1990), «Пространства вероятностей с малым смещением: эффективные конструкции и приложения» , Труды 22-го ежегодного симпозиума ACM по теории вычислений, STOC 1990 : 213–223, CiteSeerX 10.1.1.421.2784 , doi : 10.1145 / 100216.100244 , ISBN 978-0897913614, S2CID 14031194
Виола, Эмануэле (2008), «Сумма d генераторов с малым смещением обманывает многочлены степени d» (PDF) , Труды 23-й ежегодной конференции по вычислительной сложности (CCC 2008) : 124–127, CiteSeerX 10.1.1.220.1554 , DOI : 10,1109 / CCC.2008.16 , ISBN 978-0-7695-3169-4
Эта статья включает материал из генератора псевдослучайных сообщений на PlanetMath , который находится под лицензией Creative Commons Attribution / Share-Alike License .

[1] Кац, Джонатан (2014-11-06). Введение в современную криптографию . Линделл, Иегуда (второе изд.). Бока-Ратон. ISBN 9781466570269. OCLC 893721520 . CS1 maint: discouraged parameter (link)

[2] Вольфрам, Стивен (2002). Новый вид науки . Wolfram Media, Inc. стр. 1085 . ISBN 978-1-57955-008-0.

[3] «Методы статистического тестирования псевдослучайной генерации» .

[1]