Squaring in cyclotomic subgroups

Karabina, Koray

doi:10.1090/S0025-5718-2012-02625-1

Squaring in cyclotomic subgroups
HTML articles powered by AMS MathViewer

by Koray Karabina PDF

Math. Comp. 82 (2013), 555-579 Request permission

Abstract:

We propose new squaring formulae for cyclotomic subgroups of the multiplicative group of certain finite fields. Our formulae use a compressed representation of elements having the property that decompression can be performed at a very low cost. The squaring formulae lead to new exponentiation algorithms in cyclotomic subgroups which outperform the fastest previously-known exponentiation algorithms when the exponent has low Hamming weight. Our algorithms can be adapted to accelerate the final exponentiation step of pairing computations.

References

D. Aranha, K. Karabina, P. Longa, C. Gebotys, and J. López, Faster explicit formulas for computing pairings over ordinary curves, Advances in Cryptology - Eurocrypt 2011, Lecture Notes in Computer Science 6632 (2011), 48–68.
Paulo S. L. M. Barreto and Michael Naehrig, Pairing-friendly elliptic curves of prime order, Selected areas in cryptography, Lecture Notes in Comput. Sci., vol. 3897, Springer, Berlin, 2006, pp. 319–331. MR 2241646, DOI 10.1007/11693383_{2}2
Naomi Benger and Michael Scott, Constructing tower extensions of finite fields for implementation of pairing-based cryptography, Arithmetic of finite fields, Lecture Notes in Comput. Sci., vol. 6087, Springer, Berlin, 2010, pp. 180–195. MR 2674223, DOI 10.1007/978-3-642-13797-6_{1}3
J. Beuchat, J. Díaz, S. Mitsunari, E. Okamoto, F. Rodríguez-Henríquez, and T. Teruya, High-speed software implementation of the optimal Ate pairing over Barreto-Naehrig curves, Pairing-Based Cryptography – Pairing 2010, Lecture Notes in Computer Science 6487 (2010), 21–39.
A. Brouwer, R. Pellikaan, and E. Verheul, Doing more with fewer bits, Advances in Cryptology – ASIACRYPT ’99, Lecture Notes in Computer Science 1716 (1999), 321–332.
J. Chung and M. Hasan, Asymmetric squaring formulae, 18th IEEE Symposium on Computer Arithmetic – ARITH 2007 (2007), 113–122.
David Freeman, Michael Scott, and Edlyn Teske, A taxonomy of pairing-friendly elliptic curves, J. Cryptology 23 (2010), no. 2, 224–280. MR 2578668, DOI 10.1007/s00145-009-9048-z
K. Giuliani and G. Gong, Analogues to the Gong-Harn and XTR cryptosystems, Technical Report CORR 2003-34, University of Waterloo (2003), Available at http://www.cacr.math.uwaterloo.ca/techreports/2003/corr2003-34.ps.
Guang Gong and Lein Harn, Public-key cryptosystems based on cubic finite field extensions, IEEE Trans. Inform. Theory 45 (1999), no. 7, 2601–2605. MR 1725159, DOI 10.1109/18.796413
R. Granger, D. Page, and N. P. Smart, High security pairing-based cryptography revisited, Algorithmic number theory, Lecture Notes in Comput. Sci., vol. 4076, Springer, Berlin, 2006, pp. 480–494. MR 2282944, DOI 10.1007/11792086_{3}4
R. Granger, D. Page, and M. Stam, A comparison of CEILIDH and XTR, Algorithmic number theory, Lecture Notes in Comput. Sci., vol. 3076, Springer, Berlin, 2004, pp. 235–249. MR 2137357, DOI 10.1007/978-3-540-24847-7_{1}7
Robert Granger and Michael Scott, Faster squaring in the cyclotomic subgroup of sixth degree extensions, Public key cryptography—PKC 2010, Lecture Notes in Comput. Sci., vol. 6056, Springer, Berlin, 2010, pp. 209–223. MR 2660744, DOI 10.1007/978-3-642-13013-7_{1}3
D. Harris, Simultaneous field divisions: an extension of Montgomery’s trick,(2008), Available at http://eprint.iacr.org/2008/199.
Koray Karabina, Double-exponentiation in factor-4 groups and its applications, Cryptography and coding, Lecture Notes in Comput. Sci., vol. 5921, Springer, Berlin, 2009, pp. 336–350. MR 2775632, DOI 10.1007/978-3-642-10868-6_{2}0
Koray Karabina, Factor-4 and 6 compression of cyclotomic subgroups of $\Bbb F^*_{2^{4m}}$ and $\Bbb F^*_{3^{6m}}$, J. Math. Cryptol. 4 (2010), no. 1, 1–42. MR 2660332, DOI 10.1515/JMC.2010.001
—, Torus-based compression by factor 4 and 6, Accepted for publication in IEEE Transactions on Information theory, DOI 10.1109/TIT.2012.2184846; Earlier version available at http://eprint.iacr.org/2010/525.
Neal Koblitz and Alfred Menezes, Pairing-based cryptography at high security levels, Cryptography and coding, Lecture Notes in Comput. Sci., vol. 3796, Springer, Berlin, 2005, pp. 13–36. MR 2235246, DOI 10.1007/11586821_{2}
Arjen K. Lenstra and Eric R. Verheul, The XTR public key system, Advances in cryptology—CRYPTO 2000 (Santa Barbara, CA), Lecture Notes in Comput. Sci., vol. 1880, Springer, Berlin, 2000, pp. 1–19. MR 1850033, DOI 10.1007/3-540-44598-6_{1}
Chae Hoon Lim and Hyo Sun Hwang, Fast implementation of elliptic curve arithmetic in $\textrm {GF}(p^n)$, Public key cryptography (Melbourne, 2000) Lecture Notes in Comput. Sci., vol. 1751, Springer, Berlin, 2000, pp. 405–421. MR 1864790, DOI 10.1007/978-3-540-46588-1_{2}7
Peter L. Montgomery, Speeding the Pollard and elliptic curve methods of factorization, Math. Comp. 48 (1987), no. 177, 243–264. MR 866113, DOI 10.1090/S0025-5718-1987-0866113-7
Yasuyuki Nogami, Masataka Akane, Yumi Sakemi, Hidehiro Kato, and Yoshitaka Morikawa, Integer variable $\chi$-based Ate pairing, Pairing-based cryptography—Pairing 2008, Lecture Notes in Comput. Sci., vol. 5209, Springer, Berlin, 2008, pp. 178–191. MR 2733913, DOI 10.1007/978-3-540-85538-5_{1}3
Karl Rubin and Alice Silverberg, Torus-based cryptography, Advances in cryptology—CRYPTO 2003, Lecture Notes in Comput. Sci., vol. 2729, Springer, Berlin, 2003, pp. 349–365. MR 2093203, DOI 10.1007/978-3-540-45146-4_{2}1
K. Rubin and A. Silverberg, Compression in finite fields and torus-based cryptography, SIAM J. Comput. 37 (2008), no. 5, 1401–1428. MR 2386274, DOI 10.1137/060676155
Michael Scott, Implementing cryptographic pairings, Pairing-based cryptography—Pairing 2007, Lecture Notes in Comput. Sci., vol. 4575, Springer, Berlin, 2007, pp. 177–196. MR 2423639
M. Shirase, D. Han, Y. Hibin, H. Kim, and T. Takagi, A more compact representation of XTR cryptosystem, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E91-A (2008), 2843–2850.
P. Smith and C. Skinner, A public-key cryptosystem and a digital signature system based on the Lucas function analogue to discrete logarithms, Advances in Cryptology – ASIACRYPT ’94, Lecture Notes In Computer Science 917 (1994), 357–364.
Martijn Stam and Arjen K. Lenstra, Speeding up XTR, Advances in cryptology—ASIACRYPT 2001 (Gold Coast), Lecture Notes in Comput. Sci., vol. 2248, Springer, Berlin, 2001, pp. 125–143. MR 1934519, DOI 10.1007/3-540-45682-1_{8}
—, Efficient subgroup exponentiation in quadratic and sixth degree extensions, Cryptographic Hardware and Embedded Systems – CHES 2002 2523 (2003), 159–174.
Marten van Dijk, Robert Granger, Dan Page, Karl Rubin, Alice Silverberg, Martijn Stam, and David Woodruff, Practical cryptography in high dimensional tori, Advances in cryptology—EUROCRYPT 2005, Lecture Notes in Comput. Sci., vol. 3494, Springer, Berlin, 2005, pp. 234–250. MR 2352191, DOI 10.1007/11426639_{1}4
Marten van Dijk and David Woodruff, Asymptotically optimal communication for torus-based cryptography, Advances in cryptology—CRYPTO 2004, Lecture Notes in Comput. Sci., vol. 3152, Springer, Berlin, 2004, pp. 157–178. MR 2147501, DOI 10.1007/978-3-540-28628-8_{1}0