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