# The Semi-Generic Group Model and Applications to Pairing-Based Cryptography

 The Semi-Generic Group Model and Applications to Pairing-Based Cryptography Authors Tibor Jager [@: 1] , Andy Rupp [@: 2] Published 2011 г. Download Original

Abstract. In pairing-based cryptography the Generic Group Model (GGM) is used frequently to provide evidence towards newly introduced hardness assumptions. Unfortunately, the GGM does not reflect many known properties of bilinear group settings and thus hardness results in this model are of limited significance. This paper proposes a novel computational model for pairing-based cryptography, called the Semi-Generic Group Model (SGGM), that is closer to the standard model and allows to make more meaningful security guarantees. In fact, the best algorithms currently known for solving pairing-based problems are semi-generic in nature. We demonstrate the usefulness of our new model by applying it to study several important assumptions (BDDH, Co-DH). Furthermore, we develop master theorems facilitating an easy analysis of other (future) assumptions. These master theorems imply that (unless there are better algorithms than the semigeneric ones) great parts of the zoo of novel assumptions over bilinear groups are reducible to just two (more or less) standard assumptions over finite fields. Finally, we examine the appropriateness of the SGGM as a tool for analyzing the security of practical cryptosystems without random oracles by applying it to the BLS signature scheme.

Keywords: Restricted models of computation, generic groups, semi-generic group model, cryptographic assumptions, master theorems, provable security, pairingbased cryptography.

## Introduction

Assuming that certain computational problems, mostly from algebra, number theory, and coding theory, are intractable builds the foundation of public-key cryptography. However, proving the validity of these assumptions in the standard model of computation seems to be impossible with currently available techniques.

Why do we believe in such hardness assumptions, though they are not provable in general? For classic number-theoretic problems, such as integer factorization (IF) or the discrete logarithm (DL) problem, this is certainly due to the absence of efficient algorithms in spite of intensive long-term research by many brilliant people. However, besides such well-known assumptions, there frequently appear new assumptions building the basis for novel cryptosystems with original properties. What can be done to provide evidence for these assumptions apart from trying to find efficient algorithms over decades? Clearly, we should try to underpin the belief in novel assumptions by searching for reductions to a more mature assumption; but unfortunately finding such a reduction often fails.

An important approach to (nevertheless) gain immediate evidence towards hardness assumptions is to prove them with respect to a restricted but still meaningful class of algorithms. This is the motivation behind the invention of black-box models for algebraic structures like groups, fields, and rings, where algorithms are limited to perform only operations “commonly” available over these structures. Probably, the most famous of these models is the generic group model (GGM) introduced by Shoup in his seminal paper [1] 1997, from 1997, and refined by Maurer in [2]. In this model one considers algorithms – so-called generic group algorithms – that, given a group G as black-box, may only perform a set of basic operations on the elements of G such as applying the group law, inversion of group elements and equality testing. Since the group is treated as a black-box, the algorithms cannot exploit any special properties of a concrete group representation. As a consequence, such algorithms are generic in the sense that they can be applied to any concrete instantiation of a group in order so solve a problem. Natural examples of this class of algorithms are the Pohlig-Hellman [3] and Pollard’s Rho [4] algorithm for computing discrete logarithms.

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

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

За последнюю декаду было предложено значительное количество криптосистем над билинейными группами таких, как шифрование основанное на идентификации [10] или короткая цифровая подпись со стойкой безопасностью [11] [12]. Набор билинейной группы состоит из групп ${\displaystyle \mathbb {G} _{1},\mathbb {G} _{2}~\,\!}$, и ${\displaystyle \mathbb {G} _{3}~\,\!}$ с билинейным отображением ${\displaystyle e:\mathbb {G} _{1}\times \mathbb {G} _{2}\rightarrow \mathbb {G} _{3}~\,\!}$, которое называется получение парного значения. Для данных криптосистем было предложено много новых предположений, например, Билинейное предположение Диффи-Хеллмана BDH [13] [14], q-стойкое предположение Диффи-Хеллмана [15][16][17], предположение Диффи-Хеллмана о линейном решении DLIN [18], предположение Со-Диффи-Хеллмана Со-DH [19][11], и многие другие. К несчастью, показано, что ни одно из них нельзя свести к хорошо известному DL. Действительно, нахождение такого сведения является сложной задачей, т.к. алгебраический набор соответствующих классических задач (например, простая циклическая группа для DL) значительно отличается от билинейного набора. Из этого следует, что для данного примера классической задачи сложно найти аналог преобразования её в билинейную задачу.

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

Наш вклад. Мы предлагаем ввашему вниманию полу обобщённую Групповую Модель (SGGM) которая использует данную методику следующим образом: группы эллиптических кривых ${\displaystyle \mathbb {G} _{1},\mathbb {G} _{2}~\,\!}$, моделируются как обобщённые группы, тогда как ${\displaystyle \mathbb {G} _{3}~\,\!}$ задаётся в стандартной модели, т.е. алгоритмы могут выполнять либое вычисление над ${\displaystyle \mathbb {G} _{3}~\,\!}$, которое возможно в подгруппе конечного поля. SGGM т.о. будет приближённее к стандартной модели, чем GGM и может обеспечивать более лучшее доказательство для стойкости предположений в криптографии основанной на использовании парных значений. В действительности, насколько нам известно все алгоритмы на текущий момент решающие задачу парного распределения являются по совей сути полу обобщёнными. В частности, субэкспоненциальные алгоритмы применяющие MOV сокращение описанные выше покрываются SGGM.

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

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

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

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

Пусть ${\displaystyle \mathbb {G} _{1},\mathbb {G} _{2}~\,\!}$, и ${\displaystyle \mathbb {G} _{3}~\,\!}$ будут группами простого порядка ${\displaystyle p~\,\!}$ и ${\displaystyle g_{1}\in \mathbb {G} _{1},g_{2}\in \mathbb {G} _{2}~\,\!}$ будут соответствующими генераторами. Для упрощения последующей формализации воспользуемся определением для всех групп.

Определение 1. Получение парного значения есть отображение ${\displaystyle e:\mathbb {G} _{1}\times \mathbb {G} _{2}\rightarrow \mathbb {G} _{3}~\,\!}$ со следующими свойствами:

1. Билинейность: ${\displaystyle \forall (a,b)\in \mathbb {G} _{1}\times \mathbb {G} _{2}~\,\!}$ и ${\displaystyle x_{1},x_{2}\in \mathbb {Z} ~\,\!}$ выполняется ${\displaystyle e(a^{x_{1}},b^{x_{2}})=e(a,b)^{x_{1}x_{2}}~\,\!}$

2. Невырожденность: ${\displaystyle g_{3}:=e(g_{1},g_{2})~\,\!}$ есть генератор ${\displaystyle \mathbb {G} _{3}~\,\!}$, т.е ${\displaystyle g_{3}\neq 1~\,\!}$.

3. ${\displaystyle e~\,\!}$ эффективно вычислимо.

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

• Тип 1: ${\displaystyle \mathbb {G} _{1}=\mathbb {G} _{2}~\,\!}$. Назовём это установкой с симметрическим билинейным отображением.
• Тип 1: ${\displaystyle \mathbb {G} _{1}\neq \mathbb {G} _{2}~\,\!}$, существует эффективно вычислимый изоморфизм ${\displaystyle \psi :\mathbb {G} _{1}\rightarrow \mathbb {G} _{2}~\,\!}$.
• Тип 3: ${\displaystyle \mathbb {G} _{1}\neq \mathbb {G} _{2}~\,\!}$, существует не эффективно вычислимый изоморфизм ${\displaystyle \psi :\mathbb {G} _{1}\rightarrow \mathbb {G} _{2}~\,\!}$.

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

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

${\displaystyle I_{1}=(a_{1,1},...,a_{1,k_{1}})\in \mathbb {G} _{1}^{k_{1}}~\,\!}$ и ${\displaystyle I_{2}=(a_{2,1},...,a_{2,k_{2}})\in \mathbb {G} _{2}^{k_{2}}~\,\!}$

В общем случае, оба ${\displaystyle \varepsilon _{1}\subseteq \mathbb {G} _{1}~\,\!}$ и ${\displaystyle \varepsilon _{2}\subseteq \mathbb {G} _{2}~\,\!}$ с ${\displaystyle \varepsilon _{i,j}~\,\!}$ определяют j-ый вход ${\displaystyle \varepsilon _{i}~\,\!}$, который инициализирован так, что ${\displaystyle \varepsilon _{i,j}:=a_{i,j}~\,\!}$ для всех возможных ${\displaystyle (i,j)~\,\!}$. Обозначим за ${\displaystyle [a]_{i}~\,\!}$ наименьший индекс ${\displaystyle j~\,\!}$ (также называемый кодированием) такой, что ${\displaystyle \varepsilon _{i,j}=a~\,\!}$. Индекс будет не определён, если ${\displaystyle a\in \varepsilon _{i}~\,\!}$. Можно всегда предположить, что полу обобщённые алгоритмы реализуют только определённые индексы выходных значений для оракула. В процессе инициализации ${\displaystyle \varepsilon _{i}~\,\!}$, соответствующие индексы относительно содержащихся элементов отсылаются алгоритму.

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

• ${\displaystyle GroupOp([a]_{i},[b]_{i},i):~\,\!}$ Эта процедура получает на входе два индекса ${\displaystyle [a]_{i},[b]_{i}~\,\!}$ и индекс списка ${\displaystyle i~\,\!}$. Она определяет групповые элементы ${\displaystyle a,b\in \mathbb {G} _{i}~\,\!}$ с помощью просмотра списка, и вычисляет ${\displaystyle c=a\cdot b\in \mathbb {G} _{i}~\,\!}$, добавляет ${\displaystyle c~\,\!}$ в ${\displaystyle \varepsilon _{i}~\,\!}$ и возвращает ${\displaystyle [c]_{i}~\,\!}$.
• ${\displaystyle BilinearMap([a]_{1},[b]_{2})~\,\!}$ Эта процедура получает на входе два индекса ${\displaystyle [a]_{1},[b]_{2}~\,\!}$. Она определяет соответствующие групповые элементы ${\displaystyle a\in \mathbb {G} _{1},b\in \mathbb {G} _{2}~\,\!}$ с помощью просмотра списка и возвращает ${\displaystyle e(a,b)~\,\!}$ в стандартном представлении ${\displaystyle \mathbb {G} _{3}~\,\!}$ (т.е., как конечное поле элемента).

Когда рассматривается набор Типа 2 алгоритм также старается реализовать изоморфизм ${\displaystyle \psi ~\,\!}$ для элемента ${\displaystyle \mathbb {G} _{1}~\,\!}$:

• ${\displaystyle Isomorphism([a]_{1})~\,\!}$ Эта процедура получает на входе индекс ${\displaystyle [a]_{1}~\,\!}$, определяет элемент ${\displaystyle a\in \mathbb {G} _{1}~\,\!}$, вычисляет ${\displaystyle b=\psi (a)~\,\!}$, добавляет ${\displaystyle b~\,\!}$ к ${\displaystyle \varepsilon _{2}~\,\!}$ и возвращает ${\displaystyle [b]_{2}~\,\!}$.

Отметим, что случайный групповой элемент можно эффективно получить с помощью полу обобщённого алгоритма ${\displaystyle GroupOp(\cdot )~\,\!}$ для расширения генератора (который всегда является частью примера задачи) до ${\displaystyle r{\xleftarrow {\}}\mathbb {Z} _{p}~\,\!}$.

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

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

Наблюдение 1: Составные части оракула взаимозаменяемы. Полу обобщённые алгоритмы по своей сути не получают информации касательно начальных значений для групп ${\displaystyle \mathbb {G} _{1}\mathbb {G} _{2}~\,\!}$ также как и парные ${\displaystyle e~\,\!}$ и изоморфизм ${\displaystyle \psi ~\,\!}$. Данные компоненты сокрыты чёрным ящиком. Следовательно, мы модем применить что-нибудь другое для этих компонентов т.к. любая их замена будет выглядеть как циклическая группа с билинейным отображением и изоморфизмом. Преобразуем это наблюдение в новый вид для отображения входов заданных над ${\displaystyle \mathbb {G} _{3}\mathbb {G} _{1}~\,\!}$, и ${\displaystyle \mathbb {G} _{2}~\,\!}$ набором ${\displaystyle \mathbb {G} _{1}:=\mathbb {G} _{2}:=\mathbb {G} _{3}~\,\!}$ изначально и симуляцией виртуального билинейного отображения ${\displaystyle e:\mathbb {G} _{3}\times \mathbb {G} _{3}\rightarrow \mathbb {G} _{3}~\,\!}$ и изоморфизмом ${\displaystyle \psi :\mathbb {G} _{3}\rightarrow \mathbb {G} _{3}~\,\!}$.

Наблюдение 2: Вычисляемые элементы над ${\displaystyle \mathbb {G} _{1},\mathbb {G} _{2}~\,\!}$ будут линейными полиномами для начальных входных значений. Пусть ${\displaystyle I_{1}\in \mathbb {G} _{1}^{m}~\,\!}$ и ${\displaystyle I_{2}\in \mathbb {G} _{2}^{n}~\,\!}$ будут входами заданными для полу обобщённого оракула (как части примера задачи). Получим ${\displaystyle I_{1}=I_{2}~\,\!}$ в случае набора Типа 1. В дальнейшем, мы всегда полагаем, что задано не менее двух ${\displaystyle g_{1}~\,\!}$ и ${\displaystyle g_{2}~\,\!}$ генераторов. Т.о. можно записать ${\displaystyle I_{1}=(g_{1},g_{1}^{x_{2}},...,g_{1}^{x_{m}})~\,\!}$ и ${\displaystyle I_{2}=(g_{2},g_{2}^{y_{2}},...,g_{2}^{y_{n}})~\,\!}$ для некоторого неизвестного ${\displaystyle x_{j},y_{k}\in \mathbb {Z} _{p}~\,\!}$ (здесь не делается никаких предположений о его распределении) и ${\displaystyle \psi (g_{1})=g_{2}~\,\!}$ для случая набора Типа 2. Затем определяем кортеж ${\displaystyle I'_{1}:=I_{1}~\,\!}$ и кортеж ${\displaystyle I'_{2}:=I_{2}~\,\!}$ для случая с наборами Типа 1 и 3 либо ${\displaystyle I'_{2}:=(g_{2},g_{2}^{x_{2}},...,g_{2}^{x_{m}},g_{2}^{y_{2}},...,g_{2}^{y_{n}}~\,\!}$ для набора Типа 2. Эти кортежи называются начальными значениями на входе полу обобщённых алгоритмов. Используя данное определение, мы можем описать следующее наблюдение: над ${\displaystyle \mathbb {G} _{1},\mathbb {G} _{2}~\,\!}$, полу обобщённый алгоритм может выполнять групповой закон только для входных значений. Т.о. любой элемент ${\displaystyle a\in \mathbb {G} _{i}(i\in {1,2})~\,\!}$ вычисляемый с помощью полу обобщённого алгоритма будет суммой элементов в ${\displaystyle I'_{i}~\,\!}$. Следовательно, можно показать такой элемент, что ${\displaystyle a=g_{i}^{P(x_{2},...,x_{m},y_{2},...,y_{n})}~\,\!}$ для некоторого линейного многовариантного полинома ${\displaystyle P=\alpha _{1}+\sum _{j=2}^{m}\alpha _{j}X_{j}+\sum _{j=2}^{n}\beta _{j}Y_{j}~\,\!}$, где ${\displaystyle \beta _{j}~\,\!}$ будет нулём в случае ${\displaystyle i=1~\,\!}$ или если мы рассматриваем набор Типа 1. Следует отметить, что все коэффициенты данного полинома известны оракулу.

Наблюдение 3: Парные значения являются одновременно известными изображениями начальных входов. Пусть ${\displaystyle a\in \mathbb {G} _{1}~\,\!}$ и ${\displaystyle b\in \mathbb {G} _{2}~\,\!}$ будут двумя элементами вычисляемыми с помощью полу обобщённого алгоритма. Тогда используя вышеуказанное наблюдение и набор ${\displaystyle x_{1}:=1~\,\!}$ легко заметить, что

${\displaystyle e(a,b)=e(g_{1}^{\sum _{i=1}^{m}\alpha _{i}x_{i}},g_{2}^{\sum _{j=1}^{m}\alpha '_{j}x_{j}+\sum _{k=2}^{n}\beta '_{k}y_{k}})~\,\!}$

${\displaystyle =\prod _{i=1}^{m}\prod _{j=1}^{m}e(g_{1}^{x_{i}},g_{2}^{x_{j}})^{\alpha _{i}\alpha '_{j}}\cdot \prod _{i=1}^{m}\prod _{k=2}^{n}e(g_{1}^{x_{i}},g_{2}^{y_{k}})^{\alpha _{i}\beta '_{k}}~\,\!}$

Из этого уравнения следует, что зная изображения начальных входов для парных значений, можно вычислить выход e переменных входов представленных полу обобщённым алгоритмом без действительной явной оценки парных значений. Другими словами, оракул оперирующий таблицей содержащей ${\displaystyle e(a,b)~\,\!}$ для всех комбинаций ${\displaystyle a~\,\!}$ в ${\displaystyle I'_{1}~\,\!}$ и ${\displaystyle b~\,\!}$ в ${\displaystyle I'_{2}~\,\!}$ сможет произвести все BilinearMap запросы.

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

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

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

Задача Co-DH используется в [9,8] для построения коротких примеров подписи над билинейными группами. Для набора Типа 2 её можно определить следующим образом: задано ${\displaystyle (g_{1},g_{1}^{x_{0}},g_{2},g_{2}^{x_{1}},g_{3})~\,\!}$, где ${\displaystyle (x_{0},x_{1}){\xleftarrow {\}}\mathbb {Z} _{p}^{2}~\,\!}$ есть секретный случайный выбор, и где выводиться ${\displaystyle g_{2}^{x_{0}x_{1}}~\,\!}$.

Легко заметить, что для того, чтобы доказать стойкость Со-DH нам определённо необходимо сделать предположение о реализуемости дискретной логарифмической задачи над ${\displaystyle \mathbb {G} _{3}~\,\!}$. Но достаточно ли этого? Ответ «не совсем»: мы ведь собираемся соотнести стойкость Со-DH с 2-DL задачей над ${\displaystyle \mathbb {G} _{3}~\,\!}$, что является более простым аналогом DL. q-DL задачу можно определить следующим образом: задаётся ${\displaystyle (g_{3},g_{3}^{x^{1}},...,g_{3}^{x^{q}})~\,\!}$, где ${\displaystyle x{\xleftarrow {\}}\mathbb {Z} _{p}~\,\!}$ есть секретное случайное значение, и выводится ${\displaystyle x~\,\!}$. Дополнительный вход ${\displaystyle g_{3}^{x^{2}}~\,\!}$ (в отличие от стандартного DL) необходим для того, чтобы была возможность генерации пар при выполнении Со-DH алгоритма.

Теорема 1. Предположим существует полу обобщённый алгоритм ${\displaystyle A~\,\!}$ решающий Со-DH для билинейного набора группы Типа 2 за время ${\displaystyle t~\,\!}$ с вероятностью успеха ${\displaystyle \epsilon ~\,\!}$. Тогда существует алгоритм ${\displaystyle B~\,\!}$ решающий 2-DL задачу над ${\displaystyle \mathbb {G} _{3}~\,\!}$ за время ${\displaystyle t'\approx t~\,\!}$ с вероятностью успеха ${\displaystyle \epsilon '\geq {\frac {1}{2}}\epsilon ~\,\!}$.

Доказательство. Для заданной 2-DL задачи, устанавливаем ${\displaystyle B~\,\!}$ для задачи Со-DH в полу обобщённой модели таким образом, чтобы он получал решение для Со-DH вычисляя с помощью ${\displaystyle A~\,\!}$ решение 2-DL. В частности ${\displaystyle B~\,\!}$ играет роль полу обобщённого оракула. Разобьём Наблюдение 1 из Раздела 2 для определения данных примеров: Т.к. ${\displaystyle A~\,\!}$ неизвестны начальные значения ${\displaystyle \mathbb {G} _{1},\mathbb {G} _{2},e,\psi ~\,\!}$, установим ${\displaystyle \mathbb {G} _{1}:=\mathbb {G} _{2}:=\mathbb {G} _{3}~\,\!}$ и попробуем сгенерировать виртуальное билинейное отображение ${\displaystyle e:\mathbb {G} _{3}\times \mathbb {G} _{3}\rightarrow \mathbb {G} _{3}~\,\!}$.

Теперь всё можно описать наш алгоритм сокращения В. В принимает на вход пример ${\displaystyle a_{0}:=g_{3},a_{1}:=g_{3}^{x},a_{3}:=g_{3}^{x^{2}}~\,\!}$ 2-DL задачи над ${\displaystyle \mathbb {G} _{3}~\,\!}$. Затем он выбирает ${\displaystyle i^{*}{\xleftarrow {\}}{0,1},x_{1-i^{*}}{\xleftarrow {\}}\mathbb {Z} _{p}~\,\!}$ и устанавливает ${\displaystyle a_{2}:=g_{3}^{x_{1-i^{*}}}~\,\!}$ Требуемый дискретный логарифм ${\displaystyle x~\,\!}$ теперь получается в виде секретного выбора ${\displaystyle x_{i^{*}}~\,\!}$ в примере Со-DH задачи. Более точно, В устанавливает пример задачи и генерирует оракул ${\displaystyle O~\,\!}$ следующим способом:

• Списки ${\displaystyle \varepsilon _{1}\varepsilon _{2}~\,\!}$ инициализируются с ${\displaystyle g_{3},g_{3}^{x_{0}}andg_{3},g_{3}^{x_{1}}~\,\!}$, соответственно, где ${\displaystyle g_{3}^{x_{i^{*}}}~\,\!}$ есть набор ${\displaystyle a_{1}~\,\!}$. Это выявляет ${\displaystyle [g_{3}]_{1},[g_{3}^{x_{0}}]_{1},[g_{3}]_{2},[g_{3}^{x_{1}}]_{2}~\,\!}$ и ${\displaystyle g_{3}~\,\!}$ отправляемые А.
• ${\displaystyle GroupOp~\,\!}$ можно сгенерировать т.к. В известно как реализован групповой закон над ${\displaystyle \mathbb {G} _{3}~\,\!}$.
• ${\displaystyle Isomorphism([a]_{1})~\,\!}$ можно сгенерировать находя ${\displaystyle a~\,\!}$ в ${\displaystyle \varepsilon _{1}~\,\!}$, добавляя его в ${\displaystyle \varepsilon _{2}~\,\!}$, и затем определяя индекс ${\displaystyle [a]_{2}~\,\!}$.
• Используя Наблюдение 3 из Раздела 2.1 можно легко увидеть, что ${\displaystyle BilinearMap~\,\!}$ генерируется: Пусть ${\displaystyle [b]_{1},[c]_{2}~\,\!}$ есть два индекса заданные как входы процедуры А. Тогда мы можем записать

${\displaystyle e(b,c)=e(g_{3}^{\sum _{j=-1}^{o}{z_{j}x_{j}}},g_{3}^{\sum _{k=-1}^{1}{z'_{k}x_{k}}})=\prod _{j=-1}^{0}\prod _{k=-1}^{1}(g_{3}^{x_{j}x_{k}})^{z_{j}z'_{k}}~\,\!}$

где ${\displaystyle x_{-1}:=1~\,\!}$ и ${\displaystyle z_{j}~\,\!}$ и ${\displaystyle z'_{k}~\,\!}$ известны В. Т.к. В задаёт ${\displaystyle a_{0},...,a_{3}~\,\!}$ и значет ${\displaystyle i^{*},x_{1-i^{*}}~\,\!}$, он может вычислить необходимые элементы ${\displaystyle g_{3},g_{3}^{x_{0}},g_{3}^{x_{1}},g_{3}^{x_{0}^{2}},g_{3}^{x_{0}x_{1}}~\,\!}$ для генерации парных значений: ${\displaystyle g_{3}=a_{0},g_{3}^{x_{i^{*}}}=a_{1},g_{3}^{x_{1-i^{*}}}=a_{2},g_{3}^{x_{0}^{2}}=a_{3},~\,\!}$ если ${\displaystyle i^{*}=0~\,\!}$ и ${\displaystyle g_{3}^{x_{0}^{2}}=a_{2}^{x_{0}}~\,\!}$ либо ${\displaystyle g_{3}^{x_{0}x_{1}}=a_{1}^{x_{1-i^{*}}}~\,\!}$.

Для некоторого заданного примера Co-DH, алгоритм А выводит некоторый корректной индекс ${\displaystyle [c]_{2}~\,\!}$. Соответствующий элемент ${\displaystyle c\in \mathbb {G} _{2}~\,\!}$ можно записать как ${\displaystyle c=g_{2}^{P(x_{0},x_{1})}~\,\!}$ для некоторого известного полинома ${\displaystyle P=z_{0}+z_{1}X_{0}+z_{2}X_{1}\in \mathbb {Z} _{p}[X_{0},X_{1}]~\,\!}$ (Наблюдение 2, Раздел 2.1). Т.о. мы может также сказать, что А побеждает, если ${\displaystyle (P-X_{0}X_{1})(x_{0},x_{1})\equiv 0modp~\,\!}$. Успех этого события можно разбить на следующие несвязанные события:

• Событие ${\displaystyle S_{1}~\,\!}$: одномерный полином ${\displaystyle (P-X_{0}X_{1})(x_{0})~\,\!}$ т.е. полином ${\displaystyle P-X_{0}X_{1}~\,\!}$, для которого мы только оцениваем переменную ${\displaystyle X_{0}~\,\!}$ и ${\displaystyle x_{0}~\,\!}$, будет нулевым модулем ${\displaystyle p~\,\!}$. Пусть вероятность данного события обозначается ${\displaystyle \alpha _{1}~\,\!}$.

• Событие ${\displaystyle S_{2}~\,\!}$: одномерный полином ${\displaystyle (P-X_{0}X_{1})(x_{0})~\,\!}$ будет не нулевым модулем ${\displaystyle p~\,\!}$, но ${\displaystyle (P-X_{0}X_{1})(x_{0},x_{1})~\,\!}$. Пусть вероятность этого события обозначается как ${\displaystyle \alpha _{2}~\,\!}$.

Ясно, что получиться ${\displaystyle \epsilon =\alpha _{1}+\alpha _{2}~\,\!}$

Давайте рассмотрим события ${\displaystyle S_{1}andS_{2}~\,\!}$ когда В выполняет А для некоторого выбора ${\displaystyle i^{*}~\,\!}$. Отметим, что В известны коэффициенты Р т.к. он отвечает на запросы А. С вероятностью ${\displaystyle {\frac {1}{2}}\alpha _{1}~\,\!}$ получаем ${\displaystyle i^{*}=0~\,\!}$ и ${\displaystyle S_{1}~\,\!}$. Это означает, что ${\displaystyle z_{0}+z_{1}x+z_{2}X_{1}-xX_{1}\equiv 0~\,\!}$. Но в таком случае ${\displaystyle z_{2}~\,\!}$ необходимо быть эквивалентным ${\displaystyle x~\,\!}$. Т.о. В побеждает просто возврящая известный коэффициент ${\displaystyle z_{2}~\,\!}$. Более того, с вероятностью ${\displaystyle {\frac {1}{2}}\alpha _{2}~\,\!}$ получаем ${\displaystyle i^{*}=1~\,\!}$ и ${\displaystyle S_{2}~\,\!}$. Следовательно, нужный DL будет корнем инвариантного ненулевого полинома ${\displaystyle z_{0}+z_{1}x_{0}+z_{2}X_{1}-x_{0}X_{1}~\,\!}$ известного как В. Его т.о. можно определить как ${\displaystyle x\equiv (z_{0}+z_{1}x_{0})(x_{0}-z_{2})^{-1}modp~\,\!}$. И легко проверить, что инверсия ${\displaystyle (x_{0}-z_{2})^{-1}~\,\!}$ всегда существует.

В итоге, если ${\displaystyle i^{*}~\,\!}$ равна 0, В выводит ${\displaystyle z_{2}~\,\!}$ в противном случае выводит ${\displaystyle (z_{0}+z_{1}x_{0})(x_{0}-z_{2})^{-1}~\,\!}$ Т.о. вероятность успеха будет не менее ${\displaystyle {\frac {1}{2}}\alpha _{1}+{\frac {1}{2}}\alpha _{2}={\frac {1}{2}}\epsilon ~\,\!}$.

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

Билинейная решающая задача Диффи-Хеллмана BDDH несомненно является одной из наиболее известных задач над билинейными группами. Она была представлена в работе Джоукса [13] и в дальнейшем использовалась Бонехом и Франклином в [10] для построения схемы шифрования основанной на идентификации. Давайте рассмотрим BDDH для набора Типа 1, где её можно определить как: Задаётся ${\displaystyle (g_{1},g_{1}^{x_{1}},g_{1}^{x_{2}},g_{1}^{x_{3}},g_{1}^{r_{b}})~\,\!}$, где ${\displaystyle (x_{1},x_{2},x_{3}){\xleftarrow {\}}\mathbb {Z} _{p}^{3},b{\xleftarrow {\}}{0,1},r_{1}=x_{1}x_{2}x_{3}~\,\!}$, и ${\displaystyle r_{0}{\xleftarrow {\}}\mathbb {Z} _{p}~\,\!}$ есть секретные выборы, а выводится ${\displaystyle b~\,\!}$.

Мы соотносим стойкость BDDH относительно полу обобщённых алгоритмов со стойкостью известной решающей задачи Диффи-Хеллмана (DDH) и квадратичной решающей задачи Диффи-Хеллмана (SqDDH) над ${\displaystyle \mathbb {G} _{3}~\,\!}$. SqDDH потенциально проще чем DDH: Задаётся ${\displaystyle (g_{3},g_{3}^{x},g_{3}^{r_{b}})~\,\!}$, где ${\displaystyle x{\xleftarrow {\}}\mathbb {Z} _{p},b{\xleftarrow {\}}{0,1},r_{1}=x^{2}~\,\!}$, и ${\displaystyle r_{0}{\xleftarrow {\}}\mathbb {Z} _{p}~\,\!}$ есть секретные выборы, а выводится b. Наш результат обобщён в Теореме 2. Стоит отметить, что в отличие от вычислительных задач (таких как Со-DH) для решающих задач обычно требуется шаги уменьшения умножения. В данном доказательстве основная идея для DDH-шагов заключается в установлении билинейного набора и реализации новой концепции SqDDH-шагов. Т.к. DDH предположение сокращает SqDDH предположение [29] стойкость BDDH можно сформулировать только относительно SqDDH (Следствие 1).

Теорема 2. Предположим существует полу обобщённый алгоритм А решающий BDDH для набора группы Типа 1 за время ${\displaystyle t~\,\!}$ с вероятностью успеха ${\displaystyle e~\,\!}$. Тогда существует алгоритм ${\displaystyle B_{SqDDH}~\,\!}$ решающий SqDDH над ${\displaystyle \mathbb {G} _{3}~\,\!}$ за время ${\displaystyle t_{SqDDH}\approx t~\,\!}$ с алгоритмом ${\displaystyle B_{DDH}~\,\!}$ решающим DDH над ${\displaystyle \mathbb {G} _{3}~\,\!}$ за время ${\displaystyle t_{DDH}\approx t~\,\!}$ со средним значением ${\displaystyle e~\,\!}$ таким, что ${\displaystyle \epsilon \leq 3\epsilon _{DDH}+6\epsilon _{SqDDH}~\,\!}$.

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

Следствие 1. Если SqDDH является (e,t)-стойкой над ${\displaystyle \mathbb {G} _{3}~\,\!}$, то BDDH будет (9e,t)-стойкой для полу обобщённых алгоритмов.

Доказательство (Теоремы 2). Здесь мы покажем, что для полу обобщённого алгоритма «реальный» BDDH кортеж ${\displaystyle (g_{1},g_{1}^{x_{1}},g_{1}^{x_{2}},g_{1}^{x_{3}},g_{3}^{r_{1}}=g_{3}^{x_{1}x_{2}x_{3}})~\,\!}$ будет вычислительно неразличим то «случайного» кортежа ${\displaystyle (g_{1},g_{1}^{x_{1}},g_{1}^{x_{2}},g_{1}^{x_{3}},g_{3}^{r_{0}})~\,\!}$ если либо SqDDH либо DDH простые над ${\displaystyle \mathbb {G} _{3}~\,\!}$. Мы реализовываем это рассматривая несколько примеров приведённых для полу обобщённого алгоритма А и оракула О. Начнём с того, что А дан оракульный доступ к реальному BDDH кортежу. Т.к. идёт преобразование этого кортежа а также выходного значения оракула, то в конце мы получаем случайный кортеж. Можно показать, что если А различает по признакам два соответствующих примера ${\displaystyle \mathbb {G} _{i}~\,\!}$ и ${\displaystyle \mathbb {G} _{i-1}~\,\!}$, то он может использовать их для построения алгоритма решающего SqDDH или DDH.

Примеры показаны в Таблице 1. Каждый столбец с наименованием ${\displaystyle \mathbb {G} _{i}~\,\!}$ определяет (точно) вход над ${\displaystyle \mathbb {G} _{3}~\,\!}$ (см. Строку 1) либо выход ${\displaystyle BilinearMap~\,\!}$ в примере ${\displaystyle \mathbb {G} _{i}~\,\!}$ для всех возможных входных значений над ${\displaystyle \mathbb {G} _{1}~\,\!}$. Части изображённые жирным шрифтом показывают происходящие изменения относительно предыдущего примера. Вход в последней строке столбца ${\displaystyle \mathbb {G} _{i}~\,\!}$ выявляет какое предположение (SqDDH либо DDH) появиться в столбце, это означает, что данное значение будет добавлено к соответствующему примеру и оракул выберет ${\displaystyle x_{i}~\,\!}$ равномерно из ${\displaystyle \mathbb {Z} _{v}~\,\!}$.

Как можно заметить из таблицы, посредством ${\displaystyle \mathbb {G} _{2}~\,\!}$ мы убираем все квадраты ${\displaystyle x_{i}^{2}(1\leq i\leq 3)~\,\!}$ из выхода парного оракула. Мы выполняем это просто заменяя каждый квадрат на новое значение ${\displaystyle x_{j}(4\leq j\leq 6)~\,\!}$. Это преобразование называется (билинейным) SqDDG шагом и требуется для последовательных DDH шагов при выполнении в Примерах ${\displaystyle \mathbb {G} _{5}\mathbb {G} _{6}~\,\!}$ В процессе этих DDH шагов мы селективно убираем все произведения ${\displaystyle x_{i}x_{j}~\,\!}$ с помощью новых равномерных выбранных значений ${\displaystyle x_{j}(j\in {7,8})~\,\!}$. В примере ${\displaystyle \mathbb {G} _{6}~\,\!}$ равенство ${\displaystyle g_{3}^{r_{b}}=g_{3}^{x_{8}}~\,\!}$ независимо от входа, т.к. ${\displaystyle x_{8}~\,\!}$ нигде больше не встречается. После этого, в примере ${\displaystyle \mathbb {G} _{7}\mathbb {G} _{10}~\,\!}$ мы делаем обратные действия тем, что мы производили для BilinearMap входа при ${\displaystyle \mathbb {G} _{2}\mathbb {G} _{6}~\,\!}$ с инверсным порядком. Более точно, в ${\displaystyle \mathbb {G} _{6+j}~\,\!}$ мы сделаем всё инверсно относительно ${\displaystyle \mathbb {G} _{6-j}~\,\!}$ для ${\displaystyle 1\leq j\leq 4~\,\!}$ И наконец в ${\displaystyle \mathbb {G} _{1}0~\,\!}$ мы произведём реверсивные изменения (кроме одного в ${\displaystyle \mathbb {G} _{6}~\,\!}$). Этот последний пример соответствует ситуации, в которой А дан оракульный доступ к случайному BDDH кортежу. Если все начальные примеры вычислительно неразличимы по признакам (при SqDDH и DDH предположении), то несомненно также реальный кортеж BDDH будет вычислительно не различим от случайного кортежа, в соответствии с полу обобщёнными алгоритмами.

Для наглядности, давайте рассмотрим преобразование из ${\displaystyle \mathbb {G} _{1}~\,\!}$ в ${\displaystyle \mathbb {G} _{2}~\,\!}$ (SqDDH шаг) и из ${\displaystyle \mathbb {G} _{4}~\,\!}$ в ${\displaystyle \mathbb {G} _{5}~\,\!}$ (DDH шаг) для более детальных и количественных сокращений. Оракул ${\displaystyle O_{\mathbb {G} _{1}}~\,\!}$ в примере ${\displaystyle \mathbb {G} _{1}~\,\!}$ соответствует оригинальному полу обобщённому оракулу для BDDH предоставляющему доступ к реальному BDDH кортежу. Оракул в ${\displaystyle O_{\mathbb {G} _{2}}~\,\!}$ в ${\displaystyle \mathbb {G} _{2}~\,\!}$ эквивалентен ${\displaystyle O_{\mathbb {G} _{1}}~\,\!}$ за исключением следующих изменений: ${\displaystyle O_{\mathbb {G} _{2}}~\,\!}$ аддитивно выбирает ${\displaystyle x_{4}{\xleftarrow {\}}\mathbb {Z} _{p}~\,\!}$ и использует незначительную модификацию таблицы для расчёта парных выходных значений, как указано в Таблице 1. Положим, что А различает по признакам два примера за время t и с преимуществом

${\displaystyle \epsilon _{1}=Adv_{A}^{\mathbb {G} _{1},\mathbb {G} _{2}}=|Pr[1\leftarrow A^{O_{\mathbb {G} _{1}}}]-Pr[1\leftarrow A^{O_{\mathbb {G} _{2}}}]|~\,\!}$

Тогда из А мы можем построить алгоритм В для SqDDH. Опять же, мы можем использовать наблюдение говорящее, что полу обобщённые алгоритмы строятся в соответствии с ${\displaystyle \mathbb {G} _{1}~\,\!}$ и ${\displaystyle e~\,\!}$, и набором ${\displaystyle \mathbb {G} _{1}:=\mathbb {G} _{3}~\,\!}$ и ${\displaystyle e:\mathbb {G} _{3}\times \mathbb {G} _{3}\rightarrow \mathbb {G} _{3}~\,\!}$ Теперь пусть будет задан пример

${\displaystyle g_{3},g_{3}^{x_{1}},g_{3}^{r'_{b'}}={\begin{cases}g_{3}^{x_{1}^{2}},b'=1\\g_{3}^{x_{4}},b'=0\end{cases}}~\,\!}$

SqDDH задачи над ${\displaystyle \mathbb {G} _{3}~\,\!}$. В выбирает ${\displaystyle x_{2},x_{3}{\xleftarrow {\}}\mathbb {Z} _{p}~\,\!}$ Затем генерирует ${\displaystyle O_{\mathbb {G} _{1}}~\,\!}$ и ${\displaystyle O_{\mathbb {G} _{2}}~\,\!}$ как показано ниже (мы определяем ниже как групповые элементы вычисляются через ${\displaystyle x_{1},x_{1}^{2},x_{4}~\,\!}$ и ${\displaystyle b'~\,\!}$ неизвестные В):

• Список ${\displaystyle \varepsilon _{1}~\,\!}$ инициализируется с ${\displaystyle g_{3},g_{3}^{x_{1}},g_{3}^{x_{2}},g_{3}^{x_{3}}~\,\!}$. Над ${\displaystyle \mathbb {G} _{3}~\,\!}$ А задаёт ${\displaystyle g_{3},(g_{3}^{x_{1}})^{x_{2}x_{3}}~\,\!}$.
• Для генерации ${\displaystyle BilinearMap~\,\!}$ используем тот факт, что нам необходимо только знать выходные парные значения для всех возможных начальных входов. Эти элементы можно вычислить как показано в следующей таблице:

Легко заметить что если ${\displaystyle b'=1~\,\!}$, алгоритм В в точности ${\displaystyle O_{\mathbb {G} _{1}}~\,\!}$ и ${\displaystyle O_{\mathbb {G} _{2}}~\,\!}$ в противном случае. Т.о. просто используя выходное значение А, В решает пример SqDDH задачи с аналогичным преимуществом ${\displaystyle \epsilon _{1}~\,\!}$.

Теперь рассмотрим преобразование ${\displaystyle \mathbb {G} _{4}~\,\!}$ в ${\displaystyle \mathbb {G} _{5}~\,\!}$. Оракул ${\displaystyle O{\mathbb {G} _{5}}~\,\!}$ в ${\displaystyle \mathbb {G} _{5}~\,\!}$ совпадает с ${\displaystyle O_{\mathbb {G} _{4}}~\,\!}$ за исключением следующих изменений: ${\displaystyle O_{\mathbb {G} _{5}}~\,\!}$ аддитивно выбирает ${\displaystyle x_{7}{\xleftarrow {\}}\mathbb {Z} _{p}~\,\!}$ и использует модифицированную таблицу для расчёта парных выходов как показано в Таблице 1. Предположим, А различает по признакам два примера за время t с преимуществом ${\displaystyle \epsilon _{4}=Adv_{A}^{\mathbb {G} _{4},\mathbb {G} _{5}}~\,\!}$. Тогда мы можем использовать А для построения алгоритма В для DDH. Задаётся пример

${\displaystyle g_{3},g_{3}^{x_{1}},g_{3}^{x_{2}},g_{3}^{r'_{b'}}={\begin{cases}g_{3}^{x_{1}^{2}},b'=1\\g_{3}^{x_{7}},b'=0\end{cases}}~\,\!}$

DDH над ${\displaystyle \mathbb {G} _{3}~\,\!}$ , где В выбирает ${\displaystyle x_{3},x_{4},x_{5},x_{6}{\xleftarrow {\}}\mathbb {Z} _{p}~\,\!}$ и генерирует ${\displaystyle O_{\mathbb {G} _{5}}~\,\!}$ и ${\displaystyle O_{\mathbb {G} _{6}}~\,\!}$:

• Список ${\displaystyle \varepsilon _{1}~\,\!}$ инициализируется с ${\displaystyle g_{3},g_{3}^{x_{1}},g_{3}^{x_{2}},g_{3}^{x_{3}}~\,\!}$. Над ${\displaystyle \mathbb {G} _{3}~\,\!}$ А задаёт ${\displaystyle g_{3},(g_{3}^{r'_{b'}})^{x_{3}}~\,\!}$.
• Для генерации BilinearMap используем следующую таблицу выходных парных значений:

Если ${\displaystyle b'=1~\,\!}$, В ведёт себя как ${\displaystyle O_{\mathbb {G} _{4}}~\,\!}$, тогда как если ${\displaystyle b'=0~\,\!}$, то он ведёт себя как ${\displaystyle O_{\mathbb {G} _{5}}~\,\!}$. Оперируя выходом А, В решает пример DDH задачи с преимуществом ${\displaystyle \epsilon _{4}~\,\!}$.

Оценка ${\displaystyle \epsilon ~\,\!}$ будет следующего вида ${\displaystyle \epsilon \leq \sum _{i=1}^{9}{\epsilon _{i}}~\,\!}$, где ${\displaystyle \epsilon _{i}=Adv_{A}^{\mathbb {G} _{i}\mathbb {G} _{i+1}}~\,\!}$, и набор ${\displaystyle \epsilon _{SqDDH}=max_{i\in {1,2,3,7,8,9}}(\epsilon _{i}),\epsilon _{DDH}=max_{i\in {4,5,6}}(\epsilon _{i})~\,\!}$.

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

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

Обобщенные задачи основанные на парных вычислениях. Пусть наборы Типа 1,2 и 3 будут заданы согласно Определению 1. Более того, пусть ${\displaystyle l\in \mathbb {N} ,d\in {1,2,3}~\,\!}$ будут положительными целыми числами, ${\displaystyle I_{1},I_{2},I_{3}\subset \mathbb {Z} _{p}[X_{1},...,X_{l}]~\,\!}$ будут конечными наборами (открытых) полиномов (называемых входными полиномами) и ${\displaystyle Q\in \mathbb {Z} _{p}[X_{1},...,X_{l}]~\,\!}$ будет простым полиномом. Тогда определим ${\displaystyle (I_{1},I_{2},I_{3},Q)-BDH_{\mathbb {G} _{d}}~\,\!}$ задачу как:

${\displaystyle ((g_{1}^{R_{(x)}})_{R\in I_{1}},(g_{2}^{R_{(x)}})_{R\in I_{2}},(g_{3}^{R_{(x)}})_{R\in I_{3}})~\,\!}$,

где ${\displaystyle x{\xleftarrow {\}}\mathbb {Z} _{p}^{l}~\,\!}$ это секретные случайные значения, и выводится ${\displaystyle g_{d}^{Q_{(x)}}~\,\!}$. Решительный вариант такой задачи можно определить аналогично. В дальнейшем мы всегда полагаем, что полином 1 содержится в каждом ${\displaystyle I_{i}~\,\!}$, что соответствует основному предположению, что каждая группа генераторов задаётся изначально.

Говоря более простыми словами, ${\displaystyle (I_{1},I_{2},I_{3},Q)-BDH_{\mathbb {G} _{d}}~\,\!}$ задача не тривиальна если не существует способа вычислить Q при помощи только лишь входных полиномов и операций над ними, которые задаются соответствующим билинейным набором. Давайте рассмотрим случай ${\displaystyle d\in {1,2}~\,\!}$. Пусть ${\displaystyle I_{1}={R_{1},...,R_{t}}~\,\!}$ и ${\displaystyle I_{2}={S_{1},...,S_{t}^{'}}~\,\!}$ Тогда применяя Наблюдение 2 (раздел 2.1), можно заметить, что выход ${\displaystyle [c]_{d}~\,\!}$ полу обобщённого алгоритма для соответствующих задач можно записать как ${\displaystyle g_{d}^{P(x)}~\,\!}$ для некоторого Р вида (1):

${\displaystyle P={\begin{cases}\sum _{j=1}^{t}{z_{j}R_{j}},d=1\\\sum _{j=1}^{t'}{z_{j}^{'}S_{j}},d=2andType3setting\\\sum _{j=1}^{t}{z_{j}R_{j}}+\sum _{j=1}^{t'}{z_{j}^{'}S_{j}},d=2andType2setting\end{cases}}~\,\!}$

 Не переведено:

We call a ${\displaystyle (I_{1},I_{2},I_{3},Q)-BDH_{\mathbb {G} _{d}}~\,\!}$ non-trivial if there is no P of the above form such that ${\displaystyle g_{d}^{P(x)}=g_{d}^{Q(x)}forallz\in \mathbb {Z} _{p}^{l},i.e.,ifP\neq Q\in \mathbb {Z} _{p}[X_{1},...,X_{l}]~\,\!}$. More formal and general definitions can be found in the full version of this paper [30].

Упрощения для Обобщённых задач. Теорема 3 содержит упрощение, которое мы применили для Со-DH в Разделе 3.1 для более общих классов ${\displaystyle (I_{1},I_{2},I_{3},Q)-BDH_{\mathbb {G} _{d}}~\,\!}$ задач. Основное отличие будет в методе для выполнения расчёта дискретного логарифма заданного выходом полу обобщённого алгоритма.

Теорема 3. Пусть ${\displaystyle d\in {1,2}~\,\!}$ и ${\displaystyle (I_{1},I_{2},I_{3},Q)-BDH_{\mathbb {G} _{d}}~\,\!}$ будут нетривиальной задачей с входными полиномами ${\displaystyle \mathbb {Z} _{p}[X_{1},...,X_{l}]~\,\!}$. Пусть ${\displaystyle k=max_{i}(deg_{X_{i}}(I_{1}\cup I_{2}\cup I_{3}))~\,\!}$ Предположим, что ${\displaystyle (I_{1},I_{2},I_{3},Q)-BDH_{\mathbb {G} _{d}}~\,\!}$ есть полу обобщённый алгоритм А решающий за время t с вероятностью успеха ${\displaystyle \epsilon ~\,\!}$. Тогда существует алгоритм В решающий 2k-DL в ${\displaystyle \mathbb {G} _{3}~\,\!}$ за время ${\displaystyle t'\approx t+O(k'logp)~\,\!}$, где ${\displaystyle k'=max(k,deg(Q))~\,\!}$, с вероятностью ${\displaystyle \epsilon '\geq {\frac {\epsilon }{l}}~\,\!}$.

Доказательство. Пусть ${\displaystyle k_{1}=2k~\,\!}$. В принимает на входе ${\displaystyle k_{1}-DLchallengea_{0}=g_{3},a_{1}=g_{3}^{x^{1}},...,a_{k_{1}}=g_{3}^{x^{k_{1}}}~\,\!}$ Затем выбирается ${\displaystyle i^{*}{\xleftarrow {\}}{1,...,l}~\,\!}$ и ${\displaystyle x_{1},...,x_{i^{*}-1},x_{i^{*}+1},...,x_{l}{\xleftarrow {\}}\mathbb {Z} _{p}~\,\!}$ Неизвестное х рассматривается как секретный выбор ${\displaystyle x_{i^{*}}~\,\!}$ в контексте примера ${\displaystyle (I_{1},I_{2},I_{3},Q)-BDH_{\mathbb {G} _{d}}~\,\!}$. Мы отметим только важные составляющие процесса генерации полу обобщённого оракула: Каждый начальный список ${\displaystyle \varepsilon _{j}~\,\!}$ инициализируется с элементами ${\displaystyle (g_{3}^{P(x)})_{P\in I_{j}}~\,\!}$, где для полинома ${\displaystyle P=\sum _{e=(e_{1},...,e_{l})\in E}{b_{e}X_{1}^{e_{1}}...X_{l}^{e_{l}}},E\subset \mathbb {Z} _{p}^{l}~\,\!}$, элемент ${\displaystyle g_{3}^{P(x)}~\,\!}$ можно рассчитать как ${\displaystyle g_{3}^{P(x)}=\prod _{e}a_{e_{i^{*}}^{b_{e}\prod _{s\neq i^{*}}x_{S}^{e_{l}}}}~\,\!}$ используя данный пример для ${\displaystyle k_{1}-DL~\,\!}$ задачи. Это возможно т.к. степень ${\displaystyle X_{i^{*}}~\,\!}$ полиномиальна для каждого набора ${\displaystyle I_{j}~\,\!}$ и ограничена сверху по ${\displaystyle k_{1}~\,\!}$.

 Не переведено:

Similarly, the table for simulating BilinearMap can be created since for each entry gP(x) 3 in this table, P is again of degree at most k1 in Xi∗ . Given an (I1, I2, I3,Q)-BDHGd instance, A eventually outputs an index [c]d. Then c can be written as gP(x) 3 for some known polynomial P as described in Equation 1. Thus, A wins if Q(x) ≡ P(x) mod p.

Т.к. ${\displaystyle Z:=Q-P~\,\!}$ не нулевой модуль ${\displaystyle p~\,\!}$ (задача не тривиальна) успех данного события можно разбить на два независимых события ${\displaystyle S_{1},...,S_{l}~\,\!}$ где ${\displaystyle S_{j}~\,\!}$ определяется как (2):

${\displaystyle Z(X_{1}=x_{1},...,X_{j-1}=x_{j-1})\not \equiv 0andZ(X_{1}=x_{1},...,X_{j}=x_{j})\equiv 0~\,\!}$

Выражая вероятность события ${\displaystyle S_{j}~\,\!}$ через ${\displaystyle \alpha _{j}~\,\!}$ получаем ${\displaystyle \epsilon =\alpha _{1}+...+\alpha _{l}~\,\!}$.

Теперь предположим, что есть ещё событие ${\displaystyle S_{i^{*}}~\,\!}$, которое происходит с вероятностью ${\displaystyle \epsilon /l~\,\!}$. Рассмотрим полином ${\displaystyle Z_{i^{*}}=Z(X_{1}=x_{1},...,X_{i^{*}-1}=x_{i^{*}-1})modp\in \mathbb {Z} _{p}[X_{i^{*}},...,X_{l}]~\,\!}$. Этот полином будет вида ${\displaystyle Z_{i^{*}}=\sum _{e=(e_{i^{*}},...,e_{l})\in E}{b_{e}X_{i^{*}}^{e_{i^{*}}}...X_{l}^{e_{l}}}~\,\!}$ для некоторого ${\displaystyle E\subset \mathbb {Z} _{p}^{l-i^{*}+1}~\,\!}$ где хотя бы один одночлен переменной ${\displaystyle X_{i^{*}}~\,\!}$ встречается с ненулевой экспонентой ${\displaystyle e_{i^{*}}~\,\!}$. Пусть ${\displaystyle M=b'_{e}X_{i^{*}}^{e'_{i^{*}}}...X_{l}^{e'_{l}}~\,\!}$ будет одним из этих одночленов. Тогда рассмотрим полином ${\displaystyle Z'_{i^{*}}~\,\!}$ и получим сумму всех одночленов ${\displaystyle Z_{i^{*}}~\,\!}$ содержащих субодночлен ${\displaystyle X_{i^{*}+1}^{e'_{i^{*}+1}}...X_{l}^{e'_{l}}:~\,\!}$

${\displaystyle Z'_{i^{*}}=\sum _{e=(e_{i^{*}},...,e_{l})\in E,e_{i^{*}+1}=e'_{i^{*}+1},...,e_{l}=e'_{l}}{b_{e}X_{i^{*}}^{e_{i^{*}}}X_{i^{*}}^{e'_{i^{*}}}....X_{l}^{e'_{l}}}~\,\!}$

Получаем ${\displaystyle Z'_{i^{*}}\not \equiv 0modp~\,\!}$ и т.к. ${\displaystyle Z_{i^{*}}(X_{i^{*}}=x_{i^{*}})\equiv 0modp~\,\!}$ также выполняется и ${\displaystyle Z'_{i^{*}}(X_{i^{*}}=x_{i^{*}})\equiv 0modp~\,\!}$. Следовательно, ${\displaystyle x_{i^{*}}=x~\,\!}$ есть корень ненулевого инвариантного полинома

${\displaystyle Z''_{i^{*}}=\sum _{e=(e_{i^{*}},...,e_{l})\in E,e_{i^{*}+1}=e'_{i^{*}+1},...,e_{l}=e'_{l}}{b_{e}X_{i^{*}}^{e_{i^{*}}}}~\,\!}$

Отметим, что Алгоритм В может легко построить полином ${\displaystyle Z''_{i^{*}}~\,\!}$ с помощью выбора переменного одночлена из ${\displaystyle Z_{i^{*}}~\,\!}$ для которого ${\displaystyle X_{i^{*}}~\,\!}$ встречается с ненулевой степенью. Коэффициенты ${\displaystyle b_{e}~\,\!}$ можно также просто рассчитать т.к. коэффициенты ${\displaystyle Z~\,\!}$ известны, а ${\displaystyle x_{1},...,x_{i^{*}-1}~\,\!}$ выбираются В. Т.о. применяя эффективный стандартный алгоритм для вычисления корней полиномов над ${\displaystyle \mathbb {Z} _{p}~\,\!}$ таких как [31], В может найти желаемый DL ${\displaystyle x_{i^{*}}=x~\,\!}$ путём расчёта всех корней полинома ${\displaystyle Z''_{i^{*}}~\,\!}$. Это приведёт максимум ${\displaystyle k'=max(k,deg(Q))~\,\!}$ различных корней вычислимых за время ${\displaystyle O(k'logp)~\,\!}$ [31]. Эквивалентность ${\displaystyle x'~\,\!}$ и ${\displaystyle x~\,\!}$ можно проверить путём выявления корректно ли ${\displaystyle g^{x'}{\xleftarrow {?}}a_{1}~\,\!}$.

Мы также можем найти упрощение для общего класса решающих задач, которые эффективны виртуально для всех задач рассматриваемых практически. В особенности, наше упрощение из SqDHH задачи над ${\displaystyle \mathbb {G} _{3}~\,\!}$ работает для всех ${\displaystyle (I_{1},I_{2},I_{3},Q)-BDDH_{\mathbb {G} _{3}}~\,\!}$ задач где переменные в ${\displaystyle I_{1}\cup I_{2}andI_{3}\cup {Q}~\,\!}$ появляются в большинстве своём с квадратичной степенью, соответственно. Наш подход для общего упрощения отличается от BDDH показанного в Разделе 3.2 следующим: BDDH упрощение явное в том плане, что все упрощающие шаги будут конкретно в полу обобщённой модели. В этом случае, можно сперва получить BDDH для группы с помощью нахождения «соответствующей» задачи, которая упрощает на первом шаге BDDH (при соответствующих полу обобщённых алгоритмах) и затем реализовать DDH и SqDDH шаги упрощения для данной задачи в стандартной модели. Мы следуем данной методике в нашем доказательстве для общих билинейных решающих задач т.к. она обладает преимуществом заимствованным у Брессона и др. для результатов обобщённых DDH задач [25] в стандартной модели. Однако, это не так уж и просто реализовать. Т.к. их результат достаточно упрощён нам необходимо расширить его для большего числа классов задач. Для более детального описания данного вопроса обращайтесь к полной версии работы [30].

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

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

BLS схема подписи для билинейного набора Типа 1 определяется следующим образом. Пусть ${\displaystyle H_{1}~\,\!}$ есть хэш функция ${\displaystyle H_{1}:{0,1}^{l}\rightarrow \mathbb {G} _{1}~\,\!}$.

• ${\displaystyle Gen~\,\!}$ выявляет случайный генератор ${\displaystyle gof\mathbb {G} _{1},s{\xleftarrow {\}}\mathbb {Z} _{p}~\,\!}$ и устанавливает ${\displaystyle pk=(g,g^{S}),sk=s~\,\!}$
• ${\displaystyle Sign(sk,m)~\,\!}$ вычисляет ${\displaystyle H_{1}(m)~\,\!}$ и возвращает ${\displaystyle \sigma =H_{1}(m)^{S}~\,\!}$
• ${\displaystyle Verify(pk,m,\sigma )~\,\!}$ возвращает 1, если ${\displaystyle e(H_{1}(m),pk)=e(\sigma ,g)~\,\!}$ и 0 в противном случае.

Давайте теперь рассмотрим EUF-CMA эксперимент по безопасности для BLS схемы подписи в SGGM. Здесь мы сталкиваемся с технической проблемой: BLS схема убирает хэш функцию ${\displaystyle H_{1}:{0,1}^{l}\rightarrow \mathbb {G} _{1}~\,\!}$ т.е. выходом данного отображения будет групповой элемент в некотором заданном представлении. Однако, в SGGM мы хотим рассмотреть алгоритмы, которые независимы от частных представлений элементов ${\displaystyle \mathbb {G} _{1}~\,\!}$. Т.к. в нашей модели элементы задаются списком индексов, то получается, что нету таких представлений групповых элементов, которые мы бы могли использовать для определения хэш функции.

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

Определение 2. Групповая хэш функция является парным алгоритмом ${\displaystyle H=(GHGen,GHEval)~\,\!}$.

• GHGen принимает на входе генератор ${\displaystyle g\in \mathbb {G} _{1}~\,\!}$ и возвращает ${\displaystyle A=(a_{1},...,a_{\delta })\in \mathbb {G} _{1}^{\delta }~\,\!}$. Вектор А определяет функцию ${\displaystyle H_{1}:{0,1}^{l}\rightarrow \mathbb {G} _{1}~\,\!}$.
• Алгоритм GHEval принимает на вход вектор ${\displaystyle A\in \mathbb {G} _{1}^{\delta }~\,\!}$ и строку ${\displaystyle m\in {0,1}^{l}~\,\!}$, а возвращает ${\displaystyle H_{1}(m)\in \mathbb {G} _{1}~\,\!}$.

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

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

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

• TrapGen принимает на входе генератор ${\displaystyle g\in \mathbb {G} _{1}~\,\!}$. Возвращает вектор ${\displaystyle A\in \mathbb {G} _{1}^{\delta }~\,\!}$, распределённый идентично выходу GHGen для всех ${\displaystyle g~\,\!}$ и некоторой информации ${\displaystyle td~\,\!}$, подвергнутой утечке по «лазейке».
• Алгоритм TrapEval принимает на вход вектор ${\displaystyle A\in \mathbb {G} _{1}^{\delta }~\,\!}$ и строку ${\displaystyle m\in {0,1}^{l}~\,\!}$, а возвращает ${\displaystyle h~\,\!}$ такой, что ${\displaystyle g^{h}=H_{1}(m)~\,\!}$.

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

Определение 3. Групповая функция будет стойкой от ${\displaystyle (e,t,q)~\,\!}$-алгебраической коллизии, если

${\displaystyle Pr[A(A)=(m_{0},...,m_{q},i_{0},...,i_{q}):H_{1}(m_{0})=g^{i_{0}}\prod _{k=1}^{q}(H_{1}(m_{j}))^{i_{j}}]\leq \epsilon ~\,\!}$

для всех алгоритмов ${\displaystyle A~\,\!}$ выполняющихся за время ${\displaystyle t~\,\!}$.

При применении методики из [37] возможно построение хэш функции удовлетворяющей данному свойству при слабых предположениях, таких как стойкость вычисления дискретных логарифмов в ${\displaystyle \mathbb {G} _{1}~\,\!}$, для любой константы ${\displaystyle q~\,\!}$. Основным недочётом, однако, будет то, что для этих конструкций размер вектора А растёт линейно относительно q. Это насущный вопрос требующий дальнейшего анализа и выявления такая групповая хэш функция с лазейкой, для которой размер будет постоянным и ${\displaystyle q=q(k)~\,\!}$ будет полиномиальным.

Обобщим EUF-CMA эксперимент в SGGM следующим образом. В начале примера, получим значения для случайного генератора ${\displaystyle g~\,\!}$ и секретного ключа ${\displaystyle x~\,\!}$. Затем выполним ${\displaystyle (a_{1},...,a_{\delta }){\xleftarrow {\}}GHGen(g),setsI_{1}:=(g,g^{x},a_{1},...,a_{\delta })~\,\!}$, и установим , а также реализуем полу обобщённый оракул со входом I1 как показано в Разделе 2. Это предоставит злоумышленнику открытый ключ, и возможность выполнять групповые операции на элементах ${\displaystyle \mathbb {G} _{1}~\,\!}$.

Когда злоумышленник запрашивает подпись какого-либо выбранного сообщения ${\displaystyle m_{i}~\,\!}$, участник вычисляет ${\displaystyle H(m_{i})^{x}~\,\!}$ и добавляет его в список ${\displaystyle \varepsilon _{1}~\,\!}$.

Мы утверждаем, что злоумышленник выигрывает, если он выводит сообщение ${\displaystyle m~\,\!}$ и индекс ${\displaystyle [s]_{1}~\,\!}$ такое, что ${\displaystyle s=H(m)^{x}~\,\!}$ т.е., злоумышленнику нужно вычислить корректную подпись для ${\displaystyle m~\,\!}$. Мы говорим, что полу обобщённый злоумышленник ${\displaystyle A(\epsilon ,t)-~\,\!}$взламывает EUF-CMA безопасность схемы подписи если ${\displaystyle A~\,\!}$ работает за время ${\displaystyle t~\,\!}$ и ${\displaystyle Pr[Awins]\geq \epsilon ~\,\!}$.

Теорема 4. Предположим существует злоумышленник ${\displaystyle A(e,t)~\,\!}$ взламывающий EUF-CMA безопасность BLS схемы подписи в полу обобщённой модели с помощью q запросов подписи для выбранных сообщений. Тогда существует алгоритм ${\displaystyle B_{coll}(\epsilon _{dl},t_{dl},q)~\,\!}$ взлома стойкости алгебраической коллизии ${\displaystyle H_{1}~\,\!}$ и алгоритм ${\displaystyle B_{dl}(\epsilon _{dl},t_{dl})~\,\!}$ решающий дискретную логарифмическую задачу в ${\displaystyle \mathbb {G} _{1}~\,\!}$ такие, что ${\displaystyle t\approx t_{coll}\approx t_{dl}~\,\!}$ и ${\displaystyle \epsilon \leq \epsilon _{coll}+\epsilon _{dl}~\,\!}$.

Доказательство. Предположим существует такой злоумышленник ${\displaystyle A~\,\!}$ который выводит сообщение ${\displaystyle m~\,\!}$ и индекс ${\displaystyle [s]_{1}~\,\!}$ такие, что ${\displaystyle s=H(m)^{x}~\,\!}$ В SGGM злоумышленнику необходимо вычислить групповой элемент ${\displaystyle \mathbb {G} _{1}~\,\!}$ с помощью применения последовательности групповых операций для начальных значений ${\displaystyle (g,g^{x},a_{1},...,a_{\delta })~\,\!}$ хранящихся в ${\displaystyle \varepsilon _{1}~\,\!}$ и для групповых элементов добавленных в список оракулом при ответе на запросы подписи выбранного сообщения. Т.о. когда А выводит ${\displaystyle (m,[a]_{1})~\,\!}$ такое, что ${\displaystyle s=H(m)^{x}~\,\!}$, то оракул получает уравнение (3)

${\displaystyle H(m)^{x}=g^{\alpha _{1}}\cdot (g^{x})^{\alpha _{2}}\cdot \prod _{i=1}^{\delta }a_{i}^{\beta _{i}}\cdot \prod _{i=1}^{q}(H(m_{i})^{x})^{\gamma _{i}}~\,\!}$

или ${\displaystyle x\cdot (log_{g}H(m))-\sum _{i=1}^{q}{\gamma _{i}log_{g}H(m_{i})-\alpha _{2})}=\alpha _{1}+\sum _{i=1}^{\delta }{\beta _{i}log_{g}a_{i}}~\,\!}$ для целых известных ${\displaystyle \alpha _{i},\beta _{i},\gamma _{i}~\,\!}$ оракулу. Рассмотрим два типа ложных значений:

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

${\displaystyle log_{g}H(m)-\sum _{i=1}^{q}{\gamma _{i}}log_{g}H(m_{i})-\alpha _{2}\approx 0modp~\,\!}$

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

${\displaystyle log_{g}H(m)-\sum _{i=1}^{q}\gamma _{i}log_{g}H(m_{i})-\alpha _{2}\not \approx 0modp~\,\!}$

Лемма 1. Предположим существует ложное значении Типа-А для ${\displaystyle A(\epsilon ,t)~\,\!}$ взламывающего EUF-CMA безопасность BLS схемы подписи с помощью выполнения максимум q запросов выбранного сообщения. Тогда существует алгоритм ${\displaystyle B_{coll}(\epsilon _{dl},t_{dl},q)~\,\!}$ взламывающий стойкость алгебраической коллизии (GHGen,GHEval) за время ${\displaystyle t'\approx t~\,\!}$ с вероятностью успеха ${\displaystyle \epsilon _{coll}\geq \epsilon ~\,\!}$.

Доказательство. Алгоритм ${\displaystyle B_{coll}~\,\!}$ получает на входе вектор ${\displaystyle A'=(g',a'_{1},...,a'_{\delta })~\,\!}$. Он работает в точности как полу обобщённый EUF-CMA участник, за исключением тогo, что устанавливаются ${\displaystyle g:=g'~\,\!}$ и ${\displaystyle a_{i}:=a'_{i}~\,\!}$ вместо получения g случайным образом и генерации А с помощью выполнения ${\displaystyle GHGen(g)~\,\!}$. Т.о. в частности ${\displaystyle B_{coll}~\,\!}$ выбирает секретный ключ ${\displaystyle x{\xleftarrow {\}}\mathbb {Z} ~\,\!}$, что позволяет ему сгенерировать изначальную работу участника.

Когда А выводит ${\displaystyle (m,[s]_{1})~\,\!}$ такое, что ${\displaystyle s=H(m)^{x}~\,\!}$, то ${\displaystyle B_{coll}~\,\!}$ вычисляет и возвращает целые ${\displaystyle (\alpha _{2},\gamma _{1},...,\gamma _{q})~\,\!}$ как в Уравнении 4. Заметим, что если Уравнение 4 удовлетворяется, то получаем ${\displaystyle H(m)=q^{\alpha _{2}}\cdot \prod _{i=1}^{1}H(m_{i})^{\gamma _{i}}~\,\!}$.

Лемма 2. Предположим существует ложное значении Типа-В для ${\displaystyle A(\epsilon ,t)~\,\!}$ взламывающего EUF-CMA безопасность BLS схемы подписи. Тогда существует алгоритм ${\displaystyle B_{dl}~\,\!}$ задачу дискретного логарифма в ${\displaystyle \mathbb {G} _{1}~\,\!}$ за время ${\displaystyle t_{dl}\approx t~\,\!}$ с вероятностью успеха ${\displaystyle \epsilon _{dl}\geq \epsilon ~\,\!}$.

Доказательство. Алгоритм ${\displaystyle B_{dl}~\,\!}$ получает на входе кортеж ${\displaystyle (g',y)~\,\!}$. Он устанавливает ${\displaystyle g:=g',g^{x}:=y~\,\!}$ и выполняет ${\displaystyle (A,td){\xleftarrow {\}}TrapGen(g)~\,\!}$ для генерации открытых параметров хэш функции. Заметим, что А распределён идентично некоторому ${\displaystyle A'~\,\!}$ сгенерированному с помощью GHGen. Устанавливается ${\displaystyle I_{1}:=(g,g^{x},a_{1},...,a_{\delta })~\,\!}$ и реализуется полу обобщённый оракул с начальным списком состояний ${\displaystyle I_{1}~\,\!}$.

Т.к. ${\displaystyle B_{dl}~\,\!}$ не известен экспонента секретного ключа ${\displaystyle x~\,\!}$, он отвечает на запросы подписи выбранного сообщения А по-разному. ${\displaystyle B_{dl}~\,\!}$ также пользуется информацией полученной из «лазейки» ${\displaystyle td~\,\!}$ генерируемой аналогично с А. Всякий раз, когда А утверждает выбранное сообщение ${\displaystyle m_{i},B_{dl}~\,\!}$ вычисляет ${\displaystyle h_{i}=TrapEval(m_{i})~\,\!}$ и добавляет ${\displaystyle y^{h_{i}}~\,\!}$ в ${\displaystyle \varepsilon _{1}~\,\!}$ Отметим, что ${\displaystyle y^{h_{i}}=g^{xlog_{g}H(m_{i})}=H(m_{i})^{x}~\,\!}$ т.о. получается корректная подпись.

Когда А выводит ${\displaystyle (m,[s]_{1})~\,\!}$ такое, что ${\displaystyle s=H(m)^{x}~\,\!}$, то ${\displaystyle B_{dl}~\,\!}$ вычисялет целые значения ${\displaystyle (\alpha _{i},\beta _{i},\gamma _{i})~\,\!}$ как в Уравнении 3 и возвращает

${\displaystyle x=log_{g'}y={\frac {\alpha _{1}+\sum _{i=1}^{\delta }\beta _{i}log_{q}a_{i}}{log_{g}H(m)-\sum _{i=1}^{q}\gamma _{i}log_{g}H(m_{i})-\alpha _{2}}}modp~\,\!}$

что возможно т.к. ${\displaystyle log_g H(m) - \sum^{й}_{i=1} \gamma_i log_g H(m_i) - \alpha_2 \ne 0 mod p ~\,\!}$

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

## Литература

Cite error: <ref> tags exist for a group named "@:", but no corresponding <references group="@:"/> tag was found, or a closing </ref> is missing
1. 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. 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. 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. 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. 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. Boneh, D., Lynn, B., Shacham, H.: Short signatures from the Weil pairing. J. Cryptology 17(4), 297–319 (2004)
13. 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. 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. 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. 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. 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. 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. 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)