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


Эспоненциально-временная инверсия



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

Эспоненциально-временная инверсия. Любую одностороннюю функцию 
можно инвертировать в любой точке y в экспоненциальном времени, просто 
проверяя все значения x ∈ {0, 1}n до тех пор, пока не будет найдено такое зна-
чение x, что f (x) = y. Таким образом, существование односторонних функций 
- это, по своей сути, предположение о вычислительной сложности и вычисли-
тельной трудности. То есть, речь идет о проблеме, которую можно решить в 
принципе, но предполагается, что ее сложно решить эффективно.
Односторонние перестановки. Нас часто будут интересовать односторон-
ние функции с дополнительными структурными свойствами. Мы говорим, что 
функция f является сохраняющей длину, если |f (x)| = |x| для всех x. Односторон-
няя функция, которая сохраняет длину и сохраняется один-к-одному, называет-
ся односторонней перестановкой. Если f является односторонней функцией, то 
любое значение y имеет уникальный прообраз x = f −1(y). Тем не менее, трудно 
найти x в течение полиномиального времени.
Семейства односторонних функций/перестановок. Приведенные выше 
определения односторонних функций и перестановок удобны тем, что в них рас-
сматривается единственная функция в бесконечной области и диапазоне. Однако 
большинство вариантов односторонних функций и перестановок не вписывают-
ся в эти рамки. Вместо этого существует алгоритм, генерирующий некоторое 
множество параметров I, который определяет функцию fI ; односторонность 
означает здесь, по существу, что fI должна быть односторонней, с практически 
пренебрежимо малой вероятностью, при всех I. Поскольку каждое значение I 
определяет разные функции, мы теперь говорим о семействах односторонних 
функций (соотв., перестановок). Теперь приведем определение и отошлем чита-
теля за конкретным примером к следующему разделу (см. также раздел 8.4.1).
ОПРЕДЕЛЕНИЕ 7.2 Запись Π = (Gen, Samp, f ) вероятностного полиноми-
ально временного алгоритма является семейством функций, если выполняют-
ся следующие условия:


269
1. Алгоритм генерации параметров Gen, на входе 1n, выходные параметры 
I при |I| ≥ n. Каждое значение I выхода Gen определяет множества DI и RI , 
которые устанавливают область и диапазон, соответственно, функции fI .
2. Алгоритм выборки Samp, на входе I, выводит равномерно распределенный 
элемент DI .
3. Детерминированный алгоритм оценки f , на входе I и x  DI , выводит эле-
мент y  RI . Мы записываем это как y := fI (x).
Π – это семейство перестановок, если для каждого значения I выхода Gen(1n), 
считается, что DI = RI и функция fI : DI → DI является взаимно однозначным 
соответствием.
Пусть Π будет семейством функций. То, что отсюда следует – это естествен-
ная аналогия эксперимента, введенного ранее.


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




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

    Басты бет