50 lines
3.9 KiB
TeX
50 lines
3.9 KiB
TeX
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


% \section{PairingBased Cryptography} %


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%




Pairingbased cryptography was introduced by Sakai, Ohgishi and Kasahara~\cite{SOK00} to generalize DiffieHellman key exchange to three users in one round.


Since then, many constructions have been proposed for cryptographic constructions, such as identitybased encryption~\cite{BF01,Wat05} or group signatures~\cite{BBS04}.


Multiple constructions and parameter sets coexist for pairings.


Realworld implementation are based on elliptic curves~\cite{BN06, KSS08}, but recent advances in cryptanalysis requires to reassess the security level of pairingbased cryptography~\cite{KB16,MSS17,BD18}.




In the following, we adopt blackbox definitions of cryptographic pairings as bilinear maps, and on the assumed hardness of classical constantsize assumptions over pairingfriendly groups, namely $\SXDH$ and $\SDL$.


The notations $1_{\GG}^{}$, $1_{\Gh}^{}$ and $1_{\GT}^{}$ denote the identity elements in $\GG$, $\Gh$ and $\GT$ respectively.




\begin{restatable}[Pairings~\cite{BSS05}]{definition}{defPairings} \label{de:pairings} \index{Pairings}


A pairing is a map $e: \GG \times \Gh \to \GT$ over cyclic groups of order $p$ that verifies the following properties for any $g \in \GG, \hat{g} \in \Gh$:


\begin{enumerate}[\quad (i)]


\item bilinearity: for any $a, b \in \Zp$, we have $e(g^a, \hat{g}^b) = e(g^b, \hat{g}^a) = e(g, \hat{g})^{ab}$.


\item nondegeneracy: $e(g,\hat{g}) = 1_{\GT} \iff g = 1_{\GG}$ or $\hat{g} = 1_{\Gh}$.


\item the map is computable in polynomial time in the size of the input.


\end{enumerate}


\end{restatable}




For cryptographic purposes, pairings are usually defined over elliptic curves, hence $\GT$ is a multiplicative subgroup of the multiplicative group of a finite field.




The most standard assumptions over pairings are derived from the equivalent of the DiffieHellman assumptions from cyclic groups,


described in \cref{de:DDH}.


This hypothesis is used to defined the $\SXDH$ assumption~\cite{Sco02} as follows.




\begin{restatable}[{$\SXDH$~\cite[As.~1]{BGdMM05}}]{definition}{defSXDH} \index{Pairings!SXDH} \label{de:SXDH}


The \emph{Symmetric eXternal DiffieHellman} ($\SXDH$) assumption holds if the $\DDH$ assumption holds both in $\GG$ and $\Gh$.


\end{restatable}




The advantages of the best $\ppt$ adversary against $\DDH$ in group $\GG$ and $\Gh$ are written $\advantage{\DDH}{\GG}$ and $\advantage{\DDH}{\Gh}$ respectively. Both of those quantities are assumed negligible under the $\SXDH$ assumption.




In \cref{ch:sigmasig}, the security of our group signature scheme relies on the $\SXDH$ assumption, which is a wellstudied assumption.


Moreover, this assumption is static, meaning that the size of the assumption is independent of the number of queries made py the adversary or any feature (e.g., the maximal number of users) of the system, and is noninteractive, in the sense that it does not involve any oracle.




This gives us stronger confidence in the security of schemes proven under this kind of assumptions.


For instance, Cheon gave an attack against the $q$Strong DiffieHellmann problem for large values of $q$~\cite{Che06} (which usually represents the number of adversarial queries).




In \cref{ch:sigmasig}, we also rely on the following assumption, which generalizes the Discrete Logarithm problem to asymmetric groups.




\begin{restatable}[$\SDL$]{definition}{defSDL}


\label{de:SDL} \index{Pairings!SDL}


In bilinear groups $\bigl(\GG,\Gh,\GT^{}\bigr)$ of prime order $p$, the \emph {Symmetric Discrete Logarithm} ($\SDL$) problem consists in, given


$\bigl(g,\hat{g},g^a_{},\hat{g}^a_{}\bigr) \in \bigl(\GG \times \Gh\bigr)^2_{}$


where $a \sample \ZZ_p^{}$, computing $a \in \ZZ_p^{}$.


\end{restatable}




Like $\SXDH$, this assumption is also static (i.e., constantsize) and noninteractive.
