Pairing Tutorial

Example: Implementing a pairing-based signature scheme

Cryptimeleon Math is a library supplying the mathematical basics for cryptography.

In this notebook, we’ll take a look at how to implement a pairing-based scheme.

The (multi-message) Pointcheval-Sanders signature scheme is a very useful digital signature scheme for advanced cryptographic constructions because of its elegant and simple algebraic structure. We’ll use it as an example for implementing a cryptographic scheme.

We’ll work alongside the scheme’s definition in the paper: image.png

… and show how to implement it.

Note: You can also check this page out in an interactive Jupyter notebook by clicking the badge below:

Binder

Setting up the bilinear group

image-2.png First, we need to set up the bilinear group setting required for the scheme. We need to know the type of pairing and the desired security parameter. In this case we want a type 3 pairing and 100 bit security.

%maven org.cryptimeleon:math:3.0.1

import org.cryptimeleon.math.structures.groups.elliptic.*;
import org.cryptimeleon.math.structures.groups.elliptic.type3.bn.BarretoNaehrigBilinearGroup;
import org.cryptimeleon.math.structures.groups.*;
import org.cryptimeleon.math.structures.groups.mappings.*;
import org.cryptimeleon.math.structures.rings.zn.*;

// Choose number of messages r
var r = 3;

// BN pairing is type 3 and we specify a 100 bit security parameter
BilinearGroup bilinearGroup = new BarretoNaehrigBilinearGroup(100);

// Let's collect the values for our pp
Group groupG1 = bilinearGroup.getG1();
Group groupG2 = bilinearGroup.getG2();
Group groupGT = bilinearGroup.getGT();
BilinearMap e = bilinearGroup.getBilinearMap();
BigInteger p = groupG1.size();
Zn zp = bilinearGroup.getZn();
System.out.println("Generated bilinear group of order " + p);

Generated bilinear group of order 66696243400694322499906033083377966773014133293855982130239936888504801018589797

Generating a key pair

image-2.png

For a key pair, we need to generate random exponents \(x\) and \(y_i\) as the secret key. Because it’s a group of order \(p\), we interpret the exponents as elements of \(\mathbb{Z}_p\).

// Generate secret key

var x = zp.getUniformlyRandomElement();
var y = zp.getUniformlyRandomElements(r); //computes a vector of r random numbers y_0, ..., y_(r-1)

System.out.println("x = " + x);
System.out.println("y = " + y);

x = 44316690029411663254611714309296043658145120563043444597918762724488774032849016
y = [51478947070224658350006832587196591192710511857417817473759773193237799142187868, 33927648900762590477251768057893685301575598802209896654837650420930260665907493, 31942443811002866534686111117566243727207867254610919218580116107487819440003493]

Then we can compute the corresponding public key easily and run precomputation on it to speed up later verifications:

// Generate public key

var tildeg = groupG2.getUniformlyRandomElement();
var tildeX = tildeg.pow(x).precomputePow(); // this computes X = tildeg^x as above and runs precomputations to speed up later pow() calls on tildeX
var tildeY = tildeg.pow(y).precomputePow(); // because y is a vector, this yields a vector of values tildeg.pow(y_0), tildeg.pow(y_1), ...

System.out.println("tildeg = " + tildeg);
System.out.println("tildeX = " + tildeX);
System.out.println("tildeY = " + tildeY);

tildeg = ([15612262186613943001599674873747672478167254678147363518484223258609773251074521, 6695625395217442917795489142627195193557009980168247801203971373627059392899917],[1716496473379239907690878433792355745729381484032749921901241128098803935018004, 35939614081875471947784722352424962014505948289558598974059797901361701390764287])
tildeX = ([49451746382193245976512827756340189497160693041699150207222002203694282378417100, 6365284962020988589657623020452805591557311074009527101274070445242244914494596],[37670039269157058643165831685573149548148296775994096925519268338690232825282580, 60808963927089034307880840373470418558922302378127350252050888807453919667759158])
tildeY = [([37096241567790314576015992933786958464224636325173180363149134697001189382086295, 14327875947050106228749975433909911771693914946911685017500928405596607835626573],[27079253588539378212703892698546491053762903276311927103744975019222497061520760, 4413013671986041630123579125881147660886375350577576990469611640843278745271165]), ([23594571273105549305264921227670608718245851924526561250983832263891119756248585, 47207821248800951510419468116848415739841492694865191256376107938526487173001798],[39335465558363876423547613958875032830683099661673915170771588979484831898202723, 56926193382850632142826462008916412486171511211260628456293691759843834067832759]), ([21150985485411507103913001986005356092426121222640587113482632661206554905976194, 58975933440802007345305668420510413905193642058656292982938750266351190327201373],[5948149942497754574825822566382077981878589606551994272424735052326243859220632, 62341803076400392123521928786045933314231151323022581797555620768971115139617684])]

Computing a signature

image.png

Computing a signature works as you’d expect now with what we’ve already seen. Messages for Pointcheval-Sanders lie in \(\mathbb{Z}_p\), but we can use a hash function \(\mathcal{H}:\{0,1\}\rightarrow \mathbb{Z}_p\) to sign arbitrary strings.

import org.cryptimeleon.math.structures.rings.cartesian.RingElementVector;

// Preparing messages ("Hello PS sigs", 42, 0, 0, ...)
var m = new RingElementVector(
    bilinearGroup.getHashIntoZGroupExponent().hash("Hello PS sigs"), 
    zp.valueOf(42)
).pad(zp.getZeroElement(), r);

// Computing signature
var sigma1 = groupG1.getUniformlyRandomNonNeutral().compute(); // h
var sigma2 = sigma1.pow(x.add(y.innerProduct(m))).compute(); // h^{x + sum(y_i*m_i)}
// The compute() call is optional but will cause sigma1 and sigma2 to be computed concurrently in the background.

System.out.println("sigma1 = " + sigma1);
System.out.println("sigma2 = " + sigma2);

sigma1 = (46630585754949243632417246990191785087363583083846579705838867952988538066520939,17263027777440197906346475373206468646187190298505150562539188344714989348129425)
sigma2 = (65234622235243653899783328258074381634715453592665691958203255223206860574036520,43680817006277096546857890922027858481588707367002330914850786080795692837683541)

Verifying a signature

image.png

For this verification, we need to emply the pairing e.

!sigma1.isNeutralElement() 
    && e.apply(sigma1, tildeX.op(tildeY.innerProduct(m))).equals(e.apply(sigma2, tildeg))

true

If this pairing computation seems slow, check out the mclwrap addon for a faster bilinear group.