142
где g выбирается единообразно из Funcn, а f выбирается единообразно из на-
бора функций, преобразовывающих ({0, 1}n)* в {0, 1}n.
(Утверждение ничем не обусловлено и не накладывает никаких ограничений
на время работы D. Таким образом, мы можем заставить D быть детерминиро-
ванной.) Вышесказанное подразумевает Теорему 4.13, используя стандартные
методы, которые мы уже проходили. В частности, для любых D, работающих
в полиномиальном времени, мы должны иметь q(n), A(n) = poly(n), и поэтому
q(n)2A(n)2 • 2−n является незначительным .
ДОКАЗАТЕЛЬСТВО ( Утверждения 4.14)
Зафиксируем n ≥ 1. Доказатель-
ство происходит в два этапа: Для начала определим понятие гладкость и докажем, что
CBC
является гладкой;
затем мы покажем, что гладкость подразумевает утверждение.
Пусть P = {X1, . . . , Xq } будет беспрефиксным набором q входных данных,
каждый Xi в ({0, 1}n)*, а самая длинная строка вP содержит A блоков (то есть
каждый Xi ∈ P содержит максимум A блоков длиной n). Обратите внимание, что
для t1, . . . , tq ∈ {0, 1}n iсправедливо, что Pr [ i : f (Xi) = ti] = 2−nq, когда вероят-
ность выше единообразного выбора функции f из набора функций, преобразу-
ющих ({0, 1}n)* в {0, 1}n. Скажем, что CBC является (q, A, δ)-гладкой, если для
каждого беспрефиксного набора P ={X1, . . . , Xq } , как сказано выше, и каждого
t1, . . . , tq ∈ {0, 1}n, справедливо, что
когда вероятность выше единообразного выбора g ∈ Funcn .
Другими словами, CBC является гладкой, если для каждого фиксированного
набора входных/выходных пар {(Xi, ti)}, где {Xi} формирует беспрефиксный
набор, вероятность того, что CBCg (Xi) = ti для всех i - δ-близка к вероятности
того, что f (Xi) = ti для всех i (где g является случайной функцией от {0, 1}n в {0,
1}n, а f является случайной функцией из ({0, 1}n)* до {0, 1}n).
Достарыңызбен бөлісу: