Список обозначений

Генератор псевдослучайный

pseudorandom generator
Синонимы: генератор псевдослучайных последовательностей

Говоря неформально, псевдослучайный генератор — это полиномиально вычислимая регулярная по длине функция $g\colon\{0,1\}^*\to\{0,1\}^*$, увеличивающая длину входа и создающая на выходе распределение вероятностей, вычислительно неотличимое от равномерного распределения на множестве всех двоичных строк соответствующей длины. Иногда псевдослучайным генератором называют алгоритм, который вычисляет такую функцию (см. [1]).

Применения псевдослучайных генераторов в математической криптографии многочисленны и разнообразны. В частности, псевдослучайный генератор используется в конструкции генератора псевдослучайных функций из [2], [3] (см. генератор псевдослучайных функций) и протокола привязки к биту из [4], [5] (см. условие абсолютной однозначности для протокола привязки к биту). Псевдослучайные генераторы позволяют уменьшить число случайных битов, необходимых для вероятностных алгоритмов.

Определение 1 псевдослучайный генератор
Функция $g\colon\{0,1\}^*\to\{0,1\}^*$, отображающая $\{0,1\}^n$ в $\{0,1\}^{m(n)}$ для всех $n\in\mathbb N$, называется псевдослучайным генератором, если
  1. $g$ полиномиально вычислима;
  2. функция $m$ удовлетворяет неравенству $m(n)>n$ для всех $n\in\mathbb N$.
  3. семейства случайных величин $(g(\widetilde u_n)\,|\, n\in\mathbb N)$ и $(\widetilde u_{m(n)}\,|\, n\in\mathbb N)$ вычислительно неотличимы;

Очевидно, что если не требовать выполнения условия 2 в этом определении, то понятие псевдослучайного генератора будет бессодержательным. Легко также видеть, что если функция $g$ отображает $\{0,1\}^n$ в $\{0,1\}^{m(n)}$ для всех $n\in\mathbb N$, причем выполнено условие 2 определения 1, то статистическое расстояние между случайными величинами $g(\widetilde u_n)$ и $\widetilde u_{m(n)}$ ограничивается снизу $1/2$ и, следовательно, семейства случайных величин из условия 3 определения 1 не могут быть статистически неотличимыми.

Условие 3 определения 1 эквивалентно условию непредсказуемости следующего бита для семейства случайных величин $(g(\widetilde u_n)\,|\, n\in\mathbb N)$ (см. Непредсказуемость следующего бита).

Если $g$ — псевдослучайный генератор, отображающий $\{0,1\}^n$ в $\{0,1\}^{m(n)}$ при любом $n\in\mathbb N$, то $x\mapsto g(x)_{[1,\dots,\lvert{x}\rvert+1]}$ — псевдослучайный генератор, отображающий $\{0,1\}^n$ в $\{0,1\}^{n+1}$ для всех $n\in\mathbb N$. Обратно, пусть $g$ — произвольная функция, отображающая $\{0,1\}^n$ в $\{0,1\}^{n+1}$ при любом $n\in\mathbb N$. Для произвольного $i\in\mathbb N$ определим функцию $g_i\colon\{0,1\}^*\to\{0,1\}^*$ (отображающую $\{0,1\}^n$ в $\{0,1\}^{n+i}$ при любом $n\in\mathbb N$) индукцией по $i$ следующим образом: \[ g_0(x)=x,\quad g_{i+1}(x)=g(x)_{[1]}g_i\left(g(x)_{[2,\dots,\lvert{x}\rvert+1]}\right)\quad(x\in\{0,1\}^*). \] Тогда если $g$ — псевдослучайный генератор и $k$ — произвольный полиномиальный параметр, принимающий лишь положительные значения, то $x\mapsto g_{k(\lvert{x}\rvert)}(x)$ — псевдослучайный генератор, отображающий $\{0,1\}^n$ в $\{0,1\}^{n+k(n)}$ для всех $n\in\mathbb N$ (см. [6]). Аналогичная конструкция приводится в [1]; см. также [1]. Таким образом, имеет место

Предложение 2
Если существует какой либо псевдослучайный генератор, то для любого полиномиального параметра $m$, удовлетворяющего неравенству $m(n)>n$ при любом $n\in\mathbb N$, существует псевдослучайный генератор, отображающий $\{0,1\}^n$ в $\{0,1\}^{m(n)}$ для всех $n\in\mathbb N$.

Следующая теорема была доказана в [7] для неоднородной модели вычислений и в [8] для однородной модели вычислений. См. также [9], [10], [11], [1], [6]. Более простое, чем в [9], доказательство этой теоремы см. в [12].

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

Данной теореме предшествовал ряд результатов, согласно которым псевдослучайные генераторы существуют, если существуют односторонние функции, удовлетворяющие некоторым дополнительным условиям (см. [13], [14], [15], [16], [17]). В следующей теореме в качестве примера приводится простая конструкция псевдослучайного генератора на основе односторонней перестановки (см. [1]).

Теорема 4
Если $f\colon\{0,1\}^*\to\{0,1\}^*$ — односторонняя перестановка, а $b$ — трудный предикат для $f$, то функция $x\mapsto f(x)b(x)$ ($x\in\{0,1\}^*$) является псевдослучайным генератором.
Для построения трудного предиката можно воспользоваться известной теоремой Гольдрайха”– Левина (см. функция трудная, предикат трудный). Тогда получается, что если $f\colon\{0,1\}^*\to\{0,1\}^*$ — односторонняя перестановка, то функция \[ (x,y)\mapsto\left(f(x),y,\bigoplus_{i=1}^nx_{[i]}y_{[i]} \right)\quad(x,y\in\{0,1\}^n,\, n\in\mathbb N) \] является псевдослучайным генератором (см. [6]).

Литература

  • [1] Goldreich, O. «Foundations of cryptography. Volume 1 (Basic tools). Volume 2 (Basic applications)» 2001 (v. 1), 2004 (v. 2)
  • [2] Goldreich, O. and Goldwasser, S. and Micali, S. «How to construct random functions» 1984
  • [3] Goldreich, O. and Goldwasser, S. and Micali, S. «How to construct random functions» 1986
  • [4] Naor, M. «Bit commitment using pseudo-randomness» 1989
  • [5] Naor, M. «Bit commitment using pseudorandomness» 1991
  • [6] Luby, M. «Pseudorandomness and cryptographic applications» 1996
  • [7] Impagliazzo, R. and Levin, L. A. and Luby, M. «Pseudo-random generation from one-way functions» 1989
  • [8] H\aastad, J. «Pseudo-random generators under uniform assumptions» 1990
  • [9] H\aastad, J. and Impagliazzo, R. and Levin, L. A. and Luby, M. «Construction of a pseudo-random generator from any one-way function» 1999
  • [10] H\aastad, J. and Impagliazzo, R. and Levin, L. A. and Luby, M. «Construction of a pseudo-random generator from any one-way function» 1991
  • [11] Impagliazzo, R. and Luby, M. «Pseudo-random number generator from any one-way function» 1989
  • [12] Holenstein, T. «Pseudorandom generators from one-way functions: A simple construction for any hardness» 2006
  • [13] Yao, A. C. «Theory and applications of trapdoor functions» 1982
  • [14] Levin, L. A. «One-way functions and pseudorandom generators» 1985
  • [15] Levin, L. A. «One-way functions and pseudorandom generators» 1987
  • [16] Goldreich, O. and Krawczyk, H. and Luby, M. «On the existence of pseudorandom generators» 1988
  • [17] Goldreich, O. and Krawczyk, H. and Luby, M. «On the existence of pseudorandom generators» 1993

Адрес редакции сайта: dialogus@cryptography.ru
© При копировании материалов ссылка на авторов,
© а при их отсутствии — на сайт, обязательна