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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Формулировка)
(Формулировка)
Строка 1: Строка 1:
 
==Формулировка==
 
==Формулировка==
  
Пусть '''P''' <tex>=</tex> '''NP'''. Имеется набор схем шифрования <tex>\{\langle E_{i}, D_{i}\rangle\}</tex>, где <tex>0 \le i \le k = 2^{n}</tex>, <tex>E_{i} \in P</tex>, <tex>D_{i} \in P</tex>. На схему подаются слова длины <tex>m</tex>, при этом <tex>m > n</tex>. Тогда <tex>\exists A: \{0,1\}^{m} \Rightarrow \{0,1\}</tex>, <tex>A \in P</tex> такая, что для нее в свою очередь <tex> \exists x_{0}, 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>\{\langle E_{i}, D_{i}\rangle\}</tex>, где <tex>0 \le i \le k = 2^{n}</tex>, <tex>E_{i} \in P</tex>, <tex>D_{i} \in P</tex>. На схему подаются слова длины <tex>m</tex>, при этом <tex>m > n</tex>. Тогда <tex>\exists A: \{0,1\}^{m} \to \{0,1\}</tex>, <tex>A \in P</tex> такая, что для нее в свою очередь <tex> \exists x_{0}, 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>.
  
 
==Доказательство==
 
==Доказательство==
 
Рассмотрим язык <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>.

Версия 13:16, 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].