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

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

Пусть P [math]=[/math] NP. Имеется набор схем шифрования [math]\{\langle E_{i}, D_{i}\rangle\}[/math], где [math]0 \le i \le k = 2^{n}[/math], [math]E_{i} \in P[/math], [math]D_{i} \in P[/math]. На схему подаются слова длины [math]m[/math], при этом [math]m \gt n[/math]. Тогда [math]\exists A: \{0,1\}^{m} \to \{0,1\}[/math], [math]A \in P[/math] такая, что для нее в свою очередь [math] \exists x_{0}, 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].

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

Рассмотрим язык [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 * P(A(E_{i}(x_{0})) = 0) + 0,5 * 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].