145
Уравнение (4.7), мы, таким образом, имеем
Из Уравнения (4.6) мы получаем Pr[Coll] < q2A2 • 2−n = δ. Наконец, используя
Уравнени (4.5) мы видим, что
как и утверждалось.
Мы теперь видим, что гладкость подразумевает теорему. Предположим, без
потери обобщенности, что D всегда совершает q (разных) запросов, каждый из
которых содержит максимум A блоков. D может выбиратьсвои запросы адап-
тивно (то есть в зависимости от ответов на рпедыдущие запросы), но набор
запросов D должен быть беспрефиксным.
Дt ля разных X1, . . . , Xq ∈ ({0, 1}n)* и произвольных t1, . . . , tq ∈ {0, 1}n,
определим, что α(X1, . . . , Xq ; t1, . . . , tq ) равно 1, если и только если D выводит
1, при запросах X1, . . . , Xq и полчении ответов t1, . . . , tq . (Если, скажем, D не
делает запрос X1
как свой первый запрос, тогда α(X1, . . . ; . . .) = 0.) Допуская,
что X˙ = (X1, . . . , Xq ) и ˙t = (t1, . . . , tq ), мы, таким образом, имеем
где, выше, g выбирается единообразно из Funcn, а f выбирается единообразно
из набора функций, преобразовывающих ({0, 1}n)* в {0, 1}n. Из
этого следует
Симметричный аргумент для того, когда D выводит 0, завершает доказательство.
Достарыңызбен бөлісу: