Односторонние функции и псевдослучайные генераторы

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

Определения

• Функция [math] \epsilon(n) [/math] называется пренебрежимо малой, если [math] \forall c \gt 0 [/math] и достаточно больших [math] n:~\epsilon(n) = o(n^{-c}) [/math]. Пример: [math] 1/2^n [/math].
• Функция [math] f [/math] называется односторонней, если для любого полиномиального вероятностного алгоритма [math] A [/math] существует пренебрежимо малая функция [math] \epsilon (n)[/math] такая, что для любого натурального [math] n [/math] вероятность [math] P_{A}(A(f(x)) = x) \lt \epsilon (n)[/math] по всем [math] x \in \{0,1\}^n [/math].

Гипотеза

• Односторонние функции существуют.

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

1. [math] f(x,y) = xy [/math]
2. RSA: [math] f_{e,n}(x) = x^e \bmod n [/math]
3. Функция Рабина: [math] f(x,n) = x^2 \bmod n [/math]

Теорема

Если P = NP, то не существует односторонних функций.

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

Рассмотрим язык [math] L = \{\langle a,y \rangle ~|~ \exists x, a [/math] - префикс [math] x, f(x) = y \} [/math].

[math] L \in NP [/math] и, так как по условию [math] NP = P [/math], то [math] L \in P [/math]. Заметим, что подбирая по одному биту, [math] x [/math] легко восстанавливается за полином, а значит вероятность [math] P_{A} [/math] из определения односторонних функций не является пренебрежимо малой и, следовательно, односторонних функций существовать не может.

Определение

Система шифрования называется вычислительно безопасной, если для любого полиномиального вероятностного алгоритма [math] A [/math] существует пренебрежимо малая функция [math] \epsilon (n) [/math] такая, что вероятность [math] P(A(E_{k}(x)) = (i,b) \wedge x_{i} = b) \le 1/2 + \epsilon(n) [/math] по всем [math] k \in K = \{0,1\}^n, x \in \{0,1\}^m [/math]. То есть любой выбранный наугад бит текста в лучшем случае может быть угадан перехватчиком с вероятностью, большей, чем [math] 1/2 [/math], на пренебрежимо малую величину.

Теорема

Если существуют односторонние функции, то для любого натурального [math]c[/math] существует [math]\langle E,D \rangle[/math] - вычислительно безопасная схема: [math] |k| = n, |x| = n^c [/math], то есть использующая ключи длины [math]n[/math] для сообщений размера [math]n^{c}[/math].

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

Определение

Функция [math] G: \{0,1\}^n \to \{0,1\}^m, m \gt n [/math] называется псевдослучайным генератором, если для любого полиномиального вероятностного алгоритма [math] A [/math] и любого натурального [math] n [/math] существует пренебрежимо малая функция [math] \epsilon (n) [/math] такая, что разность вероятностей [math] |P(A(G(x)) = 1) - P(A(y) = 1)| \lt \epsilon (n)[/math] по всем [math] x \in \{0,1\}^n, y \in \{0,1\}^m [/math].

Теорема

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

Определение

Функция [math] G: \{0,1\}^n \to \{0,1\}^m, m \gt n [/math] называется непредсказуемой, если для любого полиномиального вероятностного алгоритма [math] A [/math] и любого натурального [math] n [/math] существует пренебрежимо малая функция [math] \epsilon (n) [/math] такая, что вероятность [math] P(A(1^n, y_{1},...,y_{i-1}) = y_{i} \wedge y = G(x)) \le 1/2 + \epsilon(n) [/math] по всем [math] x \in \{0,1\}^n [/math]. Иными словами, предсказать [math]i[/math]-й бит, зная предыдущие [math]i-1[/math] бит, трудно для любого полиномиального алгоритма.

Теорема

Функция [math] G [/math] является случайным генератором тогда и только тогда, когда [math] G [/math] - непредсказуемая.