Разработка псевдослучайной функции повышенной эффективности на основе конструкции расширенного каскада
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
?ложили схему короткой электронно-цифровой подписи (signature) [BB04c], основанной на q-сложной проблеме Диффи-Хеллмана, по сути являющейся аналогом рассматриваемой. Это предположение использовалось также в [BB04a, DY05] под названием k-обратного предположения Диффи-Хеллмана (k-DHI). Кроме перечисленных работ, существуют многочисленные протоколы на основе проблемах, подобных q-слабой проблеме Диффи-Хелмана, в том числе и [BB04b, BBG06].
Ясно, что 1-DDH () предположение подразумевает стандартное DDH предположение. Более того, для k-DDH предположение подразумевает существование также ?-DDH предположения при ?< k.
Полезная лемма. Далее нам понадобится следующая лемма из [52] (Лемма 1). Пусть - набор матриц размерности над и пусть Rk1() - набор матриц ранга 1. Как известно, матрица, имеющая ранг 1, имеет только одну независимую строку или столбец.
Пусть ? - группа простого порядка p с генератором g. Пусть матрицы A0 и A1 равномерно распределены на множествах Rk1() и соответственно. Для алгоритма определяем преимущество атакующего алгоритма ?, отличающего A0 от A1 как
.(3.6)
Следующая лемма демонстрирует, что если решение DDH сложно в ?, то не существует эффективных алгоритмов, способных отличить матрицу ранга 1, представленной в экспоненциальной форме, от матрицы со случайными значениями, представленной также в экспоненциальном виде.
Лемма 1. Для любого алгоритма ? существует такой атакующий DDH алгоритм ?, выполнение которого занимает примерно такое же время, как и ?, что
(3.7)
3.4 Построение конструкции классического каскада на основе классического решения
Как уже упоминалось, мы будем использовать конструкцию расширенного каскада из [47] для доказательства стойкости разработанной нами функцию. Также нам понадобится теорема из [BCK96b].
Каскадная ПСФ. Каскадная ПСФ, описание которой дается в [BCK96b], дает возможность построить стойкую ПСФ с областью определения Xn из стойкой ПСФ с областью определения X. Конструкция каскада представлена на рисунке 3.2a. Для более формального описания представим некоторую стойкую ПСФ в виде . Каскад этой функции F обозначается как и определяется работой следующего алгоритма:
ВВОД ключ , начальная последовательность
ЦИКЛ ДЛЯ i ОТ 1 ДО n [ШАГ 1]
КЦ
ВЫВОД kn.
Каскад является генерализацией GGM схемы конструирования ПСФ из псевдослучайного генератора, описанной Годрайхом, Голдвассером и Микали в [54]. Его можно рассматривать в качестве метода конвертирования ПСФ с однобитным доменом в ПСФ с n-битной областью определения. Стойкость конструкции каскада доказывается в [BCK96b] в следующей теореме.
Теорема 2. Для каждого атакующего каскад алгоритма ?, осуществляющего q запросов, существует такой алгоритм ?, атакующий F и осуществляющий также q запросов в ходе атаки, что преимущество
,(3.8)
где ? имеет приблизительно такое же время выполнения, что и ?.
ПСФ на основе расширенного каскада. Расширенный каскад определяется как функция вида
(3.9)
Областью определения расширенной функции является Xn, ключ представляет собой строку вида . Конструкция расширенного каскада представлена на рисунке 3.2б и его функционирование определяется следующим алгоритмом:
ВВОД ключевая последовательность , начальная последовательность
ЦИКЛ ДЛЯ i ОТ 1 ДО n [ШАГ 1]
КЦ
ВЫВОД kn.
Рисунок 3.2 - Классическая каскадная конструкция с ключом k (a) и конструкция расширенного каскада с ключом (б)
К сожалению, стойкость расширенного каскада совершенно не определяется стойкостью лежащей в его основе ПСФ. Теорема 3 утверждает, что расширенный каскад является ПСФ только в том случае, если лежащая в его основе ПСФ удовлетворяет условию, называемому параллельной стойкостью. Данное свойство заключается в том, что функция F продолжает оставаться стойкой при доступе противника (атакующего алгоритма) к многочисленным экземплярам функции с различными, но связанными ключами.
Для функции и целого числа q > 0 определим q связанных ключей с одним и тем же s где и . Функция F называется q-параллельно стойкой, если результирующий набор из q функций не отличим от q случайных независимых функций.
Представим отображением вида , определяемым как
,(3.8)
где и определяет пару ключей , используемой функцией F. Таким образом, эмулирует q копий функции F с ключами для .
Определение 3. ПСФ является q-параллельно стойкой ПСФ, если является стойкой ПСФ.
Отметим отдельно немаловажный факт: функция F может не быть q-параллельно стойкой даже в том случае, если она является стойкой ПСФ.
Теорема 3. Если функция F является q-параллельно стойкой, то расширенный каскад является стойкой ПСФ по отношению к атакующему q запросами алгоритму.
В частности, для каждого алгоритма ?, атакующего расширенный каскад и выполняющего q запросов к нему в ходе атаки, существует такой противник ?, атакующий функцию и выполняющий q запросов к ней в ходе атаки, что
,(3.9)
где ? выполняется приблизительно такое же время, что и ?.
.5 Применение конструкции расширенного каскада для построения псевдослучайных функций повышенной эффективности
Бонех (Dan Boneh), Монтгомери (Hart Montgomery) и Рагунатан (Ananth Raghunathan) в работе [47] продемонстрировали возможность использования расширенного каскада для проектирования новых ПСФ с большой областью определения из ПСФ с малой областью определения.
.5.1 Реализация