|
(Метки: правка с мобильного устройства, правка из мобильной версии) |
| Строка 1: |
Строка 1: |
| − | = Односторонние функции =
| + | {{Определение |
| − | == Определения == | + | |definition = |
| − | | + | }} |
| − | * Функция <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> 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>.
| + | {{Определение |
| − | | + | |definition = <tex> \forall x', x'' \in \{0, 1\}^m \\ |
| − | == Гипотеза == | + | E(k, x'), E(k, x'')</tex> (шифрограммы первого сообщения и шифрограммы второго сообщения) распределены одинаково. |
| − | * Односторонние функции существуют.
| + | }} |
| − | | + | === Пример=== |
| − | Строго говоря, нам пока не известна ни одна односторонняя функция. Однако предложено несколько функций, которые могут оказаться односторонними — для этих функций в настоящее время, несмотря на интенсивные исследования, не известны эффективные алгоритмы нахождения обратной функции.
| |
| − | # <tex> f(x,y) = xy </tex>
| |
| − | # RSA: <tex> f_{e,n}(x) = x^e \bmod n </tex>
| |
| − | # Функция Рабина: <tex> f(x,n) = x^2 \bmod 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> NP = P </tex>, то <tex> L \in P </tex>. Заметим, что подбирая по одному биту, <tex> x </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> x \in \{0,1\}^m </tex> и произвольного ключа <tex> k \in K = \{0,1\}^n </tex>. То есть любой выбранный наугад бит текста в лучшем случае может быть угадан перехватчиком с вероятностью, большей, чем <tex> 1/2 </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> 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> 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> - непредсказуемая.
| |
| − | ===== Без доказательства. =====
| |
