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



Pdf көрінісі
бет206/249
Дата14.06.2023
өлшемі6.4 Mb.
#475029
1   ...   202   203   204   205   206   207   208   209   ...   249
Криптография Катц

Полное доказательство
Мы предполагаем знакомство с упрощенными доказательствами в предыдущих раз-
делах и основываемся на идеях, развитых там. Мы основываемся на некоторой терми-
нологии и стандартных результатах из теории вероятности, обсуждаемых в Приложе-
нии A.3. Докажем следующее предположение, которое выражает теорема 7.12:
ПРЕДПОЛОЖЕНИЕ 7.17 Пусть f и gl будут как в теореме 7.12. Если суще-
ствует вероятностный полиномиально-временной алгоритм A и полином p(•), 
такой что
 
для бесконечного множества значений n, то существует вероятностный по-
линомиально-временной алгоритм Ar и полином pr(•), такой что
для бесконечного множества значений n.
ДОКАЗАТЕЛЬСТВО Еще раз зададим ε(n) = 1/p(n) и рассмотрим только те 
значения n, для которых 
. Дальнейшее ана-
логично утверждению 7.15 и доказывается тем же способом.
УТВЕРЖДЕНИЕ 7.18 Пусть n будет таким, чтобы
Тогда существует множество Sn ∈{0, 1}n размера не менее ε(n)/2 • 2n , такое 
что для каждого x ∈ Sn справедливо, что
Если мы начнем, пытаясь доказать аналогию утверждению 7.16, то лучшее, 
что мы может утверждать здесь это то, что если x ∈ Sn , то мы имеем


280
для любого i. Таким образом, если мы пытаемся использовать A(f (x), r) ⊕ A(f 
(x), r ⊕ ei) в качестве оценки для xi, то все, что мы можем утвеждать - это то, что 
эта оценка будет корректной с вероятностью не менее ε(n), которая не может 
быть лучше, чем принять случайный прогноз! Мы не можем утверждать, что 
инверсия результата дает хорошую оценку в любом случае.
Вместо этого, мы разработаем Ar так, чтобы он вычислял gl(x, r) и gl(x, r⊕ei) при вы-
зове A только один раз. Мы сделаем это, имея Ar, запустим A(x, r ⊕ ei), и имея Ar просто 
“угадаем” само значение gl(x, r). Наивным способом сделать это, было бы выбрать не-
зависимые друг от друга r, как и ранее, и имея Ar, дать независимый прогноз gl(x, r) для 
каждого значения r. Но тогда вероятность того, что все эти прогнозы правильные , что, 
как мы увидим, необходимо, если Ar является выходом корректной инверсии, было бы 
пренебрежимо малым, поскольку используется полиномиальное множество r.
Ключевое наблюдение настоящего доказательства состоит в том, что Ar может 
генерировать r парно-независимым способом, и делать свои прогнозы определен-
ным образом так, чтобы его прогнозы были правильными, с не пренебрежимо ма-
лой вероятностью. В частности, чтобы генерировать m значений r, мы имеем Ar , 
выбираем A = |log(m + 1)| независимо и равномерно распределенные строки s1, . . . , 
sA ∈ {0, 1}n. Затем, для каждого непустого подмножества I∈{1, . . . , A}, мы задаем 
rI := ⊕i I si. Поскольку существуют 2A − 1 непустых подмножеств, это определяет 
набор 2flog(m+1){ − 1 ≥ m строк. Каждая такая строка имеет равномерное распреде-
ление. Эти строки не являются независимыми, но они являются попарно независи-
мыми. Чтобы убедиться в этом, обратите внимание, что для каждых двух подмно-
жеств I ƒ= J существует индекс j ∈ I∩ J, такой что j ∉/ I ∩ J . Без потери общности
предположим j ƒ∩ I. Тогда значение sj является равномерным и независимым от 
значения rI . Поскольку sj включено в исключающее ИЛИ (XOR), которое опре-
деляет rJ , это означает, что rJ также является равномерным и независимым от rI .
Теперь у нас есть два следующих важных замечания:
1. С учетом gl(x, s1), . . . , gl(x, sA ), можно вычислить gl(x, rI ) для каждого 
подмножества I ∈ {1, . . . , A}. Это потому, что gl(x, rI ) = gl(x, ⊕i I si) = ⊕gl(x, si).
2. Если Ar просто прогнозирует значения gl(x, s1), . . . , gl(x, sA ) выбирая 
однородный бит для каждого, то все эти прогнозы будут корректными с вероят-
ностью 1/2A. Если m является полиномом в параметре безопасности n, то 1/2A
не пренебрежимо мало, и, таким образом, при не пренебрежимо малой вероят-
ности Ar корректно прогнозирует все значения gl(x, s1), . . . , gl(x, sA ).
Сочетание указанного выше дает способ получения m = poly(n) равномерных и по-
парно-независимых строк {rI }, наряду с корректными значениями для {gl(x, rI )} при не 


281
пренебрежимо малой вероятности.. Эти значения затем можно использовать, чтобы вы-
числить xi тем же способом, как и в доказательстве предположения 7.14. Детали далее.


Достарыңызбен бөлісу:
1   ...   202   203   204   205   206   207   208   209   ...   249




©dereksiz.org 2024
әкімшілігінің қараңыз

    Басты бет