Лемма о невозможности существования вычислительно безопасных шифров в случае P = NP
Формулировка
Пусть P NP. Имеется набор схем шифрования , где , , . На схему подаются слова длина , при этом .
Пусть P [math]=[/math] NP. Имеется набор схем шифрования [math]\{E_{i}, D_{i}\}[/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].
