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

Определения

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

Гипотеза

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

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

1. [math] f(x,y) = xy [/math]
2. RSA: [math] f_{e,n}(x) = x^e~mod~n [/math]
3. Функция Рабина: [math] f(x,n) = x^2~mod~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] x [/math] легко восстанавливается за полином.

Определение

Система шифрования называется вычислительно безопасной, если для любого алгоритма [math] A [/math], удовлетворяющего классу BPP выполнено:

вероятность [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] \epsilon(n) [/math] - пренебрежимо мала.

Теорема

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