Изменения
→Доказательство
Оценим вероятность <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>.
