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)

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

undefined

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