Prodesse Quam Conspici

pairing-based cryptography

Recently, a lot of attention has been paid on how to construct cryptographic primitives using pairings, like identity-based encrytion[1], one-round tripartite Diffie-Hellman[2], etc. (which will be disscussed in later posts).

However what is pairing?

Pairing is a map, \(e:G_1\times G_2\rightarrow G_T\), where \(G_1,G_2\) are both additive cyclic groups of prime order \(q\), \(G_T\) is another multiplicative cyclic group of order \(q\), satisfies the following properties:


\[\forall a,b\in F_q^\ast, \forall P\in G_1,Q\in G_2:e(aP, bQ)=e(P,Q)^{ab}\]


\[e\neq 1\]


\[There\ exists\ efficient\ algorithms\ to\ compute\ e.\]

1 intractable problems

1.1 BDHP

Bilinear Diffie-Hellman Problem (BDHP) is believed to be intractable, which means it is hard to compute \(e(P,P)^{abc}\) given \(<P,aP,bP,cP>\), \(a,b,c\in \mathbb{Z}_q^\ast\), \(P\) is a generator of \(\mathbb{G}_1\).

2 Weil pairing

In cryptography.

3 Tate pairing

Tate pairing is another common used instantiation.


[1] D. Boneh, M. Franklin, Identity-based encryption from the weil pairing, in: Annual International Cryptology Conference, Springer, 2001: pp. 213–229.

[2] A. Joux, A one round protocol for tripartite diffie-hellman, in: International Algorithmic Number Theory Symposium, Springer, 2000: pp. 385–393.

Tags: cryptography.