Разработка псевдослучайной функции повышенной эффективности на основе конструкции расширенного каскада
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
Вµская стойкость базируется на узкоспециальных интерактивных предположениях. Их недостаток заключается в том, что противник может осуществлять адаптивные, наиболее эффективные разновидности атак.
3.2 Постановка проблемы и обоснование выбранного решения
В 1996 Мони Наором (Moni Naor) и Омером Рейнголдом (Omer Reingold) [58] была представлена ПСФ, стойкость которой была выведена из сложности решения проблемы принятия решения Диффи-Хеллмана (DDH). ПСФ Наора-Рейнголда определяется следующим образом: на ее вход поступают m-битная строка и секретный ключ , результатом работы является
(3.1)
Вычислительная сложность этой функции составляет m-1 модулярных умножений для вычисления w и одно заключительное возведение в степень.
Алгебраическая конструкция ПСФ Наора-Рейнголда лежит в основе многих криптографических схем и даже таких алгебраических конструкций, как верифицируемые случайные функции (VRFs), рассеянные и распределенные ПСФ.
В 2010 году Дан Бонех, Харт Монтгомери и Анан Рагунатан представили в [47] конструкцию расширенного каскада и на его основе построили эффективную ПСФ, основанную на ПСФ Додиса-Ямпольского, а так же доказали ее стойкость.
Нами была разработана алгебраическая ПСФ, имеющая точно такой же размер области определения, как ПСФ Наора-Рейнголда и Бонеха-Монтгомери-Рагунатана (БМР ПСФ), но использующая более короткий секретный ключ по сравнению с ПСФ Наора-Рейнголда. Для некоторых параметров ? и n ПСФ на вход принимает входную последовательность вместе с ключом и на выход выдаёт
где (3.2)
Для области определения размером 2m значение , в следствие чего при вычислении данной функции требуется в раз меньше умножений, но на больше возведений в степень по сравнению с (3.1) для вычисления значения w. В общей сумме нам необходимо умножений для вычисления значения w. Основным преимуществом данной ПСФ является использование меньшего объема памяти для вычисления значения функция, так как она использует ключ в раз меньший размером по сравнения с ПСФ Наора-Рейнголда. Стойкость ПСФ основывается на предположении о сложности решения ?-DDH проблемы. Взаимосвязь между стойкостью функции и значением ? следующая: чем больше ?, тем более строгим становится это предположение, и тем менее стойкой становится функция. Таким образом, необходимо выдерживать небольшое значение ?. В качестве примера можно привести значения ??= 16 или 256 как достаточно разумные.
Для доказательства стойкости получившейся ПСФ предлагается использование определенной в [47] конструкции расширенного каскада, позволяющего конструировать ПСФ с большой областью определения из ПСФ с малой областью определения. Его структура является модификацией классического каскада (рисунок 3.2а), представленного Беллари, Каннети и Кравчуком в [46], и изображена на рисунке 3.2б. Конструкция классического каскада имеет один существенный недостаток: размерность выходного значения лежащий в его основе ПСФ должна быть не менее длины секретного ключа. Расширенный каскад этого требования лишен.
Интересным свойством рассматриваемого расширенного каскада является отсутствие взаимосвязи между его стойкостью и стойкостью лежащей в его основе ПСФ. Бонех, Монтгомери и Рагунатан в [47] сформулировали достаточное условие лежащей в основе ПСФ, называемое параллельной стойкостью, существование которого обеспечивает стойкость расширенного каскада.
С использованием теоремы о стойкости расширенного каскада была построение новая ПСФ с большой областью определения введением в расширенней каскад ПСФ в малой областью определения. Исходная функция получает в качестве входных данных m-битную строку и секретный ключ и выдает значение
(3.3)
Для доказательства стойкости получившейся функции мы доказываем, что исходная ПСФ (3.3) обладает свойством параллельной стойкости.
3.3 Обоснование и использование теоретико-сложностных предположений
Далее под ? будет пониматься циклическая группа (то есть группа простого порядка p с генератором (generator, порождающим элементом) g). Таким образом, . Тогда для векторов и определим операцию возведения в степень как . Возведение скаляра в степень, представленную вектором, определим как . Для матрицы и вектора также определим
где для (3.4)
и для скаляра .
Кроме того, запись [k] обозначает набор значений .
k-DDH предположение. Для обозначим как вектор вида . k-DDH (k-decisional Difffie-Hellman assumption) предположение гласит о том, что обратный элемент неотличим от выбранного случайно элемента из группы . Под неотличимостью в данном случае понимается отсутствие эффективного алгоритма решения указанной проблемы. Более точно, для алгоритма определим преимущество
(3.5)
где , h равномерно распределены на множестве ? и x равномерно распределено на . В случае, если x = 0 мы считаем элемент равным 1 в группе ?.
Определение 2. Для говорят, что k-DDH предположение выполняется в группе ? (или проблема k-DDH трудноразрешима в ?), если для всех эффективных алгоритмов ? преимущество пренебрежительно мало.
Вычислительный вариант этого предположения имеет название ?-слабой проблемы Диффи-Хеллмана (?-wDH) и впервые был введен Мицунари (Shigeo Mitsunari), Сакаи (Ryuichi Sakai) и Касахара (Masao Kasahara) в схеме обнаружения внутренних нарушителей (a traitor tracing scheme) в [57] и звучит следующим образом: для данных g и , принадлежащих группе ?, при трудно вычислить значение . В 2004 году Бонех (Dan Boneh) и Боен (Xavier Boyen) пре