Полу обобщённая групповая модель и приложения для криптографии основанной на использовании парных значений

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 06:39, 24 декабря 2015.
The Semi-Generic Group Model and Applications to Pairing-Based Cryptography
Towards a Game Theoretic View of Secure Computation.png
Авторы Tibor Jager [@: 1] ,
Andy Rupp [@: 2]
Опубликован 2011 г.
Перевели коллектив проекта «Gir»
Год перевода 2011 г.
Скачать Оригинал

__NUMBEREDHEADINGS__

Аннотация. В криптографии основанной на использовании парных значений часто используется Обобщённая Групповая модель (GGM) для доказательства более современных стойких предположений. К несчастью, GGM не отражает много известных свойств билинейного группового набора и т.о. значительно ограничивается стойкость такой модели. В данной работе мы предлагаем новую вычислительную модель для криптографии основанной на использовании парных значений, называемую полу обобщённая групповая модель (SGGM), которая более схожа со стандартной моделью и обеспечивает более лучшую гарантию безопасности. В действительности, наилучшим известным на текущее время алгоритмом решения задач с парными значениями будет полу обобщённый алгоритм. Мы продемонстрировали действенность нашей новой модели применив её для изучения некоторых важных предположений (BDDH, Co-DH). Более того, мы разработали основные теоремы реализующие простой анализ других (будущих) предположений. Эти теоремы реализуют (если нету алгоритма лучше полу обобщённого) большое число новых предположений над билинейными группами и сводятся всего к 2 (может больше или меньше) стандартным предположениям над конечными полями. В заключении, мы выявили соответствие SGGM как устройства анализа безопасности практической криптосистемы без случайных оракулов при помощи её применения в BLS схеме подписи.

Ключевые слова: ограниченные модели вычисления, обобщённые группы, полу обобщённая групповая модель, криптографические предположения, главные теоремы, доказуемая безопасность, криптография основанной на использовании парных значений.

Введение

Некоторые вычислительные задачи, в основном из алгебры, теории чисел, и теории кодирования, являются основными элементами криптографии с открытым ключом. Однако, доказать корректность этих предположений в стандартной модели вычисления скорее всего будет невозможно при помощи существующих методик.

Почему же мы пользуемся такими стойкими предположениями, при том, что они не доказуемы в общем случае? Для классических теоретико-числовых задач, таких как целочисленная факторизация IF или дискретный логарифм DL, это ограничено из-за отсутствия эффективных алгоритмов при том, что данный вопрос уже поднимался на обсуждение многими выдающимися личностями. Однако, благодаря таким хорошо известным предположениям, часто появляются новые предположения строящие базис для новой криптосистемы с оригинальными свойствами. Что можно сделать для получения доказательства данных предположений помимо нахождения соответствующих эффективных алгоритмов? Ясно, что нам необходимо попытаться основываться на новых предположениях при помощи поиска их сокращений к более реальным предположениям; но, к несчастью, нахождение таких сокращений зачастую ни к чему не приводит.

Важным подходом для выявления доказательства конкретной стойкости предположений является доказательство того, что они относятся к ограниченному, но всё же значимому классу алгоритмов. Это было мотивацией разработки моделей чёрного ящика для алгебраических структур, таких как группы, поля, и кольца, для которых алгоритмы ограничены только лишь выполнением операций над этими структурами. Вероятно, наиболее известным таким алгоритмом является обобщённая групповая модель GGM предложенная Соупом в работе [1] 1997, и пересмотренная Маууером в [2]. В данной модели рассматриваются алгоритмы – так называемые обобщённые групповые алгоритмы – которые, для заданной группы в качестве чёрного ящика, могут выполнить только определённый базовый набор операций для элементов таких, которые реализуемы по групповому закону, а также инверсию групповых элементов и проверку эквивалентности. Т.к. данная группа рассматривается как чёрный ящик, то алгоритмы нельзя разбить на определённые свойства конкретной группы представления. Последовательно, такие алгоритмы будут обобщёнными в том смысле, что их можно реализовать для любого конкретного примера группы за тем, чтобы решить задачу. Действительные примеры такого класса алгоритмов представлены алгоритмами Полига-Хеллмана [3] и Полларда Рхо [4] для вычисления дискретных логарифмов.

Следует отметить, что необходимо принять во внимание соответствующий результат в GGM свидетельствующий об сложности практической реализации доказательства, т.к. эта модель абстрагирована от многих потенциальных свойств алгоритма разделяемого в действительном примере [5]. С другой стороны, существуют криптографические группы (такие как группы некоторых эллиптических кривых) для которых известно не так много свойств согласно аксиоме алгебраической группы. Следовательно построение таких групп как общих можно рассматривать как возможную абстракцию. С другой стороны, есть группы, также использующиеся в криптографии, обладающие некоторыми новыми свойствами, которые понятное дело реализуют обобщённую модель не подходящим образом. Одним из простых примеров могут служить мультипликативные группы конечных полей или колец. Такие структуры имеют много понятных свойств согласно групповой аксиоме, таких как добавочные эффективные алгебраические операции (например, добавление в поле или кольцо), и другие свойства группового представления (например, понятие простых целых и неприводимых полиномов), которые просто игнорируются обобщённой групповой моделью, но позволяют использовать более эффективные алгоритмы для некоторых задач (например, алгоритмы исчисления индексного значения для вычисления дискретных логарифмов).

Но должно ли минимальное требование к такой идеализированной модели вычисления включать в себя рассмотрение всех известных возможных алгоритмов? Для ответа на это вопрос воспользуемся несколькими первичными подходами в криптографической литературе: псевдо свободная групповая модель предложенная Хохенбергером [6] и Ривестом [7] не рассматривает группу как чёрный ящик. К сожалению, определение псевдо-свободы очень ограничено для определённого количества важных групп (таких как группы с известным порядком), которыми исключаются некоторые задачи такие, как задача типа-Диффи-Хеллмана. Другие подходы Ландера и Паппа [8], а также Агарвала Мауера [1] принимают во внимание то, что RSA группа включена в кольцо . Они используют общую модель кольца, в которой алгоритмы могут выполнять как операции умножения так и сложения при для выявления того, что взлом RSA эквивалентен факторизации. К сожалению, недавняя работа [9] показала, что даже вычисление Якобиана эквивалентно факторизации в данной модели. Т.о. данный подход не приведёт к необходимой абстракции .

За последнюю декаду было предложено значительное количество криптосистем над билинейными группами таких, как шифрование основанное на идентификации [10] или короткая цифровая подпись со стойкой безопасностью [11] [12]. Набор билинейной группы состоит из групп , и с билинейным отображением , которое называется получение парного значения. Для данных криптосистем было предложено много новых предположений, например, Билинейное предположение Диффи-Хеллмана BDH [13] [14], q-стойкое предположение Диффи-Хеллмана [15][16][17], предположение Диффи-Хеллмана о линейном решении DLIN [18], предположение Со-Диффи-Хеллмана Со-DH [19][11], и многие другие. К несчастью, показано, что ни одно из них нельзя свести к хорошо известному DL. Действительно, нахождение такого сведения является сложной задачей, т.к. алгебраический набор соответствующих классических задач (например, простая циклическая группа для DL) значительно отличается от билинейного набора. Из этого следует, что для данного примера классической задачи сложно найти аналог преобразования её в билинейную задачу.

Следовательно, единственным способом выявить какое-нибудь существенное доказательство для таких новых предположений будет доказательство упрощённых моделей вычисления. Т.к. только такие модели для билинейного набора будут соответствующим расширением обобщённой групповой модели, где все три группы , и будут смоделированы как обобщённые группы [20][21][22]. Во всех известных случаях билинейные наборы групп , являются группами эллиптических кривых, т.о. моделирование этих групп в обобщённом виде можно рассматирвать как приемлемую абстракцию. Однако, в этом же случае, группа будет подгруппой мультипликативной группы конечного поля. Т.к. определённо существуют не обобщённые алгоритмы для криптографических задач таких как BDH, Co-DH, и т.д. ограниченность по времени будет максимально субэкспоненциальной: и данные субэкспоненциальные алгоритмы отображают входы , (заданные как часть конкретной задачи) и используя билинейное отображение (MOV [23]) и определяют дискретные логарифмы этих элементов над используя индексное исчисление. Знание данных дискретных логарифмов позволяет вычислить решение конкретной задачи при помощи нескольких возведений в степень. Отметим, что должны существовать и более эффективные алгоритмы в особенности для потенциально простых задач, таких как выборка или определение интервала. Следовательно, моделирование билинейного набора таким образом явно не корректно.

Наш вклад. Мы предлагаем ввашему вниманию полу обобщённую Групповую Модель (SGGM) которая использует данную методику следующим образом: группы эллиптических кривых , моделируются как обобщённые группы, тогда как задаётся в стандартной модели, т.е. алгоритмы могут выполнять либое вычисление над , которое возможно в подгруппе конечного поля. SGGM т.о. будет приближённее к стандартной модели, чем GGM и может обеспечивать более лучшее доказательство для стойкости предположений в криптографии основанной на использовании парных значений. В действительности, насколько нам известно все алгоритмы на текущий момент решающие задачу парного распределения являются по совей сути полу обобщёнными. В частности, субэкспоненциальные алгоритмы применяющие MOV сокращение описанные выше покрываются SGGM.

Мы проанализировали некоторые из наиболее значимых вычислительных и решающих предположений криптографии основанной на использовании парных значений для нашей новой модели. Для данного предложенного случая мы ограничились рассмотрением Со-DH и решающего BDH. В полной версии данной работы показаны дополнительные задачи, включая q-стойкую DH и DLIN. Нам также необходимо сократить рассматриваемые предположения (касательно полу обобщённых алгоритмов) для получения стандартных предположений над конечными полями, таких как Square DH и уменьшенная версия DL. Это означает, что билинейные предположения будут такими же стойкими как некоторые более стандартное предположения над показывающие что полу обобщённых алгоритмов не существует. Более того, мы разработали основные теоремы доказывающие стойкость широкого класса вычислительных и решающих задач в SGGM. Изучение таких обобщений не только необходимо для того, чтобы структурировать и содействовать анализу быстро растущего набора криптографических предположений, как это показано в [24], но и для улучшения нашего понимания свойств, которые необходимо получить с помощью реализации задачи. Соответствующий результат показан в [25][20][21]. Боен [21] (см. также [26]) разработал основные теоремы для стойкости некоторых общих классов решающих задач в обобщённой групповой модели для билинейного набора. Рапп и др. [20] представил условия для стойкости более широкого класса вычислительных задач и алгебраического набора, но всё ещё для GGM. Брессон и др. [25] изучил общий класс решающих предположений над простой группой в стандартной модели и показал, что этот класс можно сократить до DDH (при некоторых допущениях). В рамках доказательства нашей основной теоремы для решающих задач мы используем результаты Брессона и др. для стандартной модели и применяем их для SGGM.

Безопасность криптосистем с открытым ключом, в особенности, практических криптосистем, можно зачастую доказать в идеализированной модели, такой как модель случайного оракула (ROM) [27]. Значение ROM заключается в том, что он идеализирует хэш функцию таким способом, чтобы все свойства «идеальной» хэш функции (стойкость к коллизии, стойкость получения (второго) прообраза, случайные выходные значения, …) выполнялись одновременно. Когда криптосистема (и т.о. случайный оракул) реализуется на практике, любой может выбрать соответствующую хэш функцию определяющую случайный оракул. Важный вопрос заключается в том, необходимо ли определять все свойства случайного оракула одновременно для достижение требуемой безопасности.

Мы исследовали возможность использования SGGM в качестве дополнения к ROM. Мы смогли доказать безопасность схемы короткой подписи Бонеха-Лина-Шачама (BLS) [11][12] для полу обобщённых злоумышленников без случайных оракулов, однако, это потребовало наличие нестандартных свойств для реализации хэш функции. Вопрос о том, можно ли в данном случае обойтись эффективной практической хэш функцией, остаётся открытым.

Полу обобщённая групповая модель

Пусть , и будут группами простого порядка и будут соответствующими генераторами. Для упрощения последующей формализации воспользуемся определением для всех групп.

Определение 1. Получение парного значения есть отображение со следующими свойствами:

1. Билинейность: и выполняется

2. Невырожденность: есть генератор , т.е .

3. эффективно вычислимо.

Следуя [28], мы выделяем по признакам три различных типа набора билинейной группы:

  • Тип 1: . Назовём это установкой с симметрическим билинейным отображением.
  • Тип 1: , существует эффективно вычислимый изоморфизм .
  • Тип 3: , существует не эффективно вычислимый изоморфизм .


Общее определение для SGGM. Мы основываем наше общее определение SGGM для линейного набора на обобщённой групповой модели предложенной Мауером [2], хотя наши доказательства можно реализовать и с помощью GGM Соупа [1]. Основным отличием между формализациями Мауера и Соупа будет то, что в первом случае групповые элементы модели кодируются детерминистически, тогда как во втором – случайным образом.

Алгоритм А в SGGM работает с полу обобщённым групповым оракулом О, который вычисляет групповые операции и оценивает парные значения и изоморфизм части А. О получает на вход два вектора группы элементов (пример задачи)

и


В общем случае, оба и с определяют j-ый вход , который инициализирован так, что для всех возможных . Обозначим за наименьший индекс (также называемый кодированием) такой, что . Индекс будет не определён, если . Можно всегда предположить, что полу обобщённые алгоритмы реализуют только определённые индексы выходных значений для оракула. В процессе инициализации , соответствующие индексы относительно содержащихся элементов отсылаются алгоритму.

Данный оракул реализует следующие открытые процедуры, которые можно назвать А:

  • Эта процедура получает на входе два индекса и индекс списка . Она определяет групповые элементы с помощью просмотра списка, и вычисляет , добавляет в и возвращает .
  • Эта процедура получает на входе два индекса . Она определяет соответствующие групповые элементы с помощью просмотра списка и возвращает в стандартном представлении (т.е., как конечное поле элемента).

Когда рассматривается набор Типа 2 алгоритм также старается реализовать изоморфизм для элемента :

  • Эта процедура получает на входе индекс , определяет элемент , вычисляет , добавляет к и возвращает .

Отметим, что случайный групповой элемент можно эффективно получить с помощью полу обобщённого алгоритма для расширения генератора (который всегда является частью примера задачи) до .

Основные элементы доказательств в SGGM

В данном разделе описывается несколько общих наблюдений, которые являются основными для доказательств полу обобщённой модели.

Наблюдение 1: Составные части оракула взаимозаменяемы. Полу обобщённые алгоритмы по своей сути не получают информации касательно начальных значений для групп также как и парные и изоморфизм . Данные компоненты сокрыты чёрным ящиком. Следовательно, мы модем применить что-нибудь другое для этих компонентов т.к. любая их замена будет выглядеть как циклическая группа с билинейным отображением и изоморфизмом. Преобразуем это наблюдение в новый вид для отображения входов заданных над , и набором изначально и симуляцией виртуального билинейного отображения и изоморфизмом .


Наблюдение 2: Вычисляемые элементы над будут линейными полиномами для начальных входных значений. Пусть и будут входами заданными для полу обобщённого оракула (как части примера задачи). Получим в случае набора Типа 1. В дальнейшем, мы всегда полагаем, что задано не менее двух и генераторов. Т.о. можно записать и для некоторого неизвестного (здесь не делается никаких предположений о его распределении) и для случая набора Типа 2. Затем определяем кортеж и кортеж для случая с наборами Типа 1 и 3 либо для набора Типа 2. Эти кортежи называются начальными значениями на входе полу обобщённых алгоритмов. Используя данное определение, мы можем описать следующее наблюдение: над , полу обобщённый алгоритм может выполнять групповой закон только для входных значений. Т.о. любой элемент вычисляемый с помощью полу обобщённого алгоритма будет суммой элементов в . Следовательно, можно показать такой элемент, что для некоторого линейного многовариантного полинома , где будет нулём в случае или если мы рассматриваем набор Типа 1. Следует отметить, что все коэффициенты данного полинома известны оракулу.


Наблюдение 3: Парные значения являются одновременно известными изображениями начальных входов. Пусть и будут двумя элементами вычисляемыми с помощью полу обобщённого алгоритма. Тогда используя вышеуказанное наблюдение и набор легко заметить, что

Из этого уравнения следует, что зная изображения начальных входов для парных значений, можно вычислить выход e переменных входов представленных полу обобщённым алгоритмом без действительной явной оценки парных значений. Другими словами, оракул оперирующий таблицей содержащей для всех комбинаций в и в сможет произвести все BilinearMap запросы.

Анализ выбранных задач в полу обобщённой модели

В данном разделе мы экспериментально проанализируем стойкость вычислительной Со-DH и решающей BDH задачи. Понятно, что список задач рассматриваемых нами здесь будет не полным. Наша основная цель заключается в задании конкретного анализа некоторой значимой задачи билинейной криптографии, и для этого проиллюстрируем основные идеи и методы соответствующих доказательств в данной модели перед оперированием более сложных случаев общих классов задач в Разделе 4.

Сокращение 2-DL до Со-DH

Задача Co-DH используется в [9,8] для построения коротких примеров подписи над билинейными группами. Для набора Типа 2 её можно определить следующим образом: задано , где есть секретный случайный выбор, и где выводиться .

Легко заметить, что для того, чтобы доказать стойкость Со-DH нам определённо необходимо сделать предположение о реализуемости дискретной логарифмической задачи над . Но достаточно ли этого? Ответ «не совсем»: мы ведь собираемся соотнести стойкость Со-DH с 2-DL задачей над , что является более простым аналогом DL. q-DL задачу можно определить следующим образом: задаётся , где есть секретное случайное значение, и выводится . Дополнительный вход (в отличие от стандартного DL) необходим для того, чтобы была возможность генерации пар при выполнении Со-DH алгоритма.

Теорема 1. Предположим существует полу обобщённый алгоритм решающий Со-DH для билинейного набора группы Типа 2 за время с вероятностью успеха . Тогда существует алгоритм решающий 2-DL задачу над за время с вероятностью успеха .

Доказательство. Для заданной 2-DL задачи, устанавливаем для задачи Со-DH в полу обобщённой модели таким образом, чтобы он получал решение для Со-DH вычисляя с помощью решение 2-DL. В частности играет роль полу обобщённого оракула. Разобьём Наблюдение 1 из Раздела 2 для определения данных примеров: Т.к. неизвестны начальные значения , установим и попробуем сгенерировать виртуальное билинейное отображение .

Теперь всё можно описать наш алгоритм сокращения В. В принимает на вход пример 2-DL задачи над . Затем он выбирает и устанавливает Требуемый дискретный логарифм теперь получается в виде секретного выбора в примере Со-DH задачи. Более точно, В устанавливает пример задачи и генерирует оракул следующим способом:

  • Списки инициализируются с , соответственно, где есть набор . Это выявляет и отправляемые А.
  • можно сгенерировать т.к. В известно как реализован групповой закон над .
  • можно сгенерировать находя в , добавляя его в , и затем определяя индекс .
  • Используя Наблюдение 3 из Раздела 2.1 можно легко увидеть, что генерируется: Пусть есть два индекса заданные как входы процедуры А. Тогда мы можем записать


где и и известны В. Т.к. В задаёт и значет , он может вычислить необходимые элементы для генерации парных значений: если и либо .

Для некоторого заданного примера Co-DH, алгоритм А выводит некоторый корректной индекс . Соответствующий элемент можно записать как для некоторого известного полинома (Наблюдение 2, Раздел 2.1). Т.о. мы может также сказать, что А побеждает, если . Успех этого события можно разбить на следующие несвязанные события:

  • Событие : одномерный полином т.е. полином , для которого мы только оцениваем переменную и , будет нулевым модулем . Пусть вероятность данного события обозначается .


  • Событие : одномерный полином будет не нулевым модулем , но . Пусть вероятность этого события обозначается как .


Ясно, что получиться

Давайте рассмотрим события когда В выполняет А для некоторого выбора . Отметим, что В известны коэффициенты Р т.к. он отвечает на запросы А. С вероятностью получаем и . Это означает, что . Но в таком случае необходимо быть эквивалентным . Т.о. В побеждает просто возврящая известный коэффициент . Более того, с вероятностью получаем и . Следовательно, нужный DL будет корнем инвариантного ненулевого полинома известного как В. Его т.о. можно определить как . И легко проверить, что инверсия всегда существует.

В итоге, если равна 0, В выводит в противном случае выводит Т.о. вероятность успеха будет не менее .


Сокращение SqDDH до BDDH

Билинейная решающая задача Диффи-Хеллмана BDDH несомненно является одной из наиболее известных задач над билинейными группами. Она была представлена в работе Джоукса [13] и в дальнейшем использовалась Бонехом и Франклином в [10] для построения схемы шифрования основанной на идентификации. Давайте рассмотрим BDDH для набора Типа 1, где её можно определить как: Задаётся , где , и есть секретные выборы, а выводится .

Мы соотносим стойкость BDDH относительно полу обобщённых алгоритмов со стойкостью известной решающей задачи Диффи-Хеллмана (DDH) и квадратичной решающей задачи Диффи-Хеллмана (SqDDH) над . SqDDH потенциально проще чем DDH: Задаётся , где , и есть секретные выборы, а выводится b. Наш результат обобщён в Теореме 2. Стоит отметить, что в отличие от вычислительных задач (таких как Со-DH) для решающих задач обычно требуется шаги уменьшения умножения. В данном доказательстве основная идея для DDH-шагов заключается в установлении билинейного набора и реализации новой концепции SqDDH-шагов. Т.к. DDH предположение сокращает SqDDH предположение [29] стойкость BDDH можно сформулировать только относительно SqDDH (Следствие 1).

Теорема 2. Предположим существует полу обобщённый алгоритм А решающий BDDH для набора группы Типа 1 за время с вероятностью успеха . Тогда существует алгоритм решающий SqDDH над за время с алгоритмом решающим DDH над за время со средним значением таким, что .

Таблица 1. Преобразование полу обобщённого оракула для реальной BDDH в случайный BDDH использующий SqDDH и DDH шаги.

Abramov 76 1.PNG

Следствие 1. Если SqDDH является (e,t)-стойкой над , то BDDH будет (9e,t)-стойкой для полу обобщённых алгоритмов.

Доказательство (Теоремы 2). Здесь мы покажем, что для полу обобщённого алгоритма «реальный» BDDH кортеж будет вычислительно неразличим то «случайного» кортежа если либо SqDDH либо DDH простые над . Мы реализовываем это рассматривая несколько примеров приведённых для полу обобщённого алгоритма А и оракула О. Начнём с того, что А дан оракульный доступ к реальному BDDH кортежу. Т.к. идёт преобразование этого кортежа а также выходного значения оракула, то в конце мы получаем случайный кортеж. Можно показать, что если А различает по признакам два соответствующих примера и , то он может использовать их для построения алгоритма решающего SqDDH или DDH.

Примеры показаны в Таблице 1. Каждый столбец с наименованием определяет (точно) вход над (см. Строку 1) либо выход в примере для всех возможных входных значений над . Части изображённые жирным шрифтом показывают происходящие изменения относительно предыдущего примера. Вход в последней строке столбца выявляет какое предположение (SqDDH либо DDH) появиться в столбце, это означает, что данное значение будет добавлено к соответствующему примеру и оракул выберет равномерно из .


Как можно заметить из таблицы, посредством мы убираем все квадраты из выхода парного оракула. Мы выполняем это просто заменяя каждый квадрат на новое значение . Это преобразование называется (билинейным) SqDDG шагом и требуется для последовательных DDH шагов при выполнении в Примерах В процессе этих DDH шагов мы селективно убираем все произведения с помощью новых равномерных выбранных значений . В примере равенство независимо от входа, т.к. нигде больше не встречается. После этого, в примере мы делаем обратные действия тем, что мы производили для BilinearMap входа при с инверсным порядком. Более точно, в мы сделаем всё инверсно относительно для И наконец в мы произведём реверсивные изменения (кроме одного в ). Этот последний пример соответствует ситуации, в которой А дан оракульный доступ к случайному BDDH кортежу. Если все начальные примеры вычислительно неразличимы по признакам (при SqDDH и DDH предположении), то несомненно также реальный кортеж BDDH будет вычислительно не различим от случайного кортежа, в соответствии с полу обобщёнными алгоритмами.


Для наглядности, давайте рассмотрим преобразование из в (SqDDH шаг) и из в (DDH шаг) для более детальных и количественных сокращений. Оракул в примере соответствует оригинальному полу обобщённому оракулу для BDDH предоставляющему доступ к реальному BDDH кортежу. Оракул в в эквивалентен за исключением следующих изменений: аддитивно выбирает и использует незначительную модификацию таблицы для расчёта парных выходных значений, как указано в Таблице 1. Положим, что А различает по признакам два примера за время t и с преимуществом


Тогда из А мы можем построить алгоритм В для SqDDH. Опять же, мы можем использовать наблюдение говорящее, что полу обобщённые алгоритмы строятся в соответствии с и , и набором и Теперь пусть будет задан пример

SqDDH задачи над . В выбирает Затем генерирует и как показано ниже (мы определяем ниже как групповые элементы вычисляются через и неизвестные В):

  • Список инициализируется с . Над А задаёт .
  • Для генерации используем тот факт, что нам необходимо только знать выходные парные значения для всех возможных начальных входов. Эти элементы можно вычислить как показано в следующей таблице:
Abramov 76 2.PNG

Легко заметить что если , алгоритм В в точности и в противном случае. Т.о. просто используя выходное значение А, В решает пример SqDDH задачи с аналогичным преимуществом .


Теперь рассмотрим преобразование в . Оракул в совпадает с за исключением следующих изменений: аддитивно выбирает и использует модифицированную таблицу для расчёта парных выходов как показано в Таблице 1. Предположим, А различает по признакам два примера за время t с преимуществом . Тогда мы можем использовать А для построения алгоритма В для DDH. Задаётся пример


DDH над , где В выбирает и генерирует и :

  • Список инициализируется с . Над А задаёт .
  • Для генерации BilinearMap используем следующую таблицу выходных парных значений:
Abramov 76 3.PNG

Если , В ведёт себя как , тогда как если , то он ведёт себя как . Оперируя выходом А, В решает пример DDH задачи с преимуществом .


Оценка будет следующего вида , где , и набор .

Анализ общих классов задач

Анализ общих классов задач, а не частных задач очень необходим по 2 следующим причинам: во-первых, он нужен для того, чтобы улучшить наше понимание свойств удовлетворяемых задачей реализуемой относительно полу обобщённого алгоритма. Во-вторых, - для получения основных теорем классов задач которые могут появиться в последствии.


Обобщенные задачи основанные на парных вычислениях. Пусть наборы Типа 1,2 и 3 будут заданы согласно Определению 1. Более того, пусть будут положительными целыми числами, будут конечными наборами (открытых) полиномов (называемых входными полиномами) и будет простым полиномом. Тогда определим задачу как:

,

где это секретные случайные значения, и выводится . Решительный вариант такой задачи можно определить аналогично. В дальнейшем мы всегда полагаем, что полином 1 содержится в каждом , что соответствует основному предположению, что каждая группа генераторов задаётся изначально.


Говоря более простыми словами, задача не тривиальна если не существует способа вычислить Q при помощи только лишь входных полиномов и операций над ними, которые задаются соответствующим билинейным набором. Давайте рассмотрим случай . Пусть и Тогда применяя Наблюдение 2 (раздел 2.1), можно заметить, что выход полу обобщённого алгоритма для соответствующих задач можно записать как для некоторого Р вида (1):


Мы назовем нетривиальным, если в случае, когда не существует P, как находящееся выше, такое что для всех , т.е , если . Более общие определения могут быть найдены в полной версии этой статьи [30].


Упрощения для Обобщённых задач. Теорема 3 содержит упрощение, которое мы применили для Со-DH в Разделе 3.1 для более общих классов задач. Основное отличие будет в методе для выполнения расчёта дискретного логарифма заданного выходом полу обобщённого алгоритма.


Теорема 3. Пусть и будут нетривиальной задачей с входными полиномами . Пусть Предположим, что есть полу обобщённый алгоритм А решающий за время t с вероятностью успеха . Тогда существует алгоритм В решающий 2k-DL в за время , где , с вероятностью .


Доказательство. Пусть . В принимает на входе Затем выбирается и Неизвестное х рассматривается как секретный выбор в контексте примера . Мы отметим только важные составляющие процесса генерации полу обобщённого оракула: Каждый начальный список инициализируется с элементами , где для полинома , элемент можно рассчитать как используя данный пример для задачи. Это возможно т.к. степень полиномиальна для каждого набора и ограничена сверху по . Таблица для симулирования БилинейнойКарты также может быть создана для каждого в этой таблице. P - снова степень наибольшего в.

Заданное как , A чаще всего выдает индекс . Затем c может быть записано как для некоторого полиномиального P, как описано в 1. A выигрывает, если Т.к. не нулевой модуль (задача не тривиальна) успех данного события можно разбить на два независимых события где определяется как (2):


Выражая вероятность события через получаем .

Теперь предположим, что есть ещё событие , которое происходит с вероятностью . Рассмотрим полином . Этот полином будет вида для некоторого где хотя бы один одночлен переменной встречается с ненулевой экспонентой . Пусть будет одним из этих одночленов. Тогда рассмотрим полином и получим сумму всех одночленов содержащих субодночлен

Получаем и т.к. также выполняется и . Следовательно, есть корень ненулевого инвариантного полинома

Отметим, что Алгоритм В может легко построить полином с помощью выбора переменного одночлена из для которого встречается с ненулевой степенью. Коэффициенты можно также просто рассчитать т.к. коэффициенты известны, а выбираются В. Т.о. применяя эффективный стандартный алгоритм для вычисления корней полиномов над таких как [31], В может найти желаемый DL путём расчёта всех корней полинома . Это приведёт максимум различных корней вычислимых за время [31]. Эквивалентность и можно проверить путём выявления корректно ли .

Мы также можем найти упрощение для общего класса решающих задач, которые эффективны виртуально для всех задач рассматриваемых практически. В особенности, наше упрощение из SqDHH задачи над работает для всех задач где переменные в появляются в большинстве своём с квадратичной степенью, соответственно. Наш подход для общего упрощения отличается от BDDH показанного в Разделе 3.2 следующим: BDDH упрощение явное в том плане, что все упрощающие шаги будут конкретно в полу обобщённой модели. В этом случае, можно сперва получить BDDH для группы с помощью нахождения «соответствующей» задачи, которая упрощает на первом шаге BDDH (при соответствующих полу обобщённых алгоритмах) и затем реализовать DDH и SqDDH шаги упрощения для данной задачи в стандартной модели. Мы следуем данной методике в нашем доказательстве для общих билинейных решающих задач т.к. она обладает преимуществом заимствованным у Брессона и др. для результатов обобщённых DDH задач [25] в стандартной модели. Однако, это не так уж и просто реализовать. Т.к. их результат достаточно упрощён нам необходимо расширить его для большего числа классов задач. Для более детального описания данного вопроса обращайтесь к полной версии работы [30].

Анализ криптосистем в Полу обобщённой модели

Помимо его использования для изучения криптографической стойкости предположений, он также интересен в применении SGGM в качестве элемента анализа безопасности практических криптосистем основанных на использовании парных значений. Аналогичный анализ был сделан для классической GGM [32][33]. В данном разделе мы рассмотрим схему подписи Бонеха-Лина-Шачама [11][12] в SGGM. Выходит, что есть возможность доказательства безопасности данной схемы под полу обобщённой эвристикой групп, с помощью конкретных свойств хэш функции.

BLS схема подписи для билинейного набора Типа 1 определяется следующим образом. Пусть есть хэш функция .


  • выявляет случайный генератор и устанавливает
  • вычисляет и возвращает
  • возвращает 1, если и 0 в противном случае.

Давайте теперь рассмотрим EUF-CMA эксперимент по безопасности для BLS схемы подписи в SGGM. Здесь мы сталкиваемся с технической проблемой: BLS схема убирает хэш функцию т.е. выходом данного отображения будет групповой элемент в некотором заданном представлении. Однако, в SGGM мы хотим рассмотреть алгоритмы, которые независимы от частных представлений элементов . Т.к. в нашей модели элементы задаются списком индексов, то получается, что нету таких представлений групповых элементов, которые мы бы могли использовать для определения хэш функции.

Одним из возможных решений может быть пересмотр основ обобщённой группы Соупа [1]. В данной модели, групповые элементы представляются уникальными случайными строками бит. Т.о. мы можем использовать хэш функцию которая отображает в строку бит соответствующего размера. Однако, тот факт, что групповые элементы кодируются как случайные строки критично рассмотрен в [5][34][35]. К примеру, модель Соупа может неверно реализовать случайный оракул, что недопустимо т.к. нам необходимо избежать наличия случайных оракулов в нашем доказательстве безопасности. Поэтому мы применяем следующий подход. Реализуем как обобщённую групповую хэш функцию.

Определение 2. Групповая хэш функция является парным алгоритмом .


  • GHGen принимает на входе генератор и возвращает . Вектор А определяет функцию .
  • Алгоритм GHEval принимает на вход вектор и строку , а возвращает .

Мы утверждаем, что групповая хэш функция будет обобщённой, если GHGen и GHEval выполняются только для групповых операций элементов А.

Примерами обобщённых групповых хэш функций могут выступать хэш функция в IBE схеме Уотерса [36] а также программируемые хэш функции Хофхейнза и Килтза [37].

Обобщённая групповая хэш функция обладает полезным свойством наличия установки пути обхода системы защиты («лазейки») и оценки алгоритмов (TrapGen, TrapEval) со следующими свойствами.

  • TrapGen принимает на входе генератор . Возвращает вектор , распределённый идентично выходу GHGen для всех и некоторой информации , подвергнутой утечке по «лазейке».
  • Алгоритм TrapEval принимает на вход вектор и строку , а возвращает такой, что .

Для доказательства безопасности нам необходимо предложить стойкую защиту от коллизий.

Определение 3. Групповая функция будет стойкой от -алгебраической коллизии, если

для всех алгоритмов выполняющихся за время .

При применении методики из [37] возможно построение хэш функции удовлетворяющей данному свойству при слабых предположениях, таких как стойкость вычисления дискретных логарифмов в , для любой константы . Основным недочётом, однако, будет то, что для этих конструкций размер вектора А растёт линейно относительно q. Это насущный вопрос требующий дальнейшего анализа и выявления такая групповая хэш функция с лазейкой, для которой размер будет постоянным и будет полиномиальным.

Обобщим EUF-CMA эксперимент в SGGM следующим образом. В начале примера, получим значения для случайного генератора и секретного ключа . Затем выполним , и установим , а также реализуем полу обобщённый оракул со входом I1 как показано в Разделе 2. Это предоставит злоумышленнику открытый ключ, и возможность выполнять групповые операции на элементах .

Когда злоумышленник запрашивает подпись какого-либо выбранного сообщения , участник вычисляет и добавляет его в список .

Мы утверждаем, что злоумышленник выигрывает, если он выводит сообщение и индекс такое, что т.е., злоумышленнику нужно вычислить корректную подпись для . Мы говорим, что полу обобщённый злоумышленник взламывает EUF-CMA безопасность схемы подписи если работает за время и .

Теорема 4. Предположим существует злоумышленник взламывающий EUF-CMA безопасность BLS схемы подписи в полу обобщённой модели с помощью q запросов подписи для выбранных сообщений. Тогда существует алгоритм взлома стойкости алгебраической коллизии и алгоритм решающий дискретную логарифмическую задачу в такие, что и .

Доказательство. Предположим существует такой злоумышленник который выводит сообщение и индекс такие, что В SGGM злоумышленнику необходимо вычислить групповой элемент с помощью применения последовательности групповых операций для начальных значений хранящихся в и для групповых элементов добавленных в список оракулом при ответе на запросы подписи выбранного сообщения. Т.о. когда А выводит такое, что , то оракул получает уравнение (3)


или для целых известных оракулу. Рассмотрим два типа ложных значений:

1. Тип-А ложного значения выполняет следующую последовательность операций (4)

2. Тип-В ложного значения выполняет следующую последовательность операций (5)


Лемма 1. Предположим существует ложное значении Типа-А для взламывающего EUF-CMA безопасность BLS схемы подписи с помощью выполнения максимум q запросов выбранного сообщения. Тогда существует алгоритм взламывающий стойкость алгебраической коллизии (GHGen,GHEval) за время с вероятностью успеха .

Доказательство. Алгоритм получает на входе вектор . Он работает в точности как полу обобщённый EUF-CMA участник, за исключением тогo, что устанавливаются и вместо получения g случайным образом и генерации А с помощью выполнения . Т.о. в частности выбирает секретный ключ , что позволяет ему сгенерировать изначальную работу участника.

Когда А выводит такое, что , то вычисляет и возвращает целые как в Уравнении 4. Заметим, что если Уравнение 4 удовлетворяется, то получаем .

Лемма 2. Предположим существует ложное значении Типа-В для взламывающего EUF-CMA безопасность BLS схемы подписи. Тогда существует алгоритм задачу дискретного логарифма в за время с вероятностью успеха .

Доказательство. Алгоритм получает на входе кортеж . Он устанавливает и выполняет для генерации открытых параметров хэш функции. Заметим, что А распределён идентично некоторому сгенерированному с помощью GHGen. Устанавливается и реализуется полу обобщённый оракул с начальным списком состояний .

Т.к. не известен экспонента секретного ключа , он отвечает на запросы подписи выбранного сообщения А по-разному. также пользуется информацией полученной из «лазейки» генерируемой аналогично с А. Всякий раз, когда А утверждает выбранное сообщение вычисляет и добавляет в Отметим, что т.о. получается корректная подпись.

Когда А выводит такое, что , то вычисялет целые значения как в Уравнении 3 и возвращает

что возможно т.к.

Благодарности. Мы хотели бы поблагодарить Денниса Ховхейнса, Джеспера Васа, Нильсона, и Доминика Унру для их ценные советы а также тех, кто делал анонимные обзоры для Asiacrypt 2010 за их детальные и полезные комментарии.

Контакты авторов материала

  1. Horst G¨ortz Institute for IT Security, Ruhr-University Bochum, Germany, E-mail: [1]
  2. University of Trier, Germany, E-mail: [2]

Примечания

Литература

  1. 1,0 1,1 1,2 Shoup, V.: Lower bounds for discrete logarithms and related problems. In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol. 1233, pp. 256–266. Springer, Heidelberg (1997)
  2. 2,0 2,1 Maurer, U.: Abstract models of computation in cryptography. In: Smart, N.P. (ed.) Cryptography and Coding 2005. LNCS, vol. 3796, pp. 1–12. Springer, Heidelberg (2005)
  3. Pohlig, S.C., Hellman, M.E.: An improved algorithm for computing logarithms over GF(p) and its cryptographic significance. IEEE Transactions on Information Theory 24, 106–110 (1978)
  4. Pollard, J.M.: Monte Carlo methods for index computation mod p. Mathematics of Computation 32, 918–924 (1978)
  5. 5,0 5,1 Dent, A.W.: Adapting the weaknesses of the random oracle model to the generic group model. In: Zheng, Y. (ed.) ASIACRYPT 2002. LNCS, vol. 2501, pp. 100–109. Springer, Heidelberg (2002)
  6. Hohenberger, S.: The cryptographic impact of groups with infeasible inversion. Master’s thesis, Massachusetts Institute of Technology (2003)
  7. Rivest, R.L.: On the notion of pseudo-free groups. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 505–521. Springer, Heidelberg (2004)
  8. Leander, G., Rupp, A.: On the equivalence of RSA and factoring regarding generic ring algorithms. In: Lai, X., Chen, K. (eds.) ASIACRYPT 2006. LNCS, vol. 4284, pp. 241–251. Springer, Heidelberg (2006)
  9. Jager, T., Schwenk, J.: On the analysis of cryptographic assumptions in the generic ring model. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 399–416. Springer, Heidelberg (2009)
  10. 10,0 10,1 Boneh, D., Franklin, M.K.: Identity-based encryption from the Weil pairing. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 213–229. Springer, Heidelberg (2001)
  11. 11,0 11,1 11,2 11,3 Boneh, D., Lynn, B., Shacham, H.: Short signatures from theWeil pairing. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol. 2248, pp. 514–532. Springer, Heidelberg (2001)
  12. 12,0 12,1 12,2 Boneh, D., Lynn, B., Shacham, H.: Short signatures from the Weil pairing. J. Cryptology 17(4), 297–319 (2004)
  13. 13,0 13,1 Joux, A.: A one round protocol for tripartite Diffie-Hellman. In: Bosma, W. (ed.) ANTS 2000. LNCS, vol. 1838, pp. 385–394. Springer, Heidelberg (2000)
  14. Joux, A.: A one round protocol for tripartite Diffie-Hellman. J. Cryptology 17(4), 263–276 (2004)
  15. Boneh, D., Boyen, X.: Efficient selective-id secure identity-based encryption without random oracles. In: Cachin, C., Camenisch, J. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 223– 238. Springer, Heidelberg (2004)
  16. Cheon, J.: Security analysis of the Strong Diffie-Hellman problem. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 1–11. Springer, Heidelberg (2006)
  17. Jao, D., Yoshida, K.: Boneh-Boyen signatures and the Strong Diffie-Hellman problem. Cryptology ePrint Archive, Report 2009/221 (2009), http://eprint.iacr.org/
  18. Boneh, D., Boyen, X., Shacham, H.: Short group signatures. In: Franklin, M.K. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 41–55. Springer, Heidelberg (2004)
  19. Boneh, D., Gentry, C., Lynn, B., Shacham, H.: Aggregate and verifiably encrypted signatures from bilinear maps. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 416–432. Springer, Heidelberg (2003)
  20. 20,0 20,1 20,2 Rupp, A., Leander, G., Bangerter, E., Dent, A.W., Sadeghi, A.: Sufficient conditions for intractability over black-box groups: Generic lower bounds for generalized DL and DH problems. In: Pieprzyk, J. (ed.) ASIACRYPT 2008. LNCS, vol. 5350, pp. 489–505. Springer, Heidelberg (2008)
  21. 21,0 21,1 21,2 Boyen, X.: The Uber-Assumption family. In: Galbraith, S.D., Paterson, K.G. (eds.) Pairing 2008. LNCS, vol. 5209, pp. 39–56. Springer, Heidelberg (2008)
  22. Katz, J., Sahai, A., Waters, B.: Predicate encryption supporting disjunctions, polynomial equations, and inner products. In: Smart, N.P. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 146–162. Springer, Heidelberg (2008)
  23. Menezes, A., Okamoto, T., Vanstone, S.: Reducing elliptic curve logarithms to logarithms in a finite field. IEEE Transactions on Information Theory 39(5), 1639–1646 (1993)
  24. Boneh, D.: Number-theoretic assumptions. Invited Talk at TCC’s Special Session on Assumptions for Cryptography (2007)
  25. 25,0 25,1 25,2 Bresson, E., Lakhnech, Y., Mazar´e, L., Warinschi, B.: A generalization of DDH with applications to protocol analysis and computational soundness. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol. 4622, pp. 482–499. Springer, Heidelberg (2007)
  26. Boneh, D., Boyen, X., Goh, E.: Hierarchical identity based encryption with constant size ciphertext (full paper). Cryptology ePrint Archive, Report 2005/015 (2005), http://eprint.iacr.org/
  27. Bellare, M., Rogaway, P.: Random oracles are practical: A paradigm for designing efficient protocols. In: ACMConference on Computer and Communications Security, pp. 62–73 (1993)
  28. Galbraith, S.D., Paterson, K.G., Smart, N.P.: Pairings for cryptographers. Discrete Applied Mathematics 156(16), 3113–3121 (2008)
  29. Wolf, S.: Information-theoretically and computationally secure key agreement in cryptography. PhD thesis, ETH Zurich, ETH dissertation No. 13138 (1999)
  30. 30,0 30,1 Jager, T., Rupp, A.: The semi-generic group model and applications to pairing-based cryptography (full paper) (2010), http://www.nds.rub.de/chair/publications/
  31. 31,0 31,1 von zur Gathen, J., Gerhard, J.: Modern Computer Algebra, 2nd edn. Cambridge University Press, Cambridge (2003)
  32. Smart, N.P.: The exact security of ECIES in the generic group model. In: Honary, B. (ed.) Cryptography and Coding 2001. LNCS, vol. 2260, pp. 73–84. Springer, Heidelberg (2001)
  33. Brown, D.R.L.: Generic groups, collision resistance, and ECDSA. Des. Codes Cryptography 35(1), 119–152 (2005)
  34. Fischlin, M.: A note on security proofs in the generic model. In: Okamoto, T. (ed.) ASIACRYPT 2000. LNCS, vol. 1976, pp. 458–469. Springer, Heidelberg (2000)
  35. Koblitz, N., Menezes, A.: Another look at generic groups. Advances in Mathematics of Communications 1, 13–28 (2007)
  36. Waters, B.: Efficient identity-based encryption without random oracles. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 114–127. Springer, Heidelberg (2005)
  37. 37,0 37,1 Hofheinz, D., Kiltz, E.: Programmable hash functions and their applications. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 21–38. Springer, Heidelberg (2008)