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



Pdf көрінісі
бет197/249
Дата14.06.2023
өлшемі6.4 Mb.
#475029
1   ...   193   194   195   196   197   198   199   200   ...   249
Криптография Катц

ОПРЕДЕЛЕНИЕ 7.1 Функция f:{0,1}*→{0,1}* является односторонней
если выполняются следующие условия:
1. (Несложно вычислить:) Имеется полиномиально-временной алгоритм 
Mf, вычисляющий f ; то есть, Mf (x) = f (x) для всех x.
2. (Сложно инвертировать) Для любого вероятностного полиномиально-
временного алгоритма
A существует пренебрежимо малая функция negl, такая что
Pr[InvertA,f (n) = 1] ≤ negl(n).
Примечание. В этой главе мы часто будем делать вероятностное пространство 
более определенным, индексируя (часть) его в вероятностной записи. Например, 
мы можем кратко выразить второе требование в определении, указанном выше,
следующим образом: Для каждого вероятностного полиномиально-временного 
алгоритма A существует пренебрежимо малая функция negl, такая что
(Напомним, что x ← {0, 1}n означает, что x выбирают равномерно из {0, 1}n). 
Вероятность, указанная выше, также берется по случайному распределению, 
используемому A, что остается здесь неясным.
Успешная инверсия односторонних функций. Функцию, которая не яв-
ляется односторонней, не обязательно легко инвертировать всегда (или даже 


268
«часто»). Скорее наоборот, второе условие Определения 7.1 заключается в том, что 
существует вероятностный полиномиально-временной алгоритм A и не пренебре-
жимо малая функция γ, такая что A инвертирует f (x) с вероятностью, минимум, γ (n) 
(где вероятность выбирают по равномерному из x ∈ {0, 1}n и случайному A). Это, 
в свою очередь, означает, что существует положительный многочлен p(•) такой, что 
для бесконечного множество значений n алгоритм A инвертирует f с вероятностью 
не менее 1/p(n). Таким образом, если существует алгоритм A, который инвертирует 
f с вероятностью n−10 для всех четных значений n (но никогда не может инверти-
ровать f, если n нечетное), то f не является односторонней функцией—даже в том 
случае, когда A успешно срабатывает на половине значений n и срабатывает только 
с вероятностью n−10 (для значений n, где он вообще срабатывает).


Достарыңызбен бөлісу:
1   ...   193   194   195   196   197   198   199   200   ...   249




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

    Басты бет