Введение в современную криптографию
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
- Бұл бет үшін навигация:
- ПРЕДПОЛОЖЕНИЕ 7.17
- ДОКАЗАТЕЛЬСТВО
- УТВЕРЖДЕНИЕ 7.18
| Полное доказательство
Мы предполагаем знакомство с упрощенными доказательствами в предыдущих раз- делах и основываемся на идеях, развитых там. Мы основываемся на некоторой терми- нологии и стандартных результатах из теории вероятности, обсуждаемых в Приложе- нии 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. Детали далее. жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|