Tate Pairing

This paper describes the design of a fast multi-core library for the cryptographic Tate pairing over supersingular elliptic curves. For the computation of the reduce modified Tate pairing over F₃⁵⁰⁹, we report calculation times of just 2.94 ms and 1.87 ms on the Intel Core2 and Intel Core i7 architectures, respectively. We also try to answer one important design question that arises: how many cores should be utilized for a given application?

Tate pairing, η_T pairing, supersingular curve, finite field arithmetic, multi-core

The latest version: Source of Tate pairing in characteristic two F₂¹²²³
The latest version: Source of Tate pairing in characteristic three F₃⁵⁰⁹

Multi-core Implementation of the Tate Pairing over Supersingular Elliptic Curves
Authors: Jean-Luc Beuchat and Emmanuel López-Trejo and Luis Martínez-Ramos and Shigeo Mitsunari and Francisco Rodríguez-Henríquez

Title: Multi-core Implementation of the Tate Pairing over Supersingular Elliptic Curves
Authors: Jean-Luc Beuchat and Emmanuel López-Trejo and Luis Martínez-Ramos and Shigeo Mitsunari and Francisco Rodríguez-Henríquez

CPU: Intel Core 2 Duo or later (ESSE3 is required)

OS: Windows Xp/Vista 32/64-bit version
The implementation for multi-core supports only Windows.
C++ compiler: Visual Studio 2008

For Tate Pairing in characteristic two: Open "Tate - Pairing char 2 (F_1223)/pair2_1223.sln" and compile pair2_1223 with Release mode, then you can get the binary in "Tate - Pairing char 2 (F_1223)/Release/pair2_1223.exe"
For Tate Pairing in characteristic three: Open "Tate - Pairing char 3 (F_509)/pair3_509_03.sln" and compile pair3_509_3 with Release mode, then you can get the binary in "Tate - Pairing char 3 (F_509)/Release/pair3_509_03.exe"

Implementations timings for the reduced modied Tate pairing at the 128-bit security level on an Intel Core Quad processor (2.4 GHz.)

Running times [ms]
Mode	F₂¹²²³	F₃⁵⁰⁹
Tate pairing (single-core)	11.19	7.59
Tate pairing (2-cores)	6.72	4.31
Tate pairing (4-cores)	4.22	2.94

Implementations timings for the reduced modied Tate pairing at the 128-bit security level on an Intel Core i7 processor (2.9 GHz.)

Running times [ms]
Mode	F₂¹²²³	F₃⁵⁰⁹
Tate pairing (single-core)	7.94	5.22
Tate pairing (2-cores)	4.53	3.16
Tate pairing (4-cores)	3.13	2.31
Tate pairing (8-cores)	3.08	1.87

Tate Pairing in Characteristic two F₂¹²²³

/*
Point P(x, y) (in hexadecimal) that satisfies the supersingular elliptic curve
E(F_2^m): y^2 + y = x^3 + x + b
x = [1375ab187a468d6b4a492af8ac1fa35e55df06490da51c48ccde809b40baa25b7306c82c0ab667f26f66257c7e7
     eeead6a58fd4ab9864d1612730e0d06a608610414f2b620dd55e33add0ee626d6d07d0bed3e18328fdaa3f24cf7
     1311874aa84eac15322b5a9ac35d343b3bf371c6c57d70b22339482eda2d8d234a342e1c376b094573d0f4e7644
     23e417e5ce9d1ce6901c8c56419b36b65]
y = [75ab7a41fab2bfe173d81883bd3f72b07f9e5022e3d002f151cce67df0b2b24120268400980b2360294c42ad3c2
     2e16efc81091ac15918eb2a4e74118edbda505264e1ca49f2482cb52bc959491455eed22269ebb08eafdb320faf
     89ba8e322f35b85bba88fdb0f995d22cb49038645bb62be8cb339b31821ba3a8ff5df3fa8eaed0d1eae07e8ed1a
     1bf67c1a5f8c90cbb753fe0705b9d5017]
*/
int main()
{
    MyAlign(16) 
    uint xp[] ={
      0x19b36b65,0x01c8c564,0xe9d1ce69,0x3e417e5c,0xf4e76442,0x094573d0,0x2e1c376b,0x8d234a34,
      0x482eda2d,0x70b22339,0x71c6c57d,0x343b3bf3,0x5a9ac35d,0xac15322b,0x874aa84e,0x4cf71311,
      0x8fdaa3f2,0xed3e1832,0xd6d07d0b,0xdd0ee626,0xdd55e33a,0x14f2b620,0xa6086104,0x730e0d06,
      0x864d1612,0x58fd4ab9,0x7eeead6a,0x66257c7e,0xb667f26f,0x06c82c0a,0xbaa25b73,0xde809b40,
      0xa51c48cc,0xdf06490d,0x1fa35e55,0x492af8ac,0x468d6b4a,0x75ab187a,0x00000013,0x00000000 };
    MyAlign(16) 
    uint yp[] ={
      0x5b9d5017,0x753fe070,0xf8c90cbb,0xbf67c1a5,0x7e8ed1a1,0xd0d1eae0,0xf3fa8eae,0xa3a8ff5d,
      0x9b31821b,0x2be8cb33,0x38645bb6,0xd22cb490,0xfdb0f995,0xb85bba88,0x8e322f35,0x0faf89ba,
      0x8eafdb32,0x2269ebb0,0x1455eed2,0x2bc95949,0xf2482cb5,0x64e1ca49,0xdbda5052,0x4e74118e,
      0x5918eb2a,0x81091ac1,0x22e16efc,0x4c42ad3c,0x0b236029,0x26840098,0xb2b24120,0xcce67df0,
      0xd002f151,0x9e5022e3,0x3f72b07f,0xd81883bd,0xb2bfe173,0xab7a41fa,0x00000075,0x00000000 };
    MyAlign(16) uint x2p[WORDS], y2p[WORDS];

    ec_double( xp, yp, x2p, y2p ); // doubling
	
    MyAlign(16) uint h0[WORDS];
    MyAlign(16) uint h1[WORDS];
    MyAlign(16) uint h2[WORDS];
    MyAlign(16) uint h3[WORDS];
    MyAlign(16) uint *H[] = { h0, h1, h2, h3 };

    // Compute the Tate pairing
    etaT_RL_withSR( xp, yp, x2p, y2p, H );
	
}

Tate Pairing in Characteristic three F₃⁵⁰⁹

/*
Point P(x, y) that satisfies the supersingular elliptic curve 
E(F_3^m): y^2 = x^3 - x + b
x = [2122101221111201020010012111101211122220201112011001011000100200212020000202022211100101221012210
201021200120222220222211222010121011200002120111122100011201111001102200102001210110102210101222200212
111110021200212101221020022102011002211201011210011122001001021102110021001220200010122110211202101110
112210012001210211111021122201001001022101000000201100020102010100011101011111011001201002102102201201
100101012120001011101021111000120021210210202112121102011111212100202012011022012121001021102100110121002]
y = [1000112020020221112102110122122211122020001001211111221012100211220202100022121200001010200200121
010021002212112012110200100102121121212001020110120100010010012012122210200002201102021020212100101021
221212020122202222122121022102222011201222010212202111100221020112201111202222210100211021002201011012
000010102212120021111011001101121100111102221120112010012102102202201211210001011210001102011221102001
011211112002201112221102001222000002022122221020220001010112201220020101222101001202112200220000020112221]
*/
int main()
{
    MyAlign(16) 
    uint datPx[] ={
      0x52414642,0x52866412,0x56642218,0x22599485,0x50182649,0x60115125,0xa1850446,0x50610924, 
      0x40544554,0x21408484,0x104a4400,0x95525a84,0x16906064,0xa5258915,0x241a2011,0x81049494,
      0x58459056,0x20a4850a,0x09826469,0x1aa09955,0x06451291,0x55052812,0x855a4058,0x11916009,
      0x2aa2a96a,0x69212606,0x2a5411a4,0x20988022,0x61411404,0x4656a885,0x61204195,0x009a4695 };
    MyAlign(16) 
    uint datPy[] ={
      0x280085a9,0xa4418968,0x5a1a0846,0xa9228044,0x1a8008a6,0x0a15a948,0x52045956,0x5901485a,
      0x8a196404,0x16106492,0x94154a96,0x25514145,0x80112998,0x52428451,0x562aa442,0x50a485a1,
      0x1a849a25,0x64a4aa16,0x886a2a9a,0x64112699,0x0a148922,0x0619a920,0x85184041,0x49966604,
      0x96194810,0x06442429,0x66004482,0x25a2240a,0x1955a464,0x6a568804,0x2959251a,0x00405882 };
    MyAlign(16) uint x2p[WORDS], y2p[WORDS];

    GF3m xp, yp, x3p, y3p;
    setData( xp, datPx );
    setData( yp, datPy );
    ec_double( xp, yp, x3p, y3p ); // tripling
	
    GF3m R[6];

    // Compute the Tate pairing
    eta_t_RLwCR( R, xp, yp, x3p, y3p );
	
}

O. Ahmadi and F. Rodríguez-Henríquez. Low complexity cubing and cube root computation over F₃^m in standard basis. Cryptology ePrint Archive, Report 2009/070, 2009.
P.S.L.M. Barreto. A note on efficient computation of cube roots in characteristic 3. Cryptology ePrint Archive, Report 2004/305, 2004.
P.S.L.M. Barreto, S.D. Galbraith, C. Ó hÉigeartaigh, and M. Scott. Efficient pairing computation on supersingular Abelian varieties. Designs, Codes and Cryptography, 42:239-271, 2007.
P.S.L.M. Barreto, H.Y. Kim, B. Lynn, and M. Scott. Efficient algorithms for pairing-based cryptosystems. In M. Yung, editor, Advances in Cryptology CRYPTO 2002, number 2442 in Lecture Notes in Computer Science, pages 354-368. Springer, 2002.
P.S.L.M. Barreto and M. Naehrig. Pairing-friendly elliptic curves of prime order. In B. Preneel and S. Tavares, editors, Selected Areas in Cryptography SAC 2005, volume 3897 of Lecture Notes in Computer Science, pages 319-331. Springer, 2006.
J.-L. Beuchat, N. Brisebarre, J. Detrey, E. Okamoto, and F. Rodríguez-Henríquez. A comparison between hardware accelerators for the modied tate pairing over F₂^m and F₃^m. In S.D. Galbraith and K.G. Paterson, editors, Pairing-Based Cryptography Pairing 2008, number 5209 in Lecture Notes in Computer Science, pages 297-315. Springer, 2008.
J.-L. Beuchat, N. Brisebarre, J. Detrey, E. Okamoto, M. Shirase, and T. Takagi. Algorithms and arithmetic operators for computing the ηT pairing in characteristic three. IEEE Transactions on Computers, 57(11):1454-1468, November 2008.
J.-L. Beuchat, J. Detrey, N. Estibals, E. Okamoto, and F. Rodríguez-Henríquez. Hardware accelerator for the Tate pairing in characteristic three based on Karatsuba{Ofman multipliers. In C. Clavier and K. Gaj, editors, Cryptographic Hardware and Embedded Systems CHES 2009, number 5747 in Lecture Notes in Computer Science, pages 225-239. Springer, 2009.
I. Duursma and H.S. Lee. Tate pairing implementation for hyperelliptic curves y² = x^p-x+d. In C.S. Laih, editor, Advances in Cryptology-ASIACRYPT 2003, number 2894 in Lecture Notes in Computer Science, pages 111-123. Springer, 2003.
K. Fong, D. Hankerson, J. Lóopez, and A. Menezes. Field inversion and point halving revisited. IEEE Transactions on Computers, 53(8):1047-1059, August 2004.
S.D. Galbraith, K. Harrison, and D. Soldera. Implementing the Tate pairing. In C. Fieker and D.R. Kohel, editors, Algorithmic Number Theory-ANTS V, number 2369 in Lecture Notes in Computer Science, pages 324-337. Springer, 2002.
P. Grabher, J. Groβschädl, and D. Page. On software parallel implementation of cryptographic pairings. In Selected Areas in Cryptography-SAC 2008, number 5381 in Lecture Notes in Computer Science, pages 34-49. Springer, 2008.
R. Granger, D. Page, and M. Stam. On small characteristic algebraic tori in pairing-based cryptography. LMS Journal of Computation and Mathematics, 9:64- 85, March 2006.
S. Gueron and M.E. Kounavis. Carry-less multiplication and its usage for computing the GCM mode. Intel Corporation White Paper, May 2009.
D. Hankerson, J. Lóopez Hernandez, and A.J. Menezes. Software implementation of elliptic curve cryptography over binary elds. In Ç.K. Koç and C. Paar, editors, Cryptographic Hardware and Embedded Systems-CHES 2000, number 1965 in Lecture Notes in Computer Science, pages 1-24. Springer, 2000.
D. Hankerson, A. Menezes, and M. Scott. Software Implementation of Pairings, chapter 12, pages 188-206. Cryptology and Information Security Series. IOS Press, 2009.
K. Harrison, D. Page, and N.P. Smart. Software implementation of finite fields of characteristic three, for use in pairing-based cryptosystems. LMS Journal of Computation and Mathematics, 5:181-193, November 2002.
F. Hess. Pairing lattices. In S.D. Galbraith and K.G. Paterson, editors, Pairing-Based Cryptography-Pairing 2008, number 5209 in Lecture Notes in Computer Science, pages 18-38. Springer, 2008.
F. Hess, N. Smart, and F. Vercauteren. The Eta pairing revisited. IEEE Transactions on Information Theory, 52(10):4595-4602, October 2006.
D. Kammler, D. Zhang, P. Schwabe, H. Scharwaechter, M. Langenberg, D. Auras, G. Ascheid, R. Leupers, R. Mathar, and H. Meyr. Designing an ASIP for cryptographic pairings over Barreto-Naehrig curves. Cryptology ePrint Archive, Report 2009/056, 2009.
Y. Kawahara, K. Aoki, and T. Takagi. Faster implementation of ηT pairing over GF(3^m) using minimum number of logical instructions for GF(3)-addition. In S.D. Galbraith and K.G. Paterson, editors, Pairing-Based Cryptography-Pairing 2008, number 5209 in Lecture Notes in Computer Science, pages 282-296. Springer, 2008.
J. Lóopez and R. Dahab. High-speed software multiplication in F₂^m. In B.K. Roy and E. Okamoto, editors, Progress in Cryptology - INDOCRYPT 2000, volume 1977 of Lecture Notes in Computer Science, pages 203-212. Springer, 2000.
V.S. Miller. Short programs for functions on curves. Available at http://crypto.stanford.edu/miller, 1986.
V.S. Miller. The Weil pairing, and its efficient calculation. Journal of Cryptology, 17(4):235-261, 2004.
C. Ó hÉigeartaigh. Pairing Computation on Hyperelliptic Curves of Genus 2. PhD thesis, Dublin City University, 2006.
R. Schroeppel, H. Orman, S.W. O'Malley, and O. Spatscheck. Fast key exchange with elliptic curve systems. In D. Coppersmith, editor, Advances in Cryptology-CRYPTO '95, Lecture Notes in Computer Science, pages 43-56. Springer, 1995.
M. Shirase, T. Takagi, D. Choi, D. Han, and H. Kim. Efficient computation of Eta pairing over binary eld with Vandermonde matrix. ETRI Journal, 31(2):129-139, April 2009.
C. Shu, S. Kwon, and K. Gaj. Reconfigurable computing approach for Tate pairing cryptosystems over binary fields. IEEE Transactions on Computers, 58(9):1221-1237, September 2009.
F. Vercauteren. Optimal pairings. Cryptology ePrint Archive, Report 2008/096, 2008.

01 November, 2009 by Luis Martínez-Ramos

Multi-core Implementation of the Tate Pairing over Supersingular Elliptic Curves