Введение

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

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

Определение

Пусть будет класс функций. Эти функции — это статистические тесты, которые псевдослучайный генератор будет пытаться обмануть, и обычно это алгоритмы. Иногда статистические тесты также называют противниками или разделителями. Обозначение в кодомене функций — это звезда Клине. Функция с является псевдослучайным генератором против с отклонением, если для каждого в , статистическое расстояние между распределениями и не превышает , где — равномерное распределение на .

Величина называется длиной зерна, а величина — растяжением псевдослучайного генератора. Псевдослучайный генератор против семейства противников с отклонением — это семейство псевдослучайных генераторов , где — псевдослучайный генератор против с отклонением и длиной зерна .

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

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

В криптографии класс обычно состоит из всех схем, размер которых полиномиален относительно размера входа и имеющих один битный выход. Интерес представляет разработка псевдослучайных генераторов, которые могут быть вычислены алгоритмом за полиномиальное время и чей сдвиг (bias) пренебрежимо мал относительно размера схемы. Эти псевдослучайные генераторы иногда называют криптографически стойкими псевдослучайными генераторами (CSPRGs). Неизвестно, существуют ли криптографически стойкие псевдослучайные генераторы. Доказать их существование сложно, поскольку это подразумевает P ≠ NP, что является общепринятым, но знаменитым нерешенным вопросом. Широко распространено мнение о существовании криптографически стойких псевдослучайных генераторов. Это связано с тем, что было доказано, что псевдослучайные генераторы могут быть построены на основе любой односторонней функции, существование которых предполагается. Псевдослучайные генераторы необходимы для многих приложений в криптографии. Теорема о псевдослучайных генераторах утверждает, что криптографически стойкие псевдослучайные генераторы существуют тогда и только тогда, когда существуют односторонние функции.

Применение

Псевдослучайные генераторы имеют многочисленные применения в криптографии. Например, псевдослучайные генераторы предоставляют эффективный аналог одноразовых шифров. Хорошо известно, что для шифрования сообщения m таким образом, чтобы шифротекст не содержал никакой информации об исходном тексте, используемый ключ k должен быть случайным по строкам длиной |m|. Абсолютно безопасное шифрование очень затратно с точки зрения длины ключа. Длину ключа можно значительно сократить, используя псевдослучайный генератор, если абсолютная безопасность заменяется семантической безопасностью. Распространенные конструкции поточных шифров основаны на псевдослучайных генераторах. Псевдослучайные генераторы также могут использоваться для построения симметричных криптосистем, где большое количество сообщений может быть безопасно зашифровано под одним и тем же ключом. Такая конструкция может быть основана на семействе псевдослучайных функций, которое обобщает понятие псевдослучайного генератора. В 1980-х годах в физических симуляциях начали использовать псевдослучайные генераторы для получения последовательностей, содержащих миллиарды элементов, а к концу 1980-х годов появились данные о том, что некоторые распространенные генераторы давали неверные результаты в таких случаях, как свойства фазового перехода 3D модели Изинга и формы диффузионно-ограниченных агрегатов. Затем, в 1990-х годах, различные идеализации физических симуляций – основанные на случайных блужданиях, корреляционных функциях, локализации собственных состояний и т.п. – использовались в качестве тестов для псевдослучайных генераторов.

Испытания

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

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

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

Для многочленного времени

Основной вопрос в теории вычислительной сложности состоит в том, можно ли все полиномиальные рандомизированные алгоритмы для задач принятия решений детерминированно смоделировать за полиномиальное время. Существование такой симуляции означало бы, что BPP = P. Для выполнения такой симуляции достаточно построить генераторы псевдослучайных чисел, устойчивые к семейству F всех схем размера s(n), принимающих на вход данные длины n и выдающих один бит, где s(n) – произвольный полином, длина начального зерна генератора псевдослучайных чисел составляет O(log n), а его смещение равно ⅓. В 1991 году Ноам Нисан и Ави Вигдерсон предложили кандидат на роль такого генератора псевдослучайных чисел с указанными свойствами. В 1997 году Рассел Импаглиаццо и Ави Вигдерсон доказали, что конструкция Нисана и Вигдерсона является генератором псевдослучайных чисел при условии существования задачи принятия решений, которую можно вычислить за время 2O(n) на входах длины n, но для которой требуются схемы размера 2Ω(n).

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

Хотя для доказательства работоспособности генератора Нисана-Вигдерсона для машин с ограниченным временем требуются недоказанные предположения о сложности схем, естественно сузить класс статистических тестов, чтобы не зависеть от этих недоказанных предположений. Один из таких классов – это класс машин, объем рабочей памяти которых ограничен. Используя прием повторного возведения в квадрат, известный как теорема Савича, легко показать, что любое вероятностное вычисление с логарифмической памятью может быть смоделировано в памяти. Ноам Нисан (1992) показал, что эту дерандомизацию можно осуществить с помощью псевдослучайного генератора с длиной зерна, который обманывает все машины, использующие память. Генератор Нисана был использован Саксом и Чжоу (1999) для доказательства того, что вероятностные вычисления с логарифмической памятью могут быть детерминированно смоделированы в памяти. Уильям Хоза в 2021 году улучшил этот результат до памяти.

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

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

Для многочленов

Доказывает, что взятие суммы небольших генераторов смещения обманывает полиномы степени d. Длина зерна составляет l.

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

Константные схемы фиксированной глубины, выдающие один выходной бит.

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

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