Optimal Ate Pairing

We release the source of our library described in the ePrint(High-Speed Software Implementation of the Optimal Ate Pairing over Barreto-Naehrig Curves) and Pairing 2010. The latest version of this library is able to compute the optimal ate pairing over a 254-bit prime field F_p, in just 1.35 million of clock cycles on a single core of an Intel Core i7 2.8GHz processor, which implies that the pairing computation takes 0.399msec.

NEW VERSION[2013/Jun/1]
The new vesion using mulx on Haswell computes the optimal ate pairing in just 1.17 clock cycles on a single core of an Intel Core i7 4700MQ 2.4GHz processor with TurboBoost technology disabled(eprint).

To the best of our knowledge, this is the first time that a software or a hardware accelerator reports a high security level pairing computation either symmetric or asymmetric, either on one core or on a multi-core platform, in less than one millisecond.

Tate pairing, optimal pairing, Barreto-Naehrig curve, ordinay curve, finite field arithmetic, bilinear pairing software implementation.

CPU: x86_64(amd64) Intel/AMD processor
OS: 64-bit Windows/64-bit Linux/Max OS X
C++ compiler: Visual Studio 2008 or gcc 4.4.1 or later

Open ate/ate.sln and compile test_bn with Release mode, then you can get the binary in ate/x64/Release/test_bn.exe

Type

>cd ate && make

then you can get the test binary in ate/test/bn

These value are obsolete, please see https://github.com/herumi/ate-pairing.

optimal ate pairing for ate.20120130.zip
CPU	OS	M clock cycles
Core i7 2600 3.4GHz(with turbo boost)	Win7	1.35
Core i7 2600 3.4GHz(without turbo boost)	Linux	1.552
opteron 2376 2.3GHz	Linux	1.669
Xeon x5650 2.67GHz	Linux	1.630
Core i5 M 520 2.5GHz	Win7	1.603
Core2Duo T7100 1.8GHz	Win7	1.998
Core2Duo T9400 2.53GHz	Mac	2.155
Core i7 2720QM 2.2GHz	Mac	1.078

How to use

See sample.cpp. ecop::ScalarMult, EcAdd functions use Jacobian coordinate, but opt_atePairing requaires affine coordinate of g2 and g1. So you should convert points on an elliptic curve from Jacobi to Affine by ecop::NromalizeJac.

// calc e : G2 x G1 -> G3 pairing
opt_atePairing<Fp>(e, g2, g1); // e = e(g2, g1)
const Fp a("123456789012345");
Fp2 g2a[3];
ecop::ScalarMult(g2a, g2, a); // g2a = g2 * a
ecop::NormalizeJac(g2a, g2a); // Jacobi to Affine
Fp12 ea1;
opt_atePairing<Fp>(ea1, g2a, g1); // ea1 = e(g2a, g1)
Fp12 ea2 = power(e, a); // ea2 = e^a

the following resuts for older version

Cycle counts of multiplication over F_p², squaring over F_p², and optimal ate pairing
	Our results				dclxvi[1st version]
	Core i7^a	Opteron^b	Core 2 Duo^c	Athlon 64^d	Opteron^b	Core 2 Quad^e	Athlon 64^d
Multiplication over F_p²	435	443	558	473	695	693	1714
Squaring over over F_p²	342	355	445	376	614	558	1207
Miller loop	1.33M	1.36M	1.68M	1.48M	2.48M	2.26M	5.76M
Final exponentiation	1.00M	1.04M	1.27M	1.08M	2.52M	2.21M	5.51M
Optimal ate pairing	2.33M	2.40M	2.95M	2.56M	5.0M	4.47M	11.27M

Intel Core i7 860(2.8GHz), Windows 7, Visual Studio 2008 Professional
Quad-Core AMD Opteron 2376(2.3GHz), Linux 2.6.18, gcc 4.4.1
Intel Core 2 Duo T7100(1.8GHz), Windows 7, Visual Studio 2008 Professional
AMD Athlon(tm) 64 X2 Dual Core Processor 6000+, Linux 2.6.23, gcc 4.1.2
Intel Core 2 Quad Q6600(2394MHz), Linux 2.6.28, gcc 4.33

The BSD 3-Clause License
If you have any questions or problems, just let me know, then I'm happy.

Xbyak is an x86/x64 JIT assembler for C++. I made this library for developping pairing functions efficiently.

etaT pairing of F_3⁹⁷ and F_3¹⁹³: very fast etaT pairing for Core 2 Duo
etaT pairing of F_3⁵⁰⁹ and F_2¹²²³: Multi-core Implementation of the Tate Pairing over Supersingular Elliptic Curves

2012/Jan/30 new version
2010/Sep/8 change xi from u + 12 to u
2010/Jul/16 new version of pairing(use cyclotomic squarings)
2010/Jun/24 add the result of Athon 64
2010/Jun/23 [trivial] rename r_atePairing as opt_atePairing
2010/Jun/20 first release