very fast etaT pairing for Core 2 Duo

This is an efficient implementation of η_T pairing on Core 2 Duo. The processing speed achieves 92 μsec over F₃⁹⁷ and 553 μsec over F₃¹⁹³ on Windows Xp SP3 + Core 2 Duo 2.66GHz. It is the fastest speed at 2008 Dec 21 as far as I know.

Tate pairing, η_T pairing, efficient implementation

The latest version : source of etaT pairing for F₃⁹⁷ and F₃¹⁹³.
See Multi-core Implementation of the Tate Pairing over Supersingular Elliptic Curves to get the source code for Tate pairing in F₂¹²²³ and F₃⁵⁰⁹.

CPU

Intel Core 2 Duo (ESSE3 is required)

OS

Windows Xp/Vista, Linux and Intel Mac OS X
32-bit version for m = 97, 32/64-bit version for m = 193
Remark:The current version for multi thread supports only Windows.

C++ compiler

Visual Studio 2008 or gcc 4.3.0 or later

Open etat/etat.sln and compile test_etat with Release mode, then you can get the binary in etat/test/Release/test{97,193}.exe

Type

>cd etat && make

then you can get the test binary in etat/test

The following values are at 2.6GHz Intel Core 2 Duo processor on 32-bit Windows Xp SP3.
The implemented algorithm of η_T pairing is old, then these values will be faster if newer algorithms are implemented.

Running times (usec)

mode	m = 97	m = 193
pairing(single)	149	975
pairing(multi)	92	553

Running times for m = 97(clks)

	Core2Duo 2.6GHz(my results)	Opteron 2.2GHz/x86-64 with SSE(ref)
mul	482	1100
cube	83	86
pairing(single)	436K	1053K
pairing(multi)	239K	-

Running times for m = 193(clks)

	Core2Duo 2.6GHz(my results)	Opteron 2.2GHz/x86-64(ref)
mul	1662	4009
cube	164	268
pairing(single)	2535K	5744K
pairing(multi)	1438K	-

./include.mie/mie_common.h ; for some macro definitions
./xbyak/                   ; JIT assembler (used only for m = 97)
./etat/src/*.h             ; source of etat pairing
      /test/test97.cpp     ; test and benchmark for m = 97
      /test/test193.cpp    ; test and benchmark for m = 193

int main()
{
    using namespace MIE_ETAT;
    ECgeneral<F3_97> P, Q;
    P.x.setByString("2 00200100011220200021200102211201 00021000200212122020102112002120 00202212022000011201110000200010");
    P.y.setByString("0 12010202211110211201221022002022 10221102221011211002020221200102 02111110012020102100200102011202");
    Q.x.setByString("0 01222010102100210221200200220020 12011112220212201011100200100122 20010221110121202101112001221101");
    Q.y.setByString("0 22121101111020122212220210010210 01200220002000010011211212111210 20012221111010101211110121220001");
    int count = 5000;
    int begin = clock();
    F3_97_6 t;
    for (int i = 0; i < count; i++) {
        t = CalcEtatPairing(P, Q);
    }
    int end = clock();
    printf("%.3fmsec\n", 1000.0 * (end - begin) / CLOCKS_PER_SEC / count);
}

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

• J. L. Beuchat, M. Shirase, T. Takagi, and E. Okamoto, "A Refined Algorithm for the eta T Pairing Calculation in Characteristic Three", 10 Aug 2007(http://eprint.iacr.org/2007/311).
• J. L. Beuchat, N. Brisebarre, M. Shirase, T. Takagi, and E. Okamoto, "A Coprocessor for the Final Exponentiation of the eta T Pairing in Characteristic Three", 13 Feb 2007(http://eprint.iacr.org/2007/045).
• M. Shirase, Y. Kawahara, T. Takagi, E. Okamoto, "Universal EtaT Pairing Algorithm over Arbitrary Extension Degree", WISA 2007, LNCS 4867, pp.1-15, 2007.
• M. Yoshitomi, T. Takagi, S. Kiyomoto, and T. Tanaka, "Efficient Implementation of the Pairing on Mobilephones using BREW", 20 Aug 2007(http://eprint.iacr.org/2007/340).
• Y. Kawahara, K. Aoki, T. Takagi, "Faster Implementation of eta_T Pairing Over GF(3^m) Using Minimum Number of Logical Instructions for GF(3)-Addition", The second International Conference on Pairing-based Cryptography, Pairing 2008, LNCS, 2008.
• Y. Kawahara(Advisor T. Takagi), "Efficient Implementation of Tate Pairing using Java", BA Thesis at Future University-Hakodate, 2007.
• E. Okamoto, T. Okamoto, and N Kanayama, "Recent Research Activities On Pairing", http://w2.gakkai-web.net/gakkai/ieice/vol1pdf/vol1_051.pdf .

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

2010/Apr/26 support gcc 4.5.0
2009/Nov/4 add the link to Multi-core Implementation of the Tate Pairing over Supersingular Elliptic Curves
2008/Dec/21 add etat pairing for m = 193(553usec@Core2Duo 2.6GHz)
2008/Jun/28 6ops add(K. Aoki, Y. Kawahara, T. Takagi) for m = 97, 92usec@Core2Duo 2.6GHz
2008/Jun/26 fix pdf
2008/Jun/6 optimized(98usec@Core2Duo 2.6GHz with multi-thread, 161usec with single-thread)
2008/May/24 optimized(225usec@Core2Duo 1.8GHz with single-thread)
2008/Apr/4 optimized(238usec@Core2Duo 1.8GHz, 175usec@Core2Duo 2.6GHz)
2008/Mar/31 optimized(256usec@Core2Duo 1.8GHz, 184usec@Core2Duo 2.6GHz)
2008/Mar/27 first release(288usec@Core2Duo 1.8GHz, 209usec@Core 2 Duo 2.6GHz)

MITSUNARI Shigeo