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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Без доказательства)
м (rollbackEdits.php mass rollback)
 
(не показано 15 промежуточных версий 4 участников)
Строка 2: Строка 2:
 
== Определения ==
 
== Определения ==
  
* Функция <tex> \epsilon(n) </tex> называется ''пренебрежимо малой'', если <tex> \forall c > 0 ~~\epsilon(n) = o(n^{-c}) </tex>. Пример: <tex> 1/2^n </tex>.
+
* Функция <tex> \epsilon(n) </tex> называется ''пренебрежимо малой'', если <tex> \forall c > 0 </tex> и достаточно больших <tex> n:~\epsilon(n) = o(n^{-c}) </tex>. Пример: <tex> 1/2^n </tex>.
* Функция <tex> f </tex> называется ''односторонней'', если <tex> \forall g </tex>, удовлетворяющей классу [[Сложностный класс BPP|BPP]], вероятность <tex> P(g(f(x)) = x) </tex> -- пренебрежимо мала.
+
* Функция <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> f(x,y) = xy </tex>
 
# <tex> f(x,y) = xy </tex>
# RSA: <tex> f_{e,n}(x) = x^e~mod~n </tex>
+
# RSA: <tex> f_{e,n}(x) = x^e \bmod n </tex>
# Функция Рабина: <tex> f(x,n) = x^2~mod~n </tex>
+
# Функция Рабина: <tex> f(x,n) = x^2 \bmod n </tex>
  
 
== Теорема ==
 
== Теорема ==
Строка 18: Строка 18:
 
Рассмотрим язык <tex> L = \{\langle a,y \rangle ~|~ \exists x, a </tex> - префикс <tex> x, f(x) = y \} </tex>.
 
Рассмотрим язык <tex> L = \{\langle a,y \rangle ~|~ \exists x, a </tex> - префикс <tex> x, f(x) = y \} </tex>.
  
<tex> L \in NP </tex>, однако <tex> x </tex> легко восстанавливается за полином.
+
<tex> L \in NP </tex> и, так как по условию <tex> NP = P </tex>, то <tex> L \in P </tex>. Заметим, что подбирая по одному биту, <tex> x </tex> легко восстанавливается за полином и, следовательно, односторонних функций существовать не может.
  
 
== Определение ==
 
== Определение ==
[[системы шифрования|Система шифрования]] называется ''вычислительно безопасной'', если для любого алгоритма <tex> A </tex>, удовлетворяющего классу [[Сложностный класс BPP|BPP]] выполнено:
+
[[системы шифрования|Система шифрования]] называется ''вычислительно безопасной'', если для любого полиномиального вероятностного алгоритма <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> x \in \{0,1\}^m </tex> и произвольного ключа <tex> k \in K = \{0,1\}^n </tex>. То есть любой выбранный наугад бит текста в лучшем случае может быть угадан перехватчиком с вероятностью, большей, чем <tex> 1/2 </tex>, на пренебрежимо малую величину.
 
 
вероятность <tex> P(A(E_{k}(x)) = (i,b) \wedge x_{i} = b) \le 1/2 + \epsilon(n) </tex>, где  <tex> k \in K = \{0,1\}^n, x \in \{0,1\}^m </tex>, а функция <tex> \epsilon(n) </tex> - пренебрежимо мала.
 
  
 
== Теорема ==
 
== Теорема ==
Если существуют односторонние функции, то <tex> \forall c ~\exists \langle E,D \rangle</tex> -- вычислительно безопасная схема: <tex> |k| = n, |x| = n^c </tex>
+
Если существуют односторонние функции, то для любого натурального <tex>c</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> G: \{0,1\}^n \to \{0,1\}^m, m > n </tex> называется ''псевдослучайным генератором'', если для любого полиномиального вероятностного алгоритма <tex> A </tex> и любого натурального <tex> n </tex> существует пренебрежимо малая функция <tex> \epsilon (n) </tex> такая, что разность вероятностей <tex> |P(A(G(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> 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>.
 
  
 
== Теорема ==
 
== Теорема ==
Строка 41: Строка 36:
  
 
== Определение ==
 
== Определение ==
Функция <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: \{0,1\}^n \to \{0,1\}^m, m > n </tex> называется ''непредсказуемой'', если для любого полиномиального вероятностного алгоритма <tex> A </tex> и любого натурального <tex> n </tex> существует пренебрежимо малая функция <tex> \epsilon (n) </tex> такая, что вероятность <tex> P(A(1^n, y_{1},...,y_{i-1}) = y_{i} \wedge y = G(x)) \le 1/2 + \epsilon(n) </tex> для случайно выбранного <tex> x \in \{0,1\}^n </tex>. Иными словами, предсказать <tex>i</tex>-й бит, зная предыдущие <tex>i-1</tex> бит, трудно для любого полиномиального алгоритма.
  
 
== Теорема ==
 
== Теорема ==
Функция <tex> g </tex> является случайным генератором тогда и только тогда, когда <tex> g </tex> - непредсказуемая.
+
Функция <tex> G </tex> является случайным генератором тогда и только тогда, когда <tex> G </tex> - непредсказуемая.
 
===== Без доказательства. =====
 
===== Без доказательства. =====

Текущая версия на 19:06, 4 сентября 2022

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

Определения

  • Функция [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] 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] x \in \{0,1\}^m [/math] и произвольного ключа [math] k \in K = \{0,1\}^n [/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] m [/math] и строку, созданную генератором [math] G [/math] из более короткой случайной строки длины [math] n [/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] - непредсказуемая.

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