Pairings

Overview

Pairing = Bilinear Map

Technically, pairing is a special kind of bilinear map for modules. In cryptography, they are often used interchangeably.

What do pairings allow you to do that normal groups do not?

Pairings allow you to multiply two hidden numbers, while “normal groups” only allow you to add

Pairing Rules

1. $e(nP,mQ)=e(P,mQ{)}^n=e(nP,Q{)}^m=e(P,Q{)}^{nm}$
2. $e(P,Q{)}^R\ast e(P,Q{)}^S=e(P,Q{)}^{R+S}$
3. $e(P,Q{)}^0=1$
4. $e(P,Q+R)=e(P,Q)\ast e(P,Q)$
5. $e(P+S,Q)=e(P,Q)\ast e(S,Q)$

Pairing Application

Question

Let’s suppose Alice want to prove to Bob that she know some integer $a$ that satisfies the equation:  $a^2-2027a+16152=0$  without revealing $a$ to Bob. How would Alice do this using an elliptic curve pairing?

Answer:

1. Choose 2 public generators $G$, and $H$

2. Compute $aG$ and $aH$ and send results to Bob (Bob cannot compute $a$ due to ECDLP)

3. Bob computes:

   $e(aG,aH)\ast e(G,(-2027)\ast (aH))\ast e(G,16152\ast H)=e(G,H{)}^{a^2-2027a+16152}$

   If the above result == 1, then we know $a^2-2027a+16152=0$ with high probability

Definition

A pairing is a map:

$$e:G_1\times G_2\to G_T$$

where:

• $G_1,G_2$ are groups of points on elliptic curves (sometimes the same curve, sometimes different).
• $G_T$ is a multiplicative subgroup of a finite field ${\mathbb{F}}_{q^k}^{\ast }$.
• The pairing $e$ must be:
  • Bilinear: $e(aP,bQ)=e(P,Q{)}^{ab}$ for all points $P\in G_1,Q\in G_2$ and integers $a,b$
  • Non-degenerate: $e(P,Q)\ne 1$ if $P$ and $Q$ are generators of $G_1$ and $G_2$, so it carries meaningful information
  • Efficiently computable: there must be an efficient algorithm to compute $e(P,Q)$

Pairing Friendly Elliptic Curves

• for an elliptic curve defined by $(p,q)$, there is an integer $k$ such that $q$ divides $p^k-1$ (i.e. $\frac{p^k-1}{q}$)
• k is called the embedding degree
• the smaller $k$ is, the more pairing-friendly the curve
  • e.g. for BN254, $k=12$
• Reason:
  • the pairing function pair(𝑎, 𝑏) takes as input two points 𝑎, 𝑏 ∈ 𝐸 on the elliptic curve and spits out a value pair $(a,b)\in f_{p^k}^x$
  • in other words, a nonzero element of the finite field of order $p^k$
  • thus, the smaller the $k$, the smaller the order of $p^k$

Pairing Types

• All types are equally secure
• Tate Pairing
  • Weil and Ate pairings can be written in terms of Tate pairing
• Weil Pairing
• Ate Pairing
  • most efficient type

Pairing Classification

Type 1

• $G1=G2$ (symmetric pairing)

Type 2

• $G1\ne G2$
• $\exists \phi :G2\to G1$ which is an efficiently computable homomorphism
• no efficient secure hash to group function $H:0,1\ast \to G2$ exists.

Type 3

• $G1\ne G2$
• no efficiently computable homomorphism $\phi :G2\to G1$ exists

Type 4

• $G1\ne G2$
• $\exists \phi :G2\to G1$ which is an efficiently computable homomorphism
• there exists some $H:0,1\ast \to G2$ which is an efficient secure hash to group function

Security

• let $\hat{e}$ be a bilinear map and $P\in G1$ and $Q\in G2$ for asymmetric bilinear map groups $(G1,G2,GT)$, such that $z=\hat{e}(P,Q)$
• the general pairing inversion problem to be the problem of finding $P,Q$ given $z$

Different than Elliptic Curve Hardness

Hardness assumption in Pairing-based cryptography is separate from Elliptic Curve Cryptography

Calculation

4. Miller Loop
5. Final Exponentiation a. Easy Part b. Hard Part $$\frac{p^k-1}{r}=\underset{\text{Easy part}}{\underbrace{(p^s-1)\cdot \left(\sum _{i=0}^{d-1}\frac{p^{is}}{{\Phi }_k(p)}\right)}}\cdot \underset{\text{Hard part}}{\underbrace{\frac{{\Phi }_k(p)}{r}}}$$ where ${\Phi }_k(p)$ is the $k-th$ cyclotomic polynomial evaluated at p

Notation (additive vs multiplicative)

Simply put, it’s a matter of preference.

Source

Example

Discrete Logarithm Problem (DLP)

Multiplicative Notation

• $g^x=r(modp)$
• $g:generator$
• $r:1<r<p$
• $g^x$ will give a result that is uniformly distributed between 1 and (p - 1), inclusive
• Given g, r and p, it is hard to deduce x
• If p is small, it is easy to find x
• If p is very large, it is hard to find x

Additive Notation

• Given $E$ is a standard elliptic curve and arbitrary nonzero $g,g^{\prime }\in E$
• $n\cdot g=g^{\prime }$
• where $n\in F_q$ and $n\in (N)$ (e.g. $n$ is 254-bit if $E$ is BN254 )
• $n$ is hard to find
• However, given $g$ and $n$, one can compute $n\cdot g$ in $O(logn)$

General

• An instance of the Hidden Subgroup Problem (HSP)

Link to original

Benchmarks

• GitHub - guild-of-zk/pairing-bench

Implementations

pairings_bn.nim Faster pairings · Issue #101 · axiom-crypto/halo2-lib · GitHub

Reference

• Applied Crypto #1: Elliptic Curve Cryptography | ZK Learning Resources
• Exploring Elliptic Curve Pairings | by Vitalik Buterin | Medium
• Pairing-Based Cryptography in Theory and Practice - Hannes Salin