Введение в современную криптографию
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
- Бұл бет үшін навигация:
- ПРЕДПОЛОЖЕНИЕ 7.14
- ДОКАЗАТЕЛЬСТВО
| Более сложный случай
Теперь покажем, что для любого вероятностного полиномиально-временного ал- горитма A сложно вычислить gl(x, r) из (f (x), r) с вероятностью существенно выше, чем 3/4. Мы снова покажем, что любой такой A предполагал бы существование по- линомиально-временного алгоритма Ar , который инвертирует f с не пренебрежи- мо малой вероятностью. Обратите внимание, что стратегия доказательства предпо- ложения 7.13 терпит здесь неудачу, возможно, потому что A никогда не достигает цели, если r = ei (несмотря на то, что он может сработать успешно, скажем, при всех других значениях r). Кроме того, в данном случае Ar не знает, результат A(f (x), r) равен gl(x, r) или нет; единственное, что знает Ar – это то, что с большой вероятно- стью алгоритм A является правильным. Это еще более усложняет доказательство. ПРЕДПОЛОЖЕНИЕ 7.14 Пусть f и gl будут как в теореме 7.12. Если суще- ствует вероятностный полиномиально-временной алгоритм A и полином p(•), такой что для бесконечного множества значений n, то существует вероятностный по- линомиально-временной алгоритм Ar, такой что для бесконечного множества значений n. ДОКАЗАТЕЛЬСТВО Главное наблюдение, лежащее в основе доказатель- ства этого предположения, заключается в том, что для каждого r∈ {0, 1}n, зна- 276 чения gl(x, r ⊕ ei) и gl(x, r) вместе можно использовать, чтобы вычислить i-й бит x. (Напомним, что ei обозначает n-битную строку с нулями везде, кроме i-й позиции.) Это справедливо, поскольку где r¯i – дополнение ri, а второе равенство является следствием того факта, что для j ƒ= i значение xj • rj появляется в обеих суммах и, таким образом, сокращается. При- веденное выше показывает, что если A реагирует правильно как на (f (x), r) так и на (f (x), r ⊕ ei), то Ar то можно правильно вычислить xi. К сожалению, Ar не знает, ког- да A реагирует правильно и когда нет; Ar знает только, что A реагирует правильно с «высокой» вероятностью. По этой причине Ar применит многочисленные случайные значения r, используя каждое из них, чтобы получить оценку xi, а затем возьмет оцен- ку, появляющуюся большую часть времени, в качестве ее итогового прогноза для xi. В качестве предварительного шага, мы покажем, что для многих x вероят- ность того, что A реагирует корректно, как для (f (x), r) так и (f (x), r ⊕ ei), когда r однородное, достаточно высока. Это позволяет нам зафиксировать x и затем сосредоточиться на равномерном выборе r, который упрощает анализ. жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|