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

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

Имеется набор из [math]k = 2^{n}[/math] схем шифрования [math]\{\langle E_{i}, D_{i}\rangle\}[/math], где [math]E_{i}[/math] — функция для шифрования, [math]D_{i}[/math] — функция для расшифрования. Обе функции биективны. На схему подаются слова длины [math]m[/math], при этом [math]m \gt n[/math]. То есть при любом [math]i[/math] выполняется следующее: [math]E_{i}(x) = c \Rightleftarrow D_{i}(c) = x[/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].