93
линомиального числа запросов пренебрежимо мала. (Это следует из результа-
тов Приложения А.4.)
Предположение 3.27Если F — псевдослучайная перестановка и, к тому же,
Ain(n) ≥ n, то F также является псевднопроизвольной функцией.
Если F — это перестановка с ключом, то криптографические схемы, осно-
ванные на F могут предполагать наличие честных участников для вычисления
обратной функции F −1 в добавление к вычислению самой функции Fk . Это
потенциально предполагает новые проблемы с безопасностью. В частности, в
этом случае, возможно, необходимо ввести более сильное требование, а имен-
но, что Fk должна быть неотличимой от равномерной перестановки даже если
дистинктору дополнительно предосталяется оракульный
доступ к обратной
функции этой перестановки. Если F обладает этой характеристикой, то мы на-
зовем ее сильной псевдослучайной перестановкой.
ОПРЕДЕЛЕНИЕ 3.28 Пусть F:{0, 1}*×{0, 1}*→{0, 1}* будет эффективной,
сохраняющей длину перестановкой с ключом. F является сильной псевдослучай-
ной перестановкой, если для всех вероятностных полиномиальных дистинкто-
ров D, существует пренебрежимо малая функция negl
, такая что:
где первая вероятность вычисляется над равномерно выбранными k∈
{0,1}n и
произвольным D, а вторая вероятность вычисляется над равномерно выбран-
ными f∈
Permn и и произвольным D.
Очевидным образом, любая сильная псевдослучайная перестановка является
также псевдослучайной перестановкой.
Достарыңызбен бөлісу: