High-Speed Software Implementation of the Optimal Ate Pairing over Barreto-Naehrig Curves


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 Fp, 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.
The latest version : https://github.com/herumi/ate-pairing
Tate pairing, optimal pairing, Barreto-Naehrig curve, ordinay curve, finite field arithmetic, bilinear pairing software implementation.
x86_64(amd64) Intel/AMD processor
64-bit Windows/64-bit Linux/Max OS X
C++ compiler
Visual Studio 2008 or gcc 4.4.1 or later
Build on Windows
Open ate/ate.sln and compile test_bn with Release mode, then you can get the binary in ate/x64/Release/test_bn.exe
Build on Linux/Mac OS
>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 Fp2, squaring over Fp2, and optimal ate pairing
Our results dclxvi[1st version]
Core i7a Opteronb Core 2 Duoc Athlon 64d Opteronb Core 2 Quade Athlon 64d
Multiplication over Fp2 435 443 558 473 695 693 1714
Squaring over over Fp2 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
  1. Intel Core i7 860(2.8GHz), Windows 7, Visual Studio 2008 Professional
  2. Quad-Core AMD Opteron 2376(2.3GHz), Linux 2.6.18, gcc 4.4.1
  3. Intel Core 2 Duo T7100(1.8GHz), Windows 7, Visual Studio 2008 Professional
  4. AMD Athlon(tm) 64 X2 Dual Core Processor 6000+, Linux 2.6.23, gcc 4.1.2
  5. 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 F397 and F3193
very fast etaT pairing for Core 2 Duo
etaT pairing of F3509 and F21223
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
mailto:MITSUNARI Shigeo<herumi@nifty.com>