Table of Contents
What is a bilinear pairing? Essentially, a pairing is just a function e: G1 X G2 ➝ Gt. In cryptography G1 and G2 are usually taken from certain elliptic curves over finite field Fq while Gt is taken from the extension field Fqk. Let P and Q be a generator of G1 and G2, the following properties should hold for a pairing:
It is bilinear. that is:
e(aP,bQ)=e(P,Q)ab
e(P1+P2,Q)=e(P1,Q)e(P2,Q)
e(P,Q1+Q2)=e(P,Q1)e(P,Q2)
It is non-degenerate:
e(P,Q)≠1
It is computable.
In the beginning, pairings were used to attack crypto systems. People used pairing to reduce the discrete logarithm problem in an elliptic curve to the discrete logarithm problem in a finite field. But then someone found that it could also be used in a positive way. In the groundbreaking paper by Boneh and Franklin (Crypto 2001), pairings were used to build the first practical identity-based encryption scheme. After that, many pairing based cryptographic schemes have been invented.
Jpair is a pure Java Implementation of bilinear pairing. It has no dependencies on external libraries. Although not fully tested, it should compatible with any Java version above 1.2. In fact, I've used it on the Android platform without changing any of the code.
Currently Jpair intentionally supports only curves over prime fields (characteristics p > 3 and p ≡ 3 mod 4) and with embedding degree of 2. The Weierstrass equation of the curve is y2 = x3 +ax +b. For most of the usages, unless you are doing very low level stuff, this is just enough. Moreover, pairings constructed from other types of curves are usually much slower. So if there is no significant benefit, I'll stay with this.
More specifically, Jpair supports the supersingular curve y2 = x3 + x over the field Fp for some prime p = 3 mod 4. This is called Type A in the PBC terminology. The good thing about this curve is that the number of the points on the curve is exactly p+1 so you can generate the parameters of a random pairing easily.
A somewhat more interesting type of curves supported by Jpair is the non-supersingular curve in the form of y2 = x3 -3x +b over the field Fp for some prime p = 3 mod 4. In this case a=-3, so the performance of this type of curves can be boosted using the more efficient algorithms proposed by Chatterjee et.al. (see: Sanjit Chatterjee, Palash Sarkar, Rana Barua: "Efficient Computation of Tate Pairing in Projective Coordinate over General Characteristic Fields". ICISC 2004: 168-181). So if you want better performance, use this type of curves.
It fairly fast. On my MacBook Pro (2.5 GHZ Core Duo, 4 G Ram, Java 1.6), the fastest pairing takes 13 msec, which is the same as MIRACL which is in C++ and is better than JPBC (16 Msec) when using the same parameters. However it cannot beat PBC (in C), which takes only 2 msec. In the following table, nss means using the non-supersingular curve in the form of y2 = x3 -3x +b and ss means using he supersingular curve y2 = x3 + x. Each number is the average of 1000 executions.
To construct a pairing, you need to decide the proper parameters:
r: the order of group G1,
p: a large prime defines the finite field Fp
E : a good elliptic curve
cof: a cofactor such that cof=#E(Fp)/r where #E(Fp) is the number of point on the curve.
The group order r must satisfy two conditions: it must divide the number of point on the curve #E(Fp) and it must divides p2-1. The second condition is because we support only embedding degree of 2. For the supersingular curve y2 = x3 + x, the points on the curve is exactly p+1 so it is relatively easy to find the parameters. Just to find a large enough prime r and large enough prime p such that r divides p+1. Since p2-1 = (p+1)(p-1), the second condition is satisfied automatically. For performance reason, it is better that r has a low hamming weight, i.e. has only a few 1 in binary format.
For the non-supersingular curve in the form of y2 = x3 -3x +b, the parameters need to be generated by a more complex (and not yet implemented) algorithm.
To make a system secure, r and p must be large enough so that the discrete logarithm problem is computationally infeasible to solve in G1 and Fp2. A suggestion is that to achieve security equivalent to 1024-bit RSA, r should be at least 160-bit and p should be at least 512-bit; to achieve 2048-bit security, r should be 256-bit and p should be 1024-bit.
The first step is always to initialise a pairing. You have three choices:
Use a predefined pairing. In Jpair, three pairings are predefined, all provide 1024-bit security. One uses the curve y2 = x3 +ax +b, where a=-3. The other two uses the curve y2 = x3 + x.
import uk.ac.ic.doc.jpair.pairing.Predefined; ... //initialise the predifined pairing using the non-supersingular curve Pairing e = Predefined.nssTate(); //initialise the predifined pairings using the supersingular curve Pairing eSS1 = Predefined.ssTate(); Pairing eSS2 = Predefined.ssTate2();
Use the PairingFactory class to generate a random pairing. Only the supersinglar curve is support currently.
import uk.ac.ic.doc.jpair.pairing.PairingFactory; ... //provide the bit-lengths of the group order (r), the field size (p) and the source of randomness //For example, we want r to be 160-bit and p to be 512-bit Pairing e =PairingFactory.ssTate(160, 512, new Random());
Manually define the pairing. In this case, you must have a proper set of parameters for initialising the pairing.
import uk.ac.ic.doc.jpair.pairing.EllipticCurve;
import uk.ac.ic.doc.jpair.pairing.TatePairing;
...
//initialise the finite field Fp given a prime number p
BigInt p = new BigInt("878071079966331252243778198475404981580688319941420821102865339926647563088022295
7078625179422662221423155858769582317459277713367317481324925129998224791",10);
Fp field = new Fp(p);
//initialise the elliptic curve. The curve can be specified given the field and the coefficient a and b
//of the Weierstrass equation:
//y2 = x3 +ax +b
//For example, in the case of the supersingular curve //y2 = x3 + x, a = 1 b = 0 ,
EllipticCurve ec = new EllipticCurve (field,BigInt.One,BigInt.ZERO);
//You also need to know the group order r and the cofactor
BigInt r = new BigInt("730750818665451621361119245571504901405976559617",10);
BigInt cof = new BigInt("1201601226489114607938882136674053420480295440125131182291961513104720728935970
4531102844802183906537786776",10);
//now you can initialise the pairing
Pairing e = new TatePairing(ec,r,cof);Here is an example of how to play with the pairing you just initialised. Recall one of the properties of pairing says that e(aP,bQ)=e(P,Q)ab. The following code verifies this property.
import uk.ac.ic.doc.jpair.pairing.EllipticCurve;
import uk.ac.ic.doc.jpair.pairing.TatePairing;
...
//using a predefined pairing
Pairing e = Predefined.nssTate();
//get P, which is a random point in group G1
Point P = e.RandomPointInG1(new Random());
//get Q, which is a random point in group G2
Point Q = e.RandomPointInG2(new Random());
//compute e(P,Q)
FieldElement epq =e.compute(P,Q);
//the curve on which G1 is defined
EllipticCurve g1 = e.getCurve();
//a is a 160-bit random integer
BigInt a = new BigInt(160,new Random());
//Point aP is computed over G1
Point aP = g1.multiply(P, a);
//The curve on which G2 is defined
EllipticCurve g2 = e.getCurve2();
//b is a 160-bit random integer
BigInt b = new BigInt(160,new Random());
//bQ is computed over G2
Point bQ = g2.multiply(Q, b);
//compute e(aP,bQ)
FieldElement res = e.compute(aP,bQ);
//compute e(P,Q)^ab, this is done in group Gt
BigInt ab = a.multiply(b);
//get the field on which Gt is defined
Field gt = e.getGt();
FieldElement res2 = gt.pow(epq,ab);
//compare these two
if(res.equals(res2)){
System.out.println("Correct! e(aP,bQ) = e(P,Q)^ab");
}
else{
System.out.println("Something is wrong! e(aP,BQ) != e(P,Q)^ab");
}