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

Abstract
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 F3509, 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?
Keywords
Tate pairing, ηT pairing, supersingular curve, finite field arithmetic, multi-core
Download
The latest version: Source of Tate pairing in characteristic two F21223
The latest version: Source of Tate pairing in characteristic three F3509
ePrint
To appear in: CANS 2009 - The 8th International Conference on Cryptology And Networks Security (12-14 Dec. 2009)
Hardware Requirements
CPU
Intel Core 2 Duo or later (ESSE3 is required)
Software Requirements
OS
Windows Xp/Vista 32/64-bit version
The implementation for multi-core supports only Windows.
C++ compiler
Visual Studio 2008
Build on Windows
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"
Benchmark
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]
ModeF21223F3509
Tate pairing (single-core)11.197.59
Tate pairing (2-cores)6.724.31
Tate pairing (4-cores)4.222.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 F21223 F3509
Tate pairing (single-core)7.945.22
Tate pairing (2-cores)4.533.16
Tate pairing (4-cores)3.132.31
Tate pairing (8-cores)3.081.87
Sample
Tate Pairing in Characteristic two F21223
/*
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 F3509
/*
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 );
	
}
References
Last Update:
01 November, 2009 by Luis Martínez-Ramos
e-mail: Luis Martínez-Ramos - luis.mtzr@gmail.com