Лемма о невозможности существования вычислительно безопасных шифров в случае P = NP — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Формулировка)
(Формулировка)
Строка 1: Строка 1:
 
==Формулировка==
 
==Формулировка==
  
Имеется набор из <tex>k = 2^{n}</tex> схем шифрования <tex>\{\langle E_{i}, D_{i}\rangle\}</tex>, где <tex>E_{i}</tex> &mdash; функция для шифрования, <tex>D_{i}</tex> &mdash; функция для расшифрования. Обе функции биективны. То есть при любом <tex>i</tex> выполняется следующее: <tex>E_{i}(x) = c \Leftrightarrow D_{i}(c) = x</tex>. На схему подаются слова длины <tex>m</tex>, при этом <tex>m > n</tex>.  
+
Имеется схема шифрования <tex>(E, D)</tex> с набором из <tex>k = 2^{n}</tex> ключей. Будем обозначать шифрующую функцию с ключом <tex>i</tex> как <tex>E_{i}</tex>, а функцию для расшифрования с тем же ключом как <tex>D_{i}</tex>. Обе функции биективны. То есть при любом <tex>i</tex> выполняется следующее: <tex>E_{i}(x) = c \Leftrightarrow D_{i}(c) = x</tex>. На схему подаются слова длины <tex>m</tex>, при этом <tex>m > n</tex>.  
  
 
Тогда, если '''P''' <tex>=</tex> '''NP''', то существует функция <tex> A: \{0,1\}^{m} \to \{0,1\}</tex>, вычислимая за полиномиальное время от входа, такая, что для нее в свою очередь существуют слова <tex>x_{0}</tex> и <tex>x_{1}</tex> такие, что вероятность <tex>P(A(E_{i}(x_{b}))=b) \ge 0.75</tex> по всем <tex>b \in \{0,1\}</tex> и всем <tex>i \in \{0,1\}^{n}</tex>.
 
Тогда, если '''P''' <tex>=</tex> '''NP''', то существует функция <tex> A: \{0,1\}^{m} \to \{0,1\}</tex>, вычислимая за полиномиальное время от входа, такая, что для нее в свою очередь существуют слова <tex>x_{0}</tex> и <tex>x_{1}</tex> такие, что вероятность <tex>P(A(E_{i}(x_{b}))=b) \ge 0.75</tex> по всем <tex>b \in \{0,1\}</tex> и всем <tex>i \in \{0,1\}^{n}</tex>.
  
Если '''P''' <tex>=</tex> '''NP''', то получается, что для любого набора схем шифрования размером меньше, чем длина шифруемых слов, найдется пара таких слов, которые можно различить с высокой вероятностью. С другой стороны, как будет видно из доказательства, эта пара слов неконструктивна.
+
Если '''P''' <tex>=</tex> '''NP''', то получается, что для любой схемы шифрования с количеством ключей меньше, чем длина шифруемых слов, найдется пара таких слов, которые можно различить с высокой вероятностью. С другой стороны, как будет видно из доказательства, эта пара слов неконструктивна.
  
 
==Доказательство==
 
==Доказательство==

Версия 17:19, 27 мая 2010

Формулировка

Имеется схема шифрования [math](E, D)[/math] с набором из [math]k = 2^{n}[/math] ключей. Будем обозначать шифрующую функцию с ключом [math]i[/math] как [math]E_{i}[/math], а функцию для расшифрования с тем же ключом как [math]D_{i}[/math]. Обе функции биективны. То есть при любом [math]i[/math] выполняется следующее: [math]E_{i}(x) = c \Leftrightarrow D_{i}(c) = x[/math]. На схему подаются слова длины [math]m[/math], при этом [math]m \gt n[/math].

Тогда, если P [math]=[/math] NP, то существует функция [math] A: \{0,1\}^{m} \to \{0,1\}[/math], вычислимая за полиномиальное время от входа, такая, что для нее в свою очередь существуют слова [math]x_{0}[/math] и [math]x_{1}[/math] такие, что вероятность [math]P(A(E_{i}(x_{b}))=b) \ge 0.75[/math] по всем [math]b \in \{0,1\}[/math] и всем [math]i \in \{0,1\}^{n}[/math].

Если P [math]=[/math] NP, то получается, что для любой схемы шифрования с количеством ключей меньше, чем длина шифруемых слов, найдется пара таких слов, которые можно различить с высокой вероятностью. С другой стороны, как будет видно из доказательства, эта пара слов неконструктивна.

Доказательство

Рассмотрим язык [math]S = \{ y | \exists i \in \{0,1\}^{n}: y = E_{i}(0^{m})\}[/math]. Заметим, что этот язык лежит в NP. Сертификатом для слова [math]y[/math] является номер [math]i[/math] шифрующей функции [math]E_{i}[/math] такой, что [math]y = E_{i}(0^{m})[/math]. Так как NP [math]=[/math] P, то [math]S[/math] лежит в классе P. А тогда существует функция [math]A(y) \in P[/math], равная нулю, если [math]y \in S[/math], и единице в противном случае.

Оценим вероятность [math]P(A(E_{i}(x_{b})) = b)[/math] при [math]x_{0} = 0^{m}[/math] и некотором [math]x_{1}[/math]. Заметим, что так как [math]b[/math] равновероятно может быть и нулем, и единицей, то:

[math]P(A(E_{i}(x_{b})) = b) = 0.5 \cdot P(A(E_{i}(x_{0})) = 0) + 0.5 \cdot P(A(E_{i}(x_{1})) = 1)[/math].

[math]E_{i}(x_{0})[/math] лежит в [math]S[/math] при любом [math]i[/math] по определению [math]S[/math] и выбору [math]x_{0}[/math]. Таким образом [math]P(A(E_{i}(x_{0})) = 0) = 1[/math].

Докажем теперь, что [math]\exists x_{1}[/math] такой, что [math]P(A(E_{i}(x_{1})) = 1) \ge 0.5[/math]. Так как каждая шифрующая функция [math]E_{i}[/math] биективна, а [math]|S| \le 2^{n}[/math], то [math]\sum \limits_{x} A(E_{i}(x)) \ge 2^{m} - 2^{n}[/math] для любого [math]i[/math]. Тогда [math]\sum \limits_{i} \sum \limits_{x} A(E_{i}(x)) = \sum \limits_{x} \sum \limits_{i} A(E_{i}(x)) \ge 2^{n} (2^{m} - 2^{n})[/math]. Из этого неравенства следует, что не может быть для любого [math]x[/math]: [math]\sum \limits_{i} A(E_{i}(x)) \lt 2^{n} (1 - 2^{n-m})[/math]. Следовательно, [math]\exists x_{1}[/math] такой, что [math]\sum \limits_{i} A(E_{i}(x_{1})) \ge 2^{n} (1 - 2^{n-m}) \ge 2^{n-1}[/math], а вероятность по всем [math]i \in \{0,1\}^{n}[/math] [math]P(A(E_{i}(x_{1})) = 1) \ge 0.5[/math].

Таким образом [math]P(A(E_{i}(x_{b})) = b) \ge 0.5 \cdot 1 + 0.5 \cdot 0.5 = 0.75[/math].