Лемма о невозможности существования вычислительно безопасных шифров в случае P = NP
Формулировка
Пусть 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].