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 (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 ⇒ DS
• 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.

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)
• $k$-Linear assumption ⇒ ABE (via $k$-Linear assumption)