Разработка псевдослучайной функции повышенной эффективности на основе конструкции расширенного каскада
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
лнительном доказательстве сложности решения DDH проблемы в ? отпадает.
Таким образом, стойкость новой ПСФ зависит от выполнения двух условий: стойкости лежащей в основе каскада функции и трудноразрешимости проблемы DDH в ?. Следующая лемма ограничивает условия стойкости ПСФ f, определенной в (3.14).
Лемма 6. Если ?-DDH проблема является трудноразрешимой для группы ?, то функция f, определенная в (3.14), является стойкой ПСФ с полиномиальным размером области определения ? в качестве параметра безопасности.
В частности, для каждого алгоритма ?, атакующего ПСФ, существует такой атакующий алгоритм ? с приблизительно таким же временем выполнения, что и ? вплоть до полиномиального множителя, что
.(3.18)
Доказательство. Для того, чтобы доказать стойкость функции f, определенной в (3.14), достаточно продемонстрировать, что ? выходных значений этой функции f представляют собой выходную последовательность криптографически сильного (стойкого) псевдослучайного генератора (PRG, ПСГ). Таким образом, доказательство стойкости ПСФ сводится к доказательству того, что выходная последовательность
.(3.19)
является выходной последовательности криптографически стойкого ПСГ при условии существования ?-DDH предположения в ?.
Для определения псевдослучайного генератора необходимо ввести понятие вычислительной неразличимости двух распределений. Формально, два распределения ?1, ?2 называются вычислительно неразличимыми, если для любого полиномиального вероятностного алгоритма ?
.(3.20)
Неформально мы можем представить задачу следующим образом. Пусть X и Y - такие множества, что по выбранному случайным образом элементу возможно с помощью некой специальной функции G(x) породить якобы случайный элемент из Y. Будем рассматривать только случаи с мощностью множества Y намного большей мощности множества X, т.е. , иначе задача существенно упрощается. Например, рассмотрим случай, когда X = {0...1000}, Y = {0...100}. Тогда, выбрав случайный , можно легко вычислить y = x div 10, который, очевидно, будет принадлежать Y и будет случайным в силу случайности выбора x.
В случае функция G : X > Y называется псевдослучайным генератором, если и вычислительно неразличимы ( - равномерные распределения)
Напомним, что ?-DDH строка имеет вид . Если рассматривать , то отсюда обратный элемент и =. Другими словами, выходная последовательность ПСГ является представленной в ином виде ?-DDH строкой.
Лемма 7. Если ?-DDH предположение существует для группы ?, то элемент является неотличимым от случайно выбранного элемента . Более точно, для алгоритма преимущество
,(3.21)
где , .
Для доказательства леммы 7 нами использовалась часто используемая техника, называемая гибридным аргументом.
Используется следующая последовательность ?+1 гибридных экспериментов между запросчиком и атакующим алгоритмом ?. Пусть ??- алгоритм, умеющий различать псевдослучайную последовательность, выработанную ПСГ G от случайной входной последовательности, от настоящей случайной последовательности. В гибридном эксперименте i запросчик заменяет первые i выходных элемента ПСГ настоящими случайными числами, в то время как последние ?-i элементов являются выработанными ПСГ.
Более точно, при поведение запросчика в гибридном эксперименте Expi определяется следующим алгоритмом:
ВВОД: ключи и
ВЫВОД:
ЕСЛИ ТО
ЦИКЛ ДЛЯ j ОТ 1 ДО n [ШАГ 1]:
КЦ
ИНАЧЕ
ЦИКЛ ДЛЯ j ОТ i+1 ДО ? [ШАГ 1]:
КЦ.
Для определим Wi как вероятность совпадения битов b и , то есть правильного распознавания алгоритмом ? последовательности в гибридном эксперименте i. Следует отметить, что в гибридном эксперименте Exp0 противник ? получает для анализа псевдослучайную последовательность, выданную ПСГ, в то время как в гибридном эксперименте Exp? противник получает не что иное, как совершенно случайную последовательность. Отсюда
.(3.22)
Из техники гибридного аргумента следует, что существует такое значение , что
.3.23)
Другими словами, в гибридных экспериментах Expt и Expt+1 получаемые противником последовательности вычислительно неразличимы:
(3.24)
Для сведения решения проблемы различения абсолютно случайной и псевдослучайной последовательностей к теоретико-сложностному предположению мы конструируем такого атакующего алгоритма ?, умеющего решать ?-DDH проблему, что
.(3.25)
Комбинирование (3.24) и (3.25) доказывает Лемму 6.
В гибридных экспериментах Expt и Expt+1 атакующий алгоритм ?, с одной стороны, взаимодействует с ?-DDH?запросчиком, а с другой стороны, параллельно эмулирует запросчика ПСГ для атакующего алгоритма ?. Общая схема взаимодействия всех объектов в гибридных экспериментах Expt и Expt+1 отражена на рисунке 3.4.
Рисунок 3.4 - Схема взаимодействия атакующего алгоритма ? с ?-DDH?запросчиком и атакующим алгоритмом ? в гибридных экспериментах Expt and Expt+1
На этапе инициализации ?-DDH?запросчик выбирает случайным образом и бит . В случае, если , запросчик выдает алгоритму ? ?-DDH строку , а если , то запросчик выдают последовательность случайных элементов .
Атакующий алгоритм ? осуществляет свои действия в следующем порядке. На этапе инициализации случайным образом выбираются элементы . Затем алгоритм ? получает от своего ?-DDH запросчика некоторую последовательность , где может быть (то есть y - случайно выбранный элемент из множества ?) и