Введение в современную криптографию
Трудные предикаты из односторонних функций
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
- Бұл бет үшін навигация:
- Простой случай
- ПРЕДПОЛОЖЕНИЕ 7.13
- ДОКАЗАТЕЛЬСТВО
| Трудные предикаты из односторонних функций
В этом разделе мы докажем теорему 7.5, показав следующее: ТЕОРЕМА 7.12 Пусть f - односторонняя функция, определим g как g(x, r) (f (x), r), где |x| = |r|. Определим gl(x, r) ⊕Lni=1xi • ri, где x = x1 • • • xn и r = r1 • • • rn. Then gl является трудным предикатом g. Ввиду сложности доказательства , мы докажем последовательно три более стро- гих результата, достигающие высшей точки в том, что утверждается в теореме. Простой случай Покажем сначала, что если существует полиномиально-временной оппонент A, который всегда правильно вычисляет gl(x, r) при условии g(x, r) = (f (x), r), то можно инвертировать f в течение полиномиального времени. С учетом предпо- ложения, что f является односторонней функций, следует, что такого противни- ка A не существует. ПРЕДПОЛОЖЕНИЕ 7.13 Пусть f и gl такие, как в теореме 7.12. Если су- ществует полиномиально-временной алгоритм A, такой что A(f (x), r) =gl(x, r) для всех n и всех x,r∈{0,1}n, то существует полиномиально-временной алго- ритм Ar, такой что Ar(1n,f (x)) = x для всех nи всех x∈{0,1}n. ДОКАЗАТЕЛЬСТВО Построим Ar следующим образом. Ar(1n, y) вы- числяет xi := A(y, ei) для i = 1, . . . , n, где ei обозначает n-битную строку с 1 275 в i-й позиции и 0 везде, кроме данной точки.. Тогда Ar выводит x = x1 • • • xn. Очевидно, что Ar работает в течение полиномиального времени. При выполнении Ar(1n, f (xˆ)), значение xi, рассчитанное Ar, удовлетворяет Таким образом, xi = xˆi для всех i и тем самым Ar выводит правильную ин- версию x = xˆ. Если f – односторонняя, то для любого вероятностного алгоритма невозмож- но инвертировать f с пренебрежимо малой вероятностью. Таким образом, мы приходим к выводу, что не существует полиномиально-временного алгоритма, который всегда правильно вычисляет gl(x, r) из (f (x), r). Это довольно слабый результат, что очень далено от нашей цели показать, что gl(x, r) невозможно вы- числить (с вероятностью существенно выше, чем 1/2) с учетом (f (x), r). жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|