Лемма о невозможности существования вычислительно безопасных шифров в случае P = NP
Формулировка
Пусть P
NP. Имеется набор схем шифрования , где , , . На схему подаются слова длины , при этом . Тогда такая, что для нее с свою очередь такие, что вероятность по всем и всем .