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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «=== Односторонние функции === == Определения == * Функция <tex> \epsilon(n) </tex> называется ''пренебрежи…»)
 
Строка 1: Строка 1:
=== Односторонние функции ===
+
= Односторонние функции =
 
== Определения ==
 
== Определения ==
  
Строка 28: Строка 28:
 
Если существуют односторонние функции, то <tex> \forall c ~\exists \langle E,D \rangle</tex> -- вычислительно безопасная схема: <tex> |k| = n, |x| = n^c </tex>
 
Если существуют односторонние функции, то <tex> \forall c ~\exists \langle E,D \rangle</tex> -- вычислительно безопасная схема: <tex> |k| = n, |x| = n^c </tex>
 
===== Без доказательства =====
 
===== Без доказательства =====
 +
 +
= Псевдослучайные генераторы =
 +
== Определение ==
 +
Слово <tex> x: |x| = n </tex> называется ''с - случайным'', если его нельзя вывести программой на языке Pascal длиной не более <tex> cn </tex>, где <tex> 0 < c < 1 </tex>.
 +
 +
== Определение ==
 +
Функция <tex> g: \{0,1\}^n \to \{0,1\}^m, m > n </tex> называется ''псевдослучайным генератором'', если <tex> \forall A </tex>, удовл. классу [[Сложностный класс BPP|BPP]] разность вероятностей <tex> |P(A(g(x)) = 1) - P(A(y) = 1)| </tex> -- пренебрежимо мала. Здесь <tex> x \in \{0,1\}^n, y \in \{0,1\}^m </tex>.
 +
 +
== Теорема ==
 +
Если существуют односторонние функции, то существуют псевдослучайные генераторы.
 +
===== Без доказательства. =====
 +
 +
== Определение ==
 +
Функция <tex> g: \{0,1\}^n \to \{0,1\}^m, m > n </tex> называется ''непредсказуемой'', если если <tex> \forall A </tex>, удовл. классу [[Сложностный класс BPP|BPP]] вероятность <tex> P(A(y_{1},...,y_{i-1},1^n) = y_{i} \wedge y = g(x)) \le 1/2 + \epsilon(n) </tex>, где <tex> x \in \{0,1\}^n </tex>, а функция <tex> \epsilon(n) </tex> -- пренебрежимо мала.
 +
 +
== Теорема ==
 +
Функция <tex> g </tex> является случайным генератором тогда и только тогда, когда <tex> g </tex> - непредсказуемая.
 +
===== Без доказательства. =====

Версия 20:14, 27 мая 2010

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

Определения

  • Функция [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]

Без доказательства

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

Определение

Слово [math] x: |x| = n [/math] называется с - случайным, если его нельзя вывести программой на языке Pascal длиной не более [math] cn [/math], где [math] 0 \lt c \lt 1 [/math].

Определение

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

Теорема

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

Без доказательства.