Изменения

Перейти к: навигация, поиск
Формулировка
==Формулировка==
Пусть '''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>\exist exists A \in P</tex> такая, что для нее с свою очередь <tex> \exist 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>.
51
правка

Навигация