pairing_option_set(p, "method", "shipsey-stange");

PBC Library

The Pairing-Based Cryptography Library

The Pairing-Based Cryptography Library

Applied patch by Joe Cooley that addresses configure.ac issues and
fixes a bug in `example/zss.c`.

A fairly lowlevel bug had somehow escaped my attention for quite some time.
Comparing zero elements previously returned the wrong result, due to
a simple logic bug in `montfp.c`.

Simple final powering optimizations were applied to D and G pairings.

Fortunately for me, Paul Miller tests each version extensively soon after release. In version 0.4.5 he found a bug that I had overlooked for one of the usual reasons: "the modification is so trivial that it can’t possibly cause problems!". Luckily the bug wasn’t difficult to fix.

I finally implemented what I call type G pairings, which are curves of embedding degree 10 found by David Freeman.

They’re a bit slow at the moment, but I hope to speed them up soon. Interestingly, Katherine Stange’s elliptic net algorithm for computing a type G pairing is about the same speed as Miller’s algorithm, but this is without using (signed) sliding windows for the latter.

No big changes. I added code that generates random points by raising a generator by a random power, which is faster in some cases as it avoids finite field square root routines. This change does not affect pairing speed.

I’ve been trying to find a case where computing the pairing with elliptic nets is faster than Miller’s algorithm. I haven’t found one yet, but the type E pairing comes close. If the group order weren’t a Solinas prime then it’s possible that the Shipsey-Stange algorithm would be faster.

Various optimizations improve A, D, E pairing times. In the type E case the optimization was trivial: simply precomputing the random point used in the pairing saved a lot of time.

For type A curves, I implemented an algorithm that computes pairings using
elliptic nets: see
Katherine
Stange’s paper. It is not used by default since it is slower.
To activate it, if *p* is a type A pairing, use:

pairing_option_set(p, "method", "shipsey-stange");

The above paper is accompanied by a
PARI/GP
script which I used to check against my implementation.
I had never used PARI/GP before,
and it took me some time to work out what to do.
I’ll record what I did here
so I won’t have to relearn it next time. First I ran `gp` with
the script as the first argument. Then I typed something like:

q=1019 r=17 x=493 y=398 x2=672 y2=336 E=ellinit([0,0,0,Mod(1,q),0]) a=Mod(X,X^2+1) P=[Mod(x,q),Mod(y,q)] Q=[Mod(-x2,q), Mod(y2,q)*a] tate_pairing_alg(E,P,Q,r)