Изменения

* Функция <tex> f </tex> называется ''односторонней'', если для любого полиномиального вероятностного алгоритма <tex> A </tex> существует пренебрежимо малая функция <tex> \epsilon (n)</tex> такая, что для любого натурального <tex> n </tex> вероятность <tex> P_{A}(A(f(x)) = x) < \epsilon (n)</tex> по всем для случайно выбранного <tex> x \in \{0,1\}^n </tex>.

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

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

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

Слово <tex> x: |x| = n </tex> называется ''с - случайным'', если его нельзя вывести программой на языке Pascal длиной не более <tex> cn </tex>, где <tex> 0 < c < 1 </tex>. == Определение ==Функция <tex> gG: \{0,1\}^n \to \{0,1\}^m, m > n </tex> называется ''псевдослучайным генератором'', если для любого полиномиального вероятностного алгоритма <tex> A </tex> и любого натурального <tex> n </tex> существует пренебрежимо малая функция <tex> \forall A epsilon (n) </tex>такая, удовлетворяющего классу [[Сложностный класс BPP|BPP]], что разность вероятностей <tex> |P(A(gG(x)) = 1) - P(A(y) = 1)| < \epsilon (n)</tex> по всем для случайно выбранных <tex> x \in \{0,1\}^n, y \in \{0,1\}^m </tex> пренебрежимо мала. Иначе говоря, полиномиальному перехватчику невозможно различить случайно сгенерированную строку длины <tex> m </tex> и строку, созданную генератором <tex> G </tex> из более короткой случайной строки длины <tex> n </tex>.

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

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