Изменения
→Формулировка
==Формулировка==
Имеется набор схема шифрования <tex>(E, D)</tex> с набором из <tex>k = 2^{n}</tex> схем шифрования ключей. Будем обозначать шифрующую функцию с ключом <tex>\{\langle E_{i}, D_{i}\rangle\}</tex>, где как <tex>E_{i}</tex> — функция , а функцию для шифрования, расшифрования с тем же ключом как <tex>D_{i}</tex> — функция для расшифрования. Обе функции биективны. То есть при любом <tex>i</tex> выполняется следующее: <tex>E_{i}(x) = c \Leftrightarrow D_{i}(c) = x</tex>. На схему подаются слова длины <tex>m</tex>, при этом <tex>m > n</tex>.
Тогда, если '''P''' <tex>=</tex> '''NP''', то существует функция <tex> A: \{0,1\}^{m} \to \{0,1\}</tex>, вычислимая за полиномиальное время от входа, такая, что для нее в свою очередь существуют слова <tex>x_{0}</tex> и <tex>x_{1}</tex> такие, что вероятность <tex>P(A(E_{i}(x_{b}))=b) \ge 0.75</tex> по всем <tex>b \in \{0,1\}</tex> и всем <tex>i \in \{0,1\}^{n}</tex>.
Если '''P''' <tex>=</tex> '''NP''', то получается, что для любого набора схем любой схемы шифрования размером с количеством ключей меньше, чем длина шифруемых слов, найдется пара таких слов, которые можно различить с высокой вероятностью. С другой стороны, как будет видно из доказательства, эта пара слов неконструктивна.
==Доказательство==
