On hardware and software implementation of arithmetic in finite fields of characteristic~7 for calculation of pairings

S. B. Gashkov ; A. A. Bolotov ; A. A. Burtsev ; S. Yu. Zhebet ; A. B. Frolov

Fundamentalʹnaâ i prikladnaâ matematika, Tome 15 (2009) no. 3, pp. 75-111.

Résumé

We study scheme (hardware) and program (software) methods of multiplication of polynomials over fields of characteristic 7 in order to apply them to parings based cryptographic protocols on hyperelliptic curves of genus three. We consider hardware and software implementations of arithmetic in $GF(7)$, $GF(7^2)$, $GF(7^n)$, $GF(7^{7n})$, and $GF(7^{14n})$ and estimate the complexity of corresponding schemes and programs.

Bibliographie

[1] Bolotov A. A., Gashkov S. B., Frolov A. B., Chasovskikh A. A., “Programmnye i skhemnye metody umnozheniya mnogochlenov dlya ellipticheskoi kriptografii”, Izv. RAN. Teoriya i sistemy upravleniya, 2000, no. 5, 66–75 | MR

[2] Bolotov A. A., Gashkov S. B., Frolov A. B., Chasovskikh A. A., “O metodakh implementatsii arifmeticheskikh operatsii v kriptograficheskikh sistemakh”, Izv. RAN. Teoriya i sistemy upravleniya, 2002, no. 1, 86–96 | MR

[3] Bolotov A. A., Gashkov S. B., Frolov A. B., Chasovskikh A. A., Elementarnoe vvedenie v ellipticheskuyu kriptografiyu. Algebraicheskie i algoritmicheskie osnovy, Komkniga, M., 2006

[4] Bolotov A. A., Gashkov S. B., Frolov A. B., Chasovskikh A. A., Elementarnoe vvedenie v ellipticheskuyu kriptografiyu. Protokoly kriptografii na ellipticheskikh krivykh, KomKniga, M., 2006

[5] Zhebet S. Yu., “Sravnitelnyi analiz algoritmov umnozheniya binarnykh mnogochlenov v polinomialnom bazise”, Vestn. MEI, 2006, no. 6, 52–61

[6] Karatsuba A. A., Ofman Yu. P., “Umnozhenie mnogoznachnykh chisel na avtomatakh”, DAN SSSR, 145:2 (1962), 293–294

[7] Toom A. L., “O slozhnosti skhemy iz funktsionalnykh elementov, realizuyuschei umnozhenie tselykh chisel”, DAN SSSR, 150 (1963), 496–498 | MR | Zbl

[8] Noden P., Kitte K., Algebraicheskaya algoritmika, Mir, M., 1999

[9] Bailey D. V., Paar C., “Efficient arithmetic in finite field extensions with application in elliptic curve cryptography”, J. Cryptology, 14:3 (2001), 156–173 | MR

[10] Barreto P. S. L. M., Kim H. Y., Lynn B., Scott M., “Efficient algorithms for pairing-based cryptosystems”, Advances in Cryptology – CRYPTO 2002, Lect. Notes Comput. Sci., 2442, Springer, Berlin, 2002, 354–369 | DOI | MR

[11] Barreto P. S. M. L., Galbraith S., Ó hÉigeartaigh C., Scott M., Efficient pairing computation on supersingular Abelian varieties, Cryptology ePrint Archive, Report 2004/375 http://eprint.iacr.org/2004/375

[12] Beuchat J.-L., Shiraze M., Takagi T., Okamoto E., An algorithm for the $\eta_T$-pairing calculation in characteristic three and its hardware implementation., Cryptology ePrint Archive, Report 2006/327 http://eprint.iacr.org/2006/327

[13] Blake I., Seroussi G., Smart N., Elliptic Curves in Cryptography, Cambridge Univ. Press, Cambridge, 1999 | MR | Zbl

[14] Blake I., Seroussi G., Smart N., Advances in Elliptic Curve Cryptograhy, Cambridge Univ. Press, Cambridge, 2005 | MR | Zbl

[15] Boneh D., Franklin M., “Identity-based encryption from the Weil pairing”, Advances in Cryptology – CRYPTO 2001, Lect. Notes Comput. Sci., 2139, Springer, Berlin, 2001, 213–229 | DOI | MR | Zbl

[16] Boneh D., Lynn B., Shacham H., “Short signatures from the Weil pairing”, Asiacrypt-2001, Lect. Notes Comput. Sci., 2248, Springer, Berlin, 2002, 514–532 | DOI | MR

[17] Duursma I., Lee H.-S., “Tate pairing implementation for hyperelliptic curves $y^2=x^p-x+d$”, Asiacrypt-2003, Lect. Notes Comput. Sci., 2894, Springer, Berlin, 2003, 111–123 | DOI | MR | Zbl

[18] Duursma I., Lee H.-S., Tate pairing implementation for tripartite key agreement, Cryptology ePrint Archive, Report 2003/053 http://eprint.iacr.org/2003/053

[19] Granger R., Page D., Stam M., “Hardware and software normal basis arithmetic for pairing based cryptography in characteristic three”, IEEE Trans. Comput., 54:7 (2005), 852–860 | DOI

[20] Hess F., Exponent group signature schemes and efficient identity based signature schemes based on pairings., Cryptology ePrint Archive, Report 2002/012 http://eprint.iacr.org/2002/012 | MR

[21] Joux A., “A one-round protocol for tripartite Diffie–Hellman”, Algorithm Number Theory Symposium – ANTS IV, Lect. Notes Comput. Sci., 1838, Springer, Berlin, 2000, 385–394 | DOI | MR

[22] Kerins T., Marname W. P., Popovici E. M., Barreto P. S. L. M., “Efficient hardware for Tate pairing calculation in characteristic three”, Cryptographic Hardware and Embedded Systems – CHES 2005, Lect. Notes Comput. Sci., 3659, Springer, Berlin, 2005, 412–426 | DOI

[23] Kwon S., Efficient Tate pairing computation for supersingular elliptic curves over binary fields, Cryptology ePrint Archive, Report 2004/303 http://eprint.iacr.org/2004/303

[24] Lee E., Lee H.-S., Lee Y., Fast computation of Tate pairing on general divisors for hyperelliptic curves of genus 3, Cryptology ePrint Archive, Report 2006/125 http://eprint.iacr.org/2006/125

[25] Page D., Smart N. P., “Hardware implementation of finite fields of characteristic three”, Cryptographic Hardware and Embedded Systems – CHES 2002, Lect. Notes Comput. Sci., 2523, Springer, Berlin, 2003, 283–295

[26] Scott M., Barreto P. S. M. L., “Compressed pairing”, Advances in Cryptology – CRYPTO 2004, Lect. Notes Comput. Sci., 3152, Springer, Berlin, 2004, 140–156 | DOI | MR | Zbl

[27] Shiraze M., Takagi T., Okamoto E., Some efficient algorithms for the final exponentiation of an $\eta_T$-pairing, Cryptology ePrint Archive, Report 2006/431 http://eprint.iacr.org/2006/431