Изменения
Новая страница: «=== Односторонние функции === == Определения == * Функция <tex> \epsilon(n) </tex> называется ''пренебрежи…»
=== Односторонние функции ===
== Определения ==
* Функция <tex> \epsilon(n) </tex> называется ''пренебрежимо малой'', если <tex> \forall c > 0 ~~\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(x,y) = xy </tex>
# RSA: <tex> f_{e,n}(x) = x^e~mod~n </tex>
# Функция Рабина: <tex> f(x,n) = x^2~mod~n </tex>
== Теорема ==
Если '''P''' = '''NP''', то не существует односторонних функций.
===== Доказательство: =====
Рассмотрим язык <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> A </tex>, удовлетворяющего классу [[Сложностный класс BPP|BPP]] выполнено:
вероятность <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> \epsilon(n) </tex> называется ''пренебрежимо малой'', если <tex> \forall c > 0 ~~\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(x,y) = xy </tex>
# RSA: <tex> f_{e,n}(x) = x^e~mod~n </tex>
# Функция Рабина: <tex> f(x,n) = x^2~mod~n </tex>
== Теорема ==
Если '''P''' = '''NP''', то не существует односторонних функций.
===== Доказательство: =====
Рассмотрим язык <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> A </tex>, удовлетворяющего классу [[Сложностный класс BPP|BPP]] выполнено:
вероятность <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>
===== Без доказательства =====
