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

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).

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

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