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$. Pairings enable cryptographic primitives not known to be constructible from DDH alone, including identity-based encryption and short signatures.

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 (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

• BDH ⇒ IBE
• BDH ⇒ DS
• BDH ⇒ VRF
• BDH ⇒ AC
• CDH ⇒ BDH
• BDH ⇒ 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.

SXDH (Symmetric External Diffie-Hellman)

Assumes DDH is hard in both ${\mathbb{G}}_1$ and ${\mathbb{G}}_2$ of an asymmetric pairing. Stronger than BDDH; used for efficiently instantiating Groth-Sahai proofs.

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
• BDH ⇒ AC
• BDH ⇒ BE
• BDH ⇒ DS
• BDH ⇒ HIBE
• BDH ⇒ HVE
• BDH ⇒ IBE
• BDH ⇒ NIZK
• BDH ⇒ VRF

Produces Bilinear map assumptions

• CDH ⇒ BDH
• SXDH (Symmetric External Diffie-Hellman) ⇒ BDH