Введение в современную криптографию

277
Поскольку 
, простая ал-
гебра 
Теперь дальнейшее логически вытекает как простое следствие.
УТВЕРЖДЕНИЕ 7.16 Пусть n будет таким, чтобы

 
Тогда существует множество Sn ∈ {0, 1}n размера, минимум, 1/2p(n) , такое 
что для каждого x ∈Sn и каждого i справедливо следующее
ДОКАЗАТЕЛЬСТВО Пусть ε(n) = 1/p(n), и примем, что Sn будет множе-
ством, гарантированным предыдущим утверждением.. Нам известно, что для 
любого x ∈ Sn имеется
Зафиксируем i ∈ {1, . . . , n}. Если r распределено равномерно, то r ⊕ ei; таким образом
Мы заинтересованы в более низкой ограничивающей вероятности, что A выводит 
правильный ответ как для gl(x, r), так и для gl(x, r ⊕ ei); что то же самое, мы хотим 
для верхней границы вероятности, при которой A не удается вывести правильный 
ответ в любом из этих случаев. Заметим, что r и r ⊕ ei не являются независимыми, 
таким образом, мы не можем просто перемножить вероятности неудачных ответов.
Однако, мы можем применить границу объединения (см. предположение A.7) и 
сложить вероятности неудачных ответов. То есть, вероятность того, что A является 
неправильным или на gl(x, r) или gl(x, r ⊕ ei) равна, не более чем 
и, таким образом, A корректно как на gl(x, r), так и на gl(x, r ⊕ ei) с вероятно-
стью, не менее, чем 1/2 + ε(n). Это доказывает утверждение.
Для остальной части доказательства зададим ε(n) = 1/p(n) и рассмотрим толь-

278
ко те значения n, для которых
Предыдущее утверждение гласит, что для ε(n)/2 доля входов x, и любой i, ал-
горитм A реагирует правильно как на (f (x), r), так и на (f (x), r ⊕ ei) с вероят-
ностью не менее 1/2 + ε(n) при однородном выборе r, и с этого момента мы 
сосредоточимся только на таких значениях x. Построим вероятностный поли-
номиально-временной алгоритм Ar , который инвертирует f (x) с вероятностью 
1/2, когда x ∈ Sn. Этого достаточно, чтобы затем доказать предположение 7.14 
для бесконечного множества значений n,
Алгоритм Ar, заданный как вход 1n и y, работает следующим образом:
1. Для i = 1, . . . , n выполним:
• Несколько раз выберем однородное r ∈ {0, 1}n и вычисдим A(y, r) ⊕ A(y, r 
⊕
ei) в качестве «оценки» i-го бита прообраза y. После выполнения этой про-
цедуры достаточно много раз (см. ниже), будем считать xi «оценкой» того, что 
происходит большую часть времени.
2. Выведем x = x1 • • • xn.
Наметим анализ вероятности того, что Ar правильно инвертирует заданный 
вход y. (Мы позволим себе быть немного лаконичнее, поскольку полное дока-
зательство для более трудного случая приведено в следующем разделе). Пусть 
y = f (xˆ) и напомним, что мы предполагаем здесь, что n такое, что уравнение 
(7.1) справедливо и xˆ ∈ Sn. Зафиксируем некоторое i. Предыдущее требование 
предполагает, что оценка A(y, r) ⊕ A(y, r ⊕ ei) равна gl(xˆ, ei) с вероятностью не 
менее 1 + ε(n) по выбору r. Получая достаточно много оценок и позволяя xi 
быть мажоритарным значением, Ar можно гарантировать, что xi равно gl(xˆ, 
ei) с вероятностью не менее 1 − 1 . Конечно, нужно убедиться, что полино-
миально множество оценок достаточное. К счастью, поскольку ε(n) = 1/p(n) для 
некоторого полинома p и независимое значение r используется для получения 
каждой оценки, граница Чернофф (Chernoff ) (ср. с предположением A.14) по-
казывает, что полиномиально множества оценок достаточно.
Подводя итог, имеем, что для каждого i значение xi, вычисленное Ar , некор-
ректно с вероятностью не более 1/2n. Граница объединения, таким образом, 

279
показывает, что Ar является некорректным для некоторого i с вероятностью 
не более n •1/2n= /2. То есть, Ar является правильным для всех i—и, таким об-
разом правильно инвертирует y—с вероятностью не менее 1 − 1/2 = 1/2 . Это 
завершает доказательство предположения 
Следствие предположения 7.14 заключается в том, что если f является одно-
сторонней функцией, то для любого полиномиально-временного алгоритма A 
вероятность того, что A правильно прогнозирует gl(x, r) при заданном (f (x), r), 
чаще всего, незначительно больше, чем 3/4.

жүктеу/скачать 6.4 Mb.

Достарыңызбен бөлісу: