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


Трудные предикаты из односторонних функций



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

 Трудные предикаты из односторонних функций
В этом разделе мы докажем теорему 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).


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




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

    Басты бет