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