Разработка псевдослучайной функции повышенной эффективности на основе конструкции расширенного каскада
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
ли . Затем алгоритм ? к t случайным элементам присоединяет полученную от своего запросчика строку и отправляет результирующую последовательность атакующему алгоритму ?. Наконец, атакующий алгоритм ? выдает бит своему запросчику (то есть алгоритму ?), который свидетельствует о его решении по поводу принятой им последовательности. Атакующий алгоритм ?, в завершение всего гибридного эксперимента, просто пересылает тот же самый бит своему запросчика в качестве ответа на то, случайной или ?-DDH стройкой была принятая им последовательность.
В случае если ?-DDH запросчик алгоритма ? выбирает элемент , выдаваемая им строка является случайной, и таким образом алгоритм ? эмулирует эксперимент Expt+1 между ПСГ запросчиком и атакующим его алгоритмом ?.
В случае если ?-DDH запросчик алгоритма ?s выбирает элемент , выдаваемая им строка представляет собой ?-DDH?строку, и таким образом алгоритм ? эмулирует эксперимент Expt между запросчиком и атакующим его ?.
Таким образом, мы можем говорить о том, что различение выходной последовательности ПСГ от последовательности случайных чисел сводится к решению ?-DDH проблемы и поэтому может считаться вычислимо неразрешимой задачей. Как и требуется, равенство (3.18) выполняется, что завершает доказательство леммы 6.
Доказательство леммы 5. Наша цель - продемонстрировать явным образом, что функция , определенная в (3.21), является стойкой ПСФ. Для этого предлагается использовать описанную Бонехом, Монтгомери и Рагунатаном в [47] схему доказательства.
Доказательство стойкости представляется в виде последовательности трех игр между запросчиком и атакующим функцию алгоритмом ?. Для обозначение Wi определяет вероятность выигрыша атакующего алгоритма ?, то есть вероятность того, что бит b в игре Game i угадан алгоритмом правильно .
Game 0. В этой игре запросчик играет роль обычного запросчика для функции , предоставляя атакующему алгоритму ? доступ к оракулу функции , используемому случайный ключ (рисунок 3.5).
Рисунок 3.5 - Схема взаимодействия атакующего алгоритма ? с -??запросчиком в игре Game 0
Game 1. В данном случае запросчик выбирает случайную функцию вида и случайным образом генерирует значения . Затем на запрос от атакующего алгоритма возвращает вычисленное значение (рисунок 3.6).
Рисунок 3.6 - Схема взаимодействия атакующего алгоритма ? с -?запросчиком в игре Game 1
Мы утверждаем, что игры 0 и 1 неотличимы друг от друга в том случае, если функция f - стойкая ПСФ. В частности, существует такой атакующий алгоритм ?1, время выполнения которого приблизительно равно времени выполнения атакующего алгоритма ?, что
.(3.26)
Атакующий алгоритм ?1 взаимодействует с запросчиком, предоставляющим доступ к оракулу функции f либо оракулу случайной функции с одной стороны, а с другой - сам играет роль запросчика для атакующего алгоритма ?, предоставляя доступ к оракулу функции либо случайному оракулу.
Атакующий алгоритм ?1 работает описанным ниже образом. На этапе инициализации случайным образом выбираются значения . После этого атакующий алгоритм ?1 готов обрабатывать запросы алгоритма ? в качестве запросчика и переходит в режим ожидания. Каждый раз, получая запрос от атакующего алгоритма ? вида , атакующий алгоритм ?1 обращается к своему запросчику с вопросом x , на что последний возвращает некоторое значение y. Затем атакующий алгоритм ?1 вычисляет значение и отправляет результат в качестве ответа на запрос атакующему алгоритму ?. После выполнения алгоритмом ? q-запросов он принимает решение о том, с оракулом какой функции он имел дело, и в соответствии с этим выдает атакующему алгоритму ?1 выходной бит b. Игра завершается пересылкой принятого алгоритмом ?1 бита своему запросчику в качестве решения о том, ответы какого оракула атакующий алгоритм ?1 получал.
Когда запросчик атакующего алгоритма ?1 эмулирует доступ к оракулу функции f со случайным образом выбранным ключом (s, h), то он на запрос x атакующего алгоритма ?1 отвечает результатом вычисления значения ПСФ . Если для определить , то можно считать, что атакующий алгоритм ? на запрос алгоритма ? выдает значение , которое как раз является результатом вычисления псевдослучайной функции. which is precisely . Следовательно, в этом случае атакующий алгоритм ?1 эмулирует игру Game 0 запросчика с атакующим алгоритмом ?.
Когда запросчик атакующего алгоритма ?1 эмулирует доступ к случайному оракулу, то есть к случайной функции вида , то ответом запросчика атакующего алгоритма ? (то есть ответом атакующего алгоритма ?1) на запрос атакующего алгоритма ? является просто некоторое значение , которое полностью совпадает с выданным бы запросчиком в игре Game 1.
Таким образом, два вышеприведенных аргумента полностью доказывают утверждение (3.24).
Game 2. Запросчик предоставляет атакующему алгоритму ? доступ к случайному оракулу, то есть оракулу случайной функции .
Рисунок 3.7 - Схема взаимодействия атакующего алгоритма ? с -??запросчиком в игре Game 3
Свидетельством неразличимости игр Game 1 и Game 2 при условии тяжелоразрешимости проблемы DDH для группы ? может служить лемма 1. Применительно к нашему случаю, в частности, существует такой атакующий DDH проблему алгоритм ?2, что
.(3.27)
Пусть - запросы атакующего алгоритма ? к своему запросчику. Как уже было сказано, в игре Game 1 запросчик отвечает на запросы атакующего алгоритма ? с использованием случайной функции с выбранным