Разработка псевдослучайной функции повышенной эффективности на основе конструкции расширенного каскада
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
псевдослучайной функции Наора-Рейнголда с помощью расширенного каскада
Лежащая в основе каскада ПСФ определяется следующим образом. Пусть ? - группа простого порядка p и - функция вида
.(3.10)
Введение f в расширенный каскад приводит к образованию функции Наора-Рейнголда , определяемой как
.(3.11)
В работе [58] Наор и Рейнголд доказали стойкость своей ПСФ при существовании DDH предположения в группе ?. Бонех, Монтгомери и Рагунатан подтвердили стойкость функции Наора-Рейнголда [47] путем доказательства q-параллельной стойкости функции f, описанной в (3.10), для любого полинома q в параметре стойкости (параметре безопасности, security parameter) при экспоненциальной сложности (вычислительной неразрешимости) DDH проблемы в группе ?.
Сложность вычисления данной ПСФ составляет n-1 умножений плюс одно финальное возведение в степень.
3.5.2 Построение псевдослучайной функции Бонеха, Монтгомери и Рагунатана на основе псевдослучайной функции Додиса-Ямпольского
Бонех, Монтгомери и Рагунатан построили более эффективную ПСФ, взяв в качестве базовой функции для расширенного каскада ПСФ Додиса-Ямпольского (FDY), описанную авторами в [53], которая имеет область определения размера ? для некоторого небольшого значения ?.
Стойкость FDY доказана при существовании ?-DDH предположении. Напомним, что мы [?] означает набор элементов . Функция Додиса-Ямпольского имеет вид и описывается следующим образом:
.(3.12)
Как определялось ранее, значение . Евгений Додис (Yevgeniy Dodis) и Александр Ямпольский (Aleksandr Yampolskiy) стойкость своей функции доказали в следующей теореме.
Теорема 4. Если ?-DDH предположение выполняется в G, тогда функция Додиса-Ямпольского FDY , определенная в (3.11), является стойкой ПСФ с областью определения ? в качестве полинома в параметре безопасности.
Путем введения функции Додиса-Ямпольского FDY в расширенный каскад Бонех, Монтгомери и Рагунатан получили еще более эффективную ПСФ FBMR, имеющую экспоненциальный размер области определения . Итоговая ПСФ FBMR определяется следующим образом:
.(3.13)
В соответствии с теорией сложности данная функция обрабатывает бит за один блок, в то время как функция Наора-Рейнголда - только один бит за один блок. Стоимость повышения эффективности выражается в использовании более строгого предположения, а именно ?-DDH предположения, описанного раннее. Бонех, Монтгомери и Рагунатан доказали следующую теорему.
Теорема 5. ПСФ, описанная в (3.12), является стойкой при условии выполнения ?-DDH предположения в ?.
Сложность вычисления данной ПСФ определяется n сложениями плюс п-1 умножениями, финальным одним инвертированием и экспоненцированием по модулю. На сегодняшний день это наиболее быстродействующая ПСФ из числа тех, чья стойкость основывается на теоретико-числовом предположении.
3.6 Разработка псевдослучайной функции с экспоненциальной областью определения и доказательство её стойкости
Создание новой эффективной ПСФ аналогично описанному создателями расширенного каскада в [47] алгоритму: первоначально необходимо выбрать ПСФ с малой областью определения, которая ляжет в основу, а затем расширить ее область определения на основе конструкции расширенного каскада. Стойкость новой функции определяется утверждением (теорема 3) о том, что достаточным условием стойкости расширенного каскада является удовлетворение лежащей в его основе функции свойству параллельной стойкости. Для проверки соответствия этому свойству строится функция (3.8) и доказывается ее стойкость.
Если ? - группа простого порядка p, тогда исходная функция представляет отображение , где - ключевое пространство, - область определения и ? - область значения, и определяется как
.(3.14)
Введение функции (3.14) в конструкцию расширенного каскада позволяет получить ПСФ с экспоненциальной областью определения следующего вида:
.(3.15)
Если сравнить получившуюся конструкцию с ПСФ Наора-Рейнголда, то единственным отличием от нее является повышенный размер области определения, какую цель мы и преследовали.
Следующая теорема ограничивает стойкость новой ПСФ путем сведения задачи взлома ПСФ к решению одной из существующих тяжелоразрешимых теоретико-сложностных проблем.
Теорема 4. ПСФ, определенная в (3.15), является стойкой при условии неразрешимости ?-DDH проблемы в группе ?.
Согласно теореме 2, для доказательства стойкости новой ПСФ достаточно доказать то, что лежащая в основе расширенного каскада функция, определенная в (3.14), удовлетворяет свойству q-параллельной стойкости. Для этого необходимо определить функцию , эмулирующую q копий функции (3.14) и доказать ее стойкость.
Пусть функция определяется как
,(3.16)
где . Докажем, что она является стойкой ПСФ для всех полиномиальных значений q.
Лемма 5. Если функция f, определяемая как (3.14), является стойкой ПСФ и проблема DDH является тяжелоразрешимой в ?, то функция f является q-параллельно стойкой для любого полинома q в параметре безопасности.
В частности, для каждого атакующего ПСФ алгоритма ?, существуют такие атакующие алгоритмы ?1 и ?2, имеющие время выполнения приблизительно равное времени выполнения ? вплоть до полиномиального множителя, что
(3.17)
Так как предположение о сложности решения k-DDH проблемы подразумевает сложность решения DDH проблемы (при k=1 k-DDH предположение является просто DDH предположением), необходимость в допо