Bilinear map assumptions

Bilinear map (pairing) assumptions concern the computational hardness of certain problems in groups ${\mathbb{G}}_1,{\mathbb{G}}_2,{\mathbb{G}}_T$ equipped with a bilinear pairing $e:{\mathbb{G}}_1\times {\mathbb{G}}_2\to {\mathbb{G}}_T$, where $e(g_1^a,g_2^b)=e(g_1,g_2{)}^{ab}$ for generators $g_i$.

Assumption

Bilinear Diffie-Hellman (BDH): Given $(g,g^a,g^b,g^c)\in {\mathbb{G}}^4$ for a symmetric pairing group $e:\mathbb{G}\times \mathbb{G}\to {\mathbb{G}}_T$, compute $e(g,g{)}^{abc}\in {\mathbb{G}}_T$.

$${\mathbf{Adv}}_{\mathcal{A}}^{\mathrm{bdh}}(\lambda ):=\mathrm{Pr}\left[\mathcal{A}(1^{\lambda },g,g^a,g^b,g^c)=e(g,g{)}^{abc}\right]$$

is negligible for uniform $a,b,c\stackrel{\$}{\leftarrow }{\mathbb{Z}}_q$.

Decisional BDH

Decisional BDH (DBDH / BDDH): Distinguish $(g,g^a,g^b,g^c,e(g,g{)}^{abc})$ from $(g,g^a,g^b,g^c,e(g,g{)}^r)$ for random $r\stackrel{\$}{\leftarrow }{\mathbb{Z}}_q$.

Known Results

• DBDH + DLIN ⇒ IBE
• co-CDH ⇒ BLS signatures
• k-Lin ⇒ VRF
• BDH ⇒ CDH: a CDH solver gives $g^{ab}$, and $e(g^{ab},g^c)=e(g,g{)}^{abc}$ — BF01
• DLIN ⇒ NIZK
• Quantum computers break all pairing-based assumptions by running Shor’s algorithm on ${\mathbb{G}}_T$ — Shor97

Variations

Symmetric vs. asymmetric pairings

A pairing can be symmetric (${\mathbb{G}}_1={\mathbb{G}}_2$) or asymmetric (${\mathbb{G}}_1\ne {\mathbb{G}}_2$). Asymmetric pairings (Type 3) support stronger assumptions (SXDH: DDH is hard in both ${\mathbb{G}}_1$ and ${\mathbb{G}}_2$) and are used in most modern constructions. See Pairings for the full Type 1/2/3 classification and efficiency trade-offs — GPS06.

$k$-Linear assumption

Generalizes DLIN: given $k$ random group elements and their DH combinations, decide if an additional element is in the span. For $k=1$: DDH; for $k=2$: DLIN.

Decision $n$-BDHE

Given $(g,h,g^{\alpha },\dots ,g^{{\alpha }^n},g^{{\alpha }^{n+2}},\dots ,g^{{\alpha }^{2n}})$ for a symmetric pairing $e:\mathbb{G}\times \mathbb{G}\to {\mathbb{G}}_T$ with generator $g$, $h\stackrel{\$}{\leftarrow }\mathbb{G}$, and $\alpha \stackrel{\$}{\leftarrow }{\mathbb{Z}}_q$, distinguish $e(g,h{)}^{{\alpha }^{n+1}}$ from uniform in ${\mathbb{G}}_T$ — BGW05.

Subgroup decision

Let $\mathsf{GrGen}(1^{\lambda })$ output $(q_1,q_2,\mathbb{G},{\mathbb{G}}_T,e,g)$: distinct primes $q_1,q_2$, cyclic groups $\mathbb{G}$ and ${\mathbb{G}}_T$ of order $N=q_1{q}_2$, a generator $g$ of $\mathbb{G}$, and a non-degenerate bilinear map $e:\mathbb{G}\times \mathbb{G}\to {\mathbb{G}}_T$. The adversary receives $N$ but not its factors. For $x\stackrel{\$}{\leftarrow }\mathbb{G}$, the element $x^{q_2}$ is uniform in the order-$q_1$ subgroup of $\mathbb{G}$.

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{sd}}_{\GrGen,\calA}(\secpar)$}
\begin{algorithmic}
\State $(q_1, q_2, \GG, \GG_T, e, g) \gets \GrGen(1^\secpar)$; $N \gets q_1 q_2$
\State $x \getsr \GG$; $b \getsr \bits$
\State $x_0 \gets x$; $x_1 \gets x^{q_2}$
\Comment{$x_1$ is uniform in the order-$q_1$ subgroup}
\State $b' \gets \calA(N, \GG, \GG_T, e, g, x_b)$
\Return $[b' = b]$
\end{algorithmic}
\end{algorithm}

The subgroup decision assumption holds for $\mathsf{GrGen}$ if for all efficient $\mathcal{A}$,

$${\mathbf{Adv}}_{\mathsf{GrGen},\mathcal{A}}^{\mathrm{sd}}(\lambda ):=\left|2\mathrm{Pr}\left[{\mathbf{G}}_{\mathsf{GrGen},\mathcal{A}}^{\mathrm{sd}}(\lambda )=1\right]-1\right|$$

is negligible — BGN05.

Attacks

• The MOV/Frey-Rück attack reduces the discrete log in $\mathbb{G}$ to discrete log in ${\mathbb{G}}_T$ via the pairing; for small embedding degree this is devastating
• Index calculus algorithms are effective in ${\mathbb{G}}_T$ and motivate the need for large embedding degree
• Quantum: Shor’s algorithm breaks discrete log in all pairing groups — Shor97

Participates in

Builds on Bilinear map assumptions

• BDH ⇒ ABE
• n-BDHE ⇒ BE (via Decision $n$-BDHE)
• BDH ⇒ CDH
• DBDH + DLIN ⇒ HIBE
• BDH ⇒ HVE
• BDH ⇒ IBE (random oracle model)
• DBDH + DLIN ⇒ IBE
• k-Lin ⇒ VRF (via $k$-Linear assumption)
• Bilinear pairing + k-Lin ⇒ BARG for NP (via $k$-Linear assumption)
• DBDH ⇒ BDH (via Decisional BDH)
• DBDH ⇒ IBE (Waters, standard model) (via Decisional BDH)
• DBDH ⇒ Selectively secure IBE (Boneh–Boyen) (via Decisional BDH)
• DBDH ⇒ Three-party NIKE (Joux) (via Decisional BDH)
• $k$-Linear assumption ⇒ ABE (via $k$-Linear assumption)
• Subgroup decision ⇒ BARG for NP (via Subgroup decision)
• Subgroup decision ⇒ Perfect NIZK arguments for NP (via Subgroup decision)

Produces Bilinear map assumptions

• DBDH ⇒ BDH