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

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

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

Определение

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

Функция $G:\{0,1\}^{\ell }\to \{0,1\}^{n}$ с $\ell <n$ это псевдослучайный генератор против ${\mathcal {A}}$ с предвзятостью $\varepsilon$ если для каждого $A$ в ${\mathcal {A}}$ , статистическое расстояние между распределениями $A(G(U_{\ell }))$ и $A(U_{n})$ самое большее $\varepsilon$ , где $U_{k}$ — равномерное распределение по $\{0,1\}^{k}$ .

Количество $\ell$ называется длиной семени и количеством $n-\ell$ называется растяжением генератора псевдослучайных чисел.

Генератор псевдослучайных чисел против семейства противников $({\mathcal {A}}_{n})_{n\in \mathbb {N} }$ с предвзятостью $\varepsilon (n)$ это семейство псевдослучайных генераторов $(G_{n})_{n\in \mathbb {N} }$ , где $G_{n}:\{0,1\}^{\ell (n)}\to \{0,1\}^{n}$ это псевдослучайный генератор против ${\mathcal {A}}_{n}$ с предвзятостью $\varepsilon (n)$ и длина семени $\ell (n)$ .

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

В криптографии

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

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

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

Использование

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

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

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

Тестирование

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

Для дерандомизации

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

Конструкции

За полиномиальное время

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

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

Для логарифмического пространства

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

Для линейных функций

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

Для полиномов

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

Для контуров постоянной глубины

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

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

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

Ссылки

^ Кац, Джонатан (6 ноября 2014 г.). Введение в современную криптографию . Линделл, Иегуда (второе изд.). Бока Ратон. ISBN 9781466570269 . OCLC 893721520 . {{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка )
^ Хостад, Йохан; Импальяццо, Рассел; Левин Леонид А.; Луби, Майкл (1 января 1999 г.). «Псевдослучайный генератор любой односторонней функции» . SIAM Journal по вычислительной технике . 28 (4): 1364–1396. дои : 10.1137/S0097539793244708 .
^ Кац, Джонатан; Линделл, Иегуда (20 декабря 2020 г.). Введение в современную криптографию . ЦРК Пресс. п. 262. ИСБН 978-1-351-13302-9 .
^ Вольфрам, Стивен (2002). Новый вид науки . Wolfram Media, Inc. с. 1085 . ISBN 978-1-57955-008-0 .
^ «Методы статистического тестирования для генерации псевдослучайных чисел» .
^ Разборов, Александр; Рудич, Стивен (август 1997 г.). «Естественные доказательства» . Журнал компьютерных и системных наук . 55 (1): 24–35. дои : 10.1006/jcss.1997.1494 .

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

[1] Кац, Джонатан (6 ноября 2014 г.). Введение в современную криптографию . Линделл, Иегуда (второе изд.). Бока Ратон. ISBN 9781466570269 . OCLC 893721520 . {{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка )

[2] Хостад, Йохан; Импальяццо, Рассел; Левин Леонид А.; Луби, Майкл (1 января 1999 г.). «Псевдослучайный генератор любой односторонней функции» . SIAM Journal по вычислительной технике . 28 (4): 1364–1396. дои : 10.1137/S0097539793244708 .

[3] Кац, Джонатан; Линделл, Иегуда (20 декабря 2020 г.). Введение в современную криптографию . ЦРК Пресс. п. 262. ИСБН 978-1-351-13302-9 .

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

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

[6] Разборов, Александр; Рудич, Стивен (август 1997 г.). «Естественные доказательства» . Журнал компьютерных и системных наук . 55 (1): 24–35. дои : 10.1006/jcss.1997.1494 .

[1]

[2]

[3]

[4]

[5]

[6]