Лемма о невозможности существования вычислительно безопасных шифров в случае P = NP — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Формулировка)
(Доказательство)
Строка 4: Строка 4:
  
 
==Доказательство==
 
==Доказательство==
Рассмотрим язык <tex>S = \{ y | \exists i \in \{0,1\}^{n}: y = E_{i}(0^{m})\}</tex>.
+
Рассмотрим язык <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 * P(A(E_{i}(x_{0})) = 0) + 0,5 * P(A(E_{i}(x_{1})) = 1)</tex>.

Версия 13:28, 26 мая 2010

Формулировка

Пусть 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]. Тогда [math]\exists A: \{0,1\}^{m} \to \{0,1\}[/math], [math]A \in P[/math] такая, что для нее в свою очередь [math] \exists x_{0}, x_{1}[/math] такие, что вероятность [math]P(A(E_{i}(x_{b}))=b) \ge 0,75[/math] по всем [math]b \in \{0,1\}[/math] и всем [math]i \in \{0,1\}^{n}[/math].

Доказательство

Рассмотрим язык [math]S = \{ y | \exists i \in \{0,1\}^{n}: y = E_{i}(0^{m})\}[/math]. Заметим, что этот язык лежит в NP. Сертификатом для слова [math]y[/math] является номер [math]i[/math] шифрующей функции [math]E_{i}[/math] такой, что [math]y = E_{i}(0^{m})[/math]. Так как NP [math]=[/math] P, то [math]S[/math] лежит в классе P. А тогда существует функция [math]A(y) \in P[/math], равная нулю, если [math]y \in S[/math], и единице в противном случае. Оценим вероятность [math]P(A(E_{i}(x_{b})) = b)[/math] при [math]x_{0} = 0^{m}[/math] и некотором [math]x_{1}[/math]. Заметим, что так как [math]b[/math] равновероятно может быть и нулем, и единицей, то [math]P(A(E_{i}(x_{b})) = b) = 0,5 * P(A(E_{i}(x_{0})) = 0) + 0,5 * P(A(E_{i}(x_{1})) = 1)[/math].