Лемма о невозможности существования вычислительно безопасных шифров в случае P = NP — различия между версиями
(→Формулировка) |
м (rollbackEdits.php mass rollback) |
||
(не показано 19 промежуточных версий 3 участников) | |||
Строка 1: | Строка 1: | ||
==Формулировка== | ==Формулировка== | ||
− | + | Имеется схема шифрования <tex>(E, D)</tex> с набором из <tex>k = 2^{n}</tex> ключей. Будем обозначать шифрующую функцию с ключом <tex>i</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''', то получается, что для любой схемы шифрования с количеством ключей меньше, чем длина шифруемых слов, найдется пара таких слов, которые можно различить с высокой вероятностью. С другой стороны, как будет видно из доказательства, эта пара слов неконструктивна. | ||
+ | |||
+ | ==Доказательство== | ||
+ | Рассмотрим язык <tex>S = \{ y | \exists i \in \{0,1\}^{n}: y = E_{i}(0^{m})\}</tex>. Заметим, что этот язык лежит в '''NP'''. Сертификатом для слова <tex>y</tex> является номер <tex>i</tex> шифрующей функции <tex>E_{i}</tex> такой, что <tex>y = E_{i}(0^{m})</tex>. Так как '''NP''' <tex>=</tex> '''P''', то <tex>S</tex> лежит в классе '''P'''. А тогда существует функция <tex>A(y) \in P</tex>, равная нулю, если <tex>y \in S</tex>, и единице в противном случае. | ||
+ | |||
+ | Оценим вероятность <tex>P(A(E_{i}(x_{b})) = b)</tex> при <tex>x_{0} = 0^{m}</tex> и некотором <tex>x_{1}</tex>. Заметим, что так как <tex>b</tex> равновероятно может быть и нулем, и единицей, то: | ||
+ | |||
+ | <tex>P(A(E_{i}(x_{b})) = b) = 0.5 \cdot P(A(E_{i}(x_{0})) = 0) + 0.5 \cdot P(A(E_{i}(x_{1})) = 1)</tex>. | ||
+ | |||
+ | <tex>E_{i}(x_{0})</tex> лежит в <tex>S</tex> при любом <tex>i</tex> по определению <tex>S</tex> и выбору <tex>x_{0}</tex>. Таким образом <tex>P(A(E_{i}(x_{0})) = 0) = 1</tex>. | ||
+ | |||
+ | Докажем теперь, что <tex>\exists x_{1}</tex> такой, что <tex>P(A(E_{i}(x_{1})) = 1) \ge 0.5</tex>. Так как каждая шифрующая функция <tex>E_{i}</tex> биективна, а <tex>|S| \le 2^{n}</tex>, то <tex>\sum \limits_{x} A(E_{i}(x)) \ge 2^{m} - 2^{n}</tex> для любого <tex>i</tex>. Тогда <tex>\sum \limits_{i} \sum \limits_{x} A(E_{i}(x)) = \sum \limits_{x} \sum \limits_{i} A(E_{i}(x)) \ge 2^{n} (2^{m} - 2^{n})</tex>. Из этого неравенства следует, что не может быть для любого <tex>x</tex>: <tex>\sum \limits_{i} A(E_{i}(x)) < 2^{n} (1 - 2^{n-m})</tex>. Следовательно, <tex>\exists x_{1}</tex> такой, что <tex>\sum \limits_{i} A(E_{i}(x_{1})) \ge 2^{n} (1 - 2^{n-m}) \ge 2^{n-1}</tex>, а вероятность по всем <tex>i \in \{0,1\}^{n}</tex> <tex>P(A(E_{i}(x_{1})) = 1) \ge 0.5</tex>. | ||
+ | |||
+ | Таким образом <tex>P(A(E_{i}(x_{b})) = b) \ge 0.5 \cdot 1 + 0.5 \cdot 0.5 = 0.75</tex>. |
Текущая версия на 19:14, 4 сентября 2022
Формулировка
Имеется схема шифрования
с набором из ключей. Будем обозначать шифрующую функцию с ключом как , а функцию для расшифрования с тем же ключом как . Обе функции биективны. То есть при любом выполняется следующее: . На схему подаются слова длины , при этом .Тогда, если P
NP, то существует функция , вычислимая за полиномиальное время от входа, такая, что для нее в свою очередь существуют слова и такие, что вероятность по всем и всем .Если P
NP, то получается, что для любой схемы шифрования с количеством ключей меньше, чем длина шифруемых слов, найдется пара таких слов, которые можно различить с высокой вероятностью. С другой стороны, как будет видно из доказательства, эта пара слов неконструктивна.Доказательство
Рассмотрим язык
. Заметим, что этот язык лежит в NP. Сертификатом для слова является номер шифрующей функции такой, что . Так как NP P, то лежит в классе P. А тогда существует функция , равная нулю, если , и единице в противном случае.Оценим вероятность
при и некотором . Заметим, что так как равновероятно может быть и нулем, и единицей, то:.
лежит в при любом по определению и выбору . Таким образом .
Докажем теперь, что
такой, что . Так как каждая шифрующая функция биективна, а , то для любого . Тогда . Из этого неравенства следует, что не может быть для любого : . Следовательно, такой, что , а вероятность по всем .Таким образом
.