Waldyr Dias Benits Junior (2009) Applications of Frobenius Expansions in Elliptic Curve Cryptography.
Full text access: Open
Recent developments in elliptic curve cryptography have heightened the need for fast scalar point multiplication, specially when working on environments with limited computational power. It is well known that point multiplication on elliptic curves over F_{q^m} (with m > 1) can be accelerated using Frobenius expansions. In practice, the computation is much faster than the standard double-and-add scalar multiplication. An efficient implementation of elliptic curve cryptosystems can use a Koblitz curve and convert integers into Frobenius expansions to perform fast scalar multiplications. However, this conversion of integers to Frobenius expansions would lead to extra code on the device (i.e., silicon area) and extra computational cost. According to N. Koblitz, H. Lenstra suggested that rather than choosing a random integer n and then converting to a Frobenius expansion n(\tau), in certain cryptosystems it might be more efficient to generate a random Frobenius expansion directly. The temptation then is to choose a relatively short and/or sparse value for n(\tau). If this is done then we must re-evaluate the difficulty of the discrete logarithm problem (and other computational problems). A further issue is that the existing security proofs may not directly apply. For some systems it may be necessary to develop bespoke security proofs for the Frobenius expansion case. In this thesis, we analyse the Frobenius expansion DLP and present algorithms to solve it. Furthermore, we propose a variant of a well known identification scheme designed for public key cryptography on very restricted devices. More precisely, we construct the Girault-Poupard-Stern (GPS) identification scheme for Koblitz elliptic curves using Frobenius expansions. The idea is to use Frobenius expansions throughout the protocol, so there is no need to convert between integers and Frobenius expansions. We also give a security analysis of the proposed scheme.
This is a Published version This version's date is: 04/03/2009 This item is peer reviewed
https://repository.royalholloway.ac.uk/items/dfacbd71-8755-e989-6a2a-88d8529f47e6/1/
Deposited by () on 24-Jun-2010 in Royal Holloway Research Online.Last modified on 15-Dec-2010
[1] R. Avanzi, M. Ciet, and F. Sica. Faster Scalar Multiplication on KoblitzCurves Combining Point Halving with the Frobenius Endomorphism.In Public Key Cryptography, PKC 2004, pages 28{40, 2004.
[2] R. Avanzi, H. Cohen, C. Doche, G. Frey, T. Lange, K. Nguyen, andF. Vercauteren. Handbook of Elliptic and Hyperelliptic Curve Cryptog-raphy, volume 34 of Discrete Mathematics and Its Applications. CRCPress, 2005.
[3] R. Avanzi, V. Dimitrov, C. Doche, and F. Sica. Extending ScalarMultiplication Using Double Bases. In X. Lai and K. Chen, editors,ASIACRYPT 2006 - 12th International Conference on the Theory andApplication of Cryptology and Information Security, volume 4284 ofLectures Notes in Computer Science, pages 130{144, Shangai, China,December 2006. Springer.
[4] R. Avanzi, C. Heuberger, and H. Prodinger. Minimality of the Ham-ming Weight of the ¿-NAF for Koblitz Curves and Improved Combi-nation with Point Halving. In B. Preneel and S. Tavares, editors, Se-lected Areas in Cryptography, 12th International Workshop, SAC 2005,volume 3897 of Lectures Notes in Computer Science, Kingston, ON,Canada, August, 11{12 2005. Springer Berlin / Heidelberg.
[5] R. Avanzi, H. Prodinger, and C. Heuberger. Scalar Multiplication onKoblitz Curves Using the Frobenius Endomorphism and its Combina-tion with Point Halving: Extensions and Mathematical Analysis. InAlgorithmica Special Issue on Analysis of Algorithms, volume 46 of Al-gorithmica, pages 249{270, 2006.
[6] R. Avanzi and F. Sica. Scalar Multiplication on Koblitz Curves UsingDouble Bases. In P. Nguyen, editor, Vietcrypt 2006 - First InternationalConference on Cryptology in Vietnam, volume 4341 of Lectures Notesin Computer Science, pages 131{146, Hanoi, Vietnam, September 2006.Springer.
[7] M. Bellare and P. Rogaway. Random Oracles are Practical: A Paradigmfor Designing E±cient Protocols. In ACM Conference on Computer andCommunications Security, pages 62{73, 1993.
[8] W. Benits and S. Galbraith. The GPS Identi¯cation Scheme UsingFrobenius Expansions, 2007. To appear in WEWOrC 2007 - LCNS4945.
[9] I. Blake, G. Seroussi, and N. Smart, editors. Advances in Elliptic CurveCryptography, volume 317 of London Mathematical Society. CambridgeUniversity Press, New York, NY, USA, 2005.
[10] W. Bosma, J. Cannon, and C. Playoust. The MAGMA Algebra Sys-tem I: The User Language. Journal of Symbolic Computation, 24(3-4):235{265, 1997.
[11] R. Brent. An improved Monte Carlo factorization algorithm. BITNumerical Mathematics, 20:176{184, 1980.
[12] B. Brumley and K. JÄarvinen. Koblitz Curves and Integer Equivalentsof Frobenius Expansions. In C. Adams, A. Miri, and M. Wiener, ed-itors, Selected Areas in Cryptography, 14th International Workshop|SAC '07, volume 4876 of Lecture Notes in Computer Science, pages126{137. Springer-Verlag, 2007.
[13] P. Cameron. Combinatorics - Topics, Techniques, Algorithms. Cam-bridge University Press, 1994.
[14] J.-H. Cheon and H.-T. Kim. Analysis of Low Hamming Weight Prod-ucts. To appear in Discrete Appl. Math.
[15] E. G. Co®man, P. Flajolet, L. Flatto, and M. Hofri. The Maximum ofa Random Walk and Its Application to Rectangle Packing. Probabilityin Engineering and Informational Sciences, 12:373{386, 1998.
[16] H. Cohen. A Course in Computational Algebraic Number Theory. Grad-uate Texts in Mathematics. Springer-Verlag, New York, NY, USA, 1993.
[17] T. Cormen, C. Leiserson, R. Rivest, and C. Stein. Introduction toAlgorithms. MIT Press and McGraw-Hill, 2nd edition, 2001.
[18] J. Coron, D. M'Raijhi, and C. Tymen. Fast Generation of Pairs (k; [k]P)for Koblitz Elliptic Curves. In S. Vaudenay and M. Youssef, editors,Selected Areas in Cryptography, 8th Annual International Workshop,SAC 2001, volume 2259 of Lecture Notes in Computer Science, pages151{164, Toronto, Ontario, Canada, August 2001. Springer-Verlag.
[19] J.S. Coron, D. Lefranc, and G. Poupard. A New Baby-Step Giant-Step Algorithm and Some Applications to Cryptanalysis. In J. Raoand B Sunar, editors, Cryptographic Hardware and Embedded Systems- CHES 2005, 7th International Workshop, volume 3659 of LecturesNotes in Computer Science, pages 47{60, Edinburgh, UK, August 29 -September 1 2005. Springer Berlin / Heidelberg.
[20] W. Di±e and M. Hellman. New Directions in Cryptography. IEEETransactions on Information Theory, IT-22(6):644{654, 1976.
[21] N. Ebeid and M. Hasan. On ¿ -adic Representations of Integers. Designs,Codes and Cryptography, 45(3):271{296, 2007.[22] U. Feige, A. Fiat, and A. Shamir. Zero-Knowledge Proofs of Identity.Journal of Cryptology, 1(2):77{94, 1988.
[23] S. Galbraith. Elliptic Curve Cryptography. Available in:http://www.isg.rhul.ac.uk/ sdg/ecc.html.
[24] R. Gallant, R. Lambert, and S. Vanstone. Improving the ParallelizedPollard Lambda Search on Anomalous Binary Curves. Mathematics ofComputation, 69(232):1699{1705, 2000.
[25] P. Gaudry and E. Schost. A Low-Memory Parallel Version of Matsuo,Chao and Tsujii's Algorithm. In D. Buel, editor, Algorithmic Num-ber Theory, 6th International Symposium, ANTS-VI, volume 3076 ofLectures Notes in Computer Science, pages 208{222, Burlington, VT,USA, June, 13{18 2004. Springer.
[26] M. Girault. Self-Certi¯ed Public Keys. In D.W. Davies, editor, Ad-vances in Cryptology { EUROCRYPT 1991, Workshop on the Theoryand Application of of Cryptographic Techniques, volume 547 of LecturesNotes in Computer Science, pages 490{497, Brighton, UK, April, 8{111992. Springer-Verlag.
[27] M. Girault and D. Lefranc. Public Key Authentication with One (On-line) Single Addition. In M. Joye and J.J. Quisquater, editors, Cryp-tographic Hardware and Embedded Systems - CHES 2004: 6th Interna-tional Workshop, Lectures Notes in Computer Science, pages 413{427,Cambridge, MA, USA, August 11{13 2004. Springer.
[28] M. Girault, G. Poupard, and J. Stern. On the Fly Authentication andSignature Schemes Based on Groups of Unknown Order. Journal ofCryptology, 19(4):463{487, October 2006.
[29] O. Goldreich. Zero-Knowledge Twenty Years After its Invention. Avail-able in: citeseer.ist.psu.edu/goldreich02zeroknowledge.html, 2002.
[30] S. Goldwasser, S. Micali, and C. Racko®. The Knowledge Complexityof Interactive Proof Systems. SIAM J. Comput., 18(1):186{208, 1989.
[31] C. GÄunther, T. Lange, and A. Stein. Speeding up the Arithmetic onKoblitz Curves of Genus Two. In D. R. Stinson and S. E. Tavares, ed-itors, Selected Areas in Cryptography, 7th Annual International Work-shop, SAC 2000, Proceedings, volume 2012 of Lecture Notes in Com-puter Science, pages 106{117, Waterloo, Ontario, Canada, August, 14{15 2000. Springer.
[32] J.Ho®stein and J. Silverman. Random Small Hamming Weight Prod-ucts with Applications to Cryptography. Discrete Applied Mathematics,130(1):37{49, 2003.
[33] N. Koblitz. CM-Curves with Good Cryptographic Properties. InJ. Feigenbaum, editor, Advances in Cryptology - CRYPTO '91, 11thAnnual International Cryptology Conference, volume 576 of LecturesNotes in Computer Science, pages 279{287, London, UK, August, 11{15 1992. Springer-Verlag.
[34] T. Lange. Koblitz Curve Cryptosystems. Finite Fields and Their Ap-plications, 11, Issue 2:200{229, April 2005.
[35] T. Lange and I. Shparlinski. Collisions in Fast Generation of IdealClasses and Points on Hyperelliptic and Elliptic Curves. In ApplicableAlgebra in Engineering, Communication and Computing, volume 15,pages 329{337. Springer, 2005.
[36] W. Meier and O. Sta®elbach. E±cient Multiplication on Certain Non-supersingular Elliptic Curves. In E. Brickell, editor, Advances in Cryp-tology - CRYPTO '92, 12th Annual International Cryptology Confer-ence, volume Volume 740 of Lectures Notes in Computer Science, page333, Santa Barbara, California, USA, August, 16{20 1992. SpringerBerlin / Heidelberg.
[37] A. Menezes, P van Oorschot, and S. Vanstone. Handbook of AppliedCryptography. CRC Press, 2001.
[38] A. Menezes and S. A. Vanstone. Elliptic Curve Cryptosystems andtheir Implementation. Journal of Cryptology, 6:209{224, 1993.
[39] F. Mosteller, R. E. K. Rourke, and G. B. Thomas. Probability andStatistics. Reading, MA, 1961.
[40] T. Okamoto, H. Katsuno, and E. Okamoto. A Fast Signature SchemeBased on New Online Computation. In J. S. Sichman, F. Bousquet,and P. Davidsson, editors, Multi-Agent-Based Simulation, Third In-ternational Workshop, MABS 2002, volume 2581 of Lectures Notes In Computer Science, pages 111{121, Bologna, Italy, July, 15{16 2003.Springer.
[41] J. Pollard. Monte Carlo Methods for Index Computation mod p. Math-ematics of Computation, 32:918{924, 1978.
[42] J. Pollard. Kangaroos, Monopoly and Discrete Logarithms. Journal ofCryptology, 13(4):437{447, December 2000.
[43] G. Poupard and J. Stern. Security Analysis of a Practical \on the°y" Authentication and Signature Generation. In K. Nyberg, editor,Advances in Cryptology - EUROCRYPT '98, International Conferenceon the Theory and Application of Cryptographic Techniques, volume1403 of Lecture Notes in Computer Science, pages 422{436, Espoo,Finland, May 31 - June 4 1998. Springer.
[44] G. Qiao and K.-Y. Lam. RSA Signature Algorithm for Microcon-troller Implementation. In J.-J. Quisquater and B. Schneier, editors,Smart Card Research and Applications, This International Conference,CARDIS '98, volume 1820 of Lectures Notes in Computer Science,pages 353{356, Louvain-la-Neuve, Belgium, September, 14{16 2000.Springer.
[45] C. P. Schnorr. E±cient Signature Generation by Smart Cards. Journalof Cryptology, 4(3):161{174, 1991.
[46] C.P. Schnorr. E±cient Identi¯cation and Signatures for Smart Cards. InG. Brassard, editor, Advances in Cryptology - CRYPTO '89, 9th AnnualInternational Cryptology Conference, volume 435 of Lecture Notes inComputer Science, pages 235{251, Santa Barbara, California, USA,August, 20{24 1990. Springer Verlag.
[47] R. Sedgewick, T. Szymanski, and A. Chi-Chih Yao. The complexityof ¯nding cycles in periodic functions. SIAM Journal of Computation,11(2):376{390, 1982.
[48] N. Smart. Elliptic Curve Cryptosystems over Small Fields of Odd Char-acteristic. Journal of Cryptology, 12(2):141{151, 1999.
[49] N. Smart. Cryptography: An Introduction. McGraw-Hill, December2004.
[50] J. Solinas. An Improved Algorithm for Arithmetic on a Family of Ellip-tic Curves. In B Kaliski Jr, editor, Advances in Cryptology - CRYPTO'97, 17th Annual International Cryptology Conference, volume 1294 ofLectures Notes in Computer Science, pages 357{371, Santa Barbara,California, USA, August, 17{21 1997. Springer-Verlag.
[51] J. Solinas. E±cient Arithmetic on Koblitz Curves. Designs Codes andCryptography, 19(2-3):195{249, 2000.
[52] W. Stallings. Cryptography and Network Security: Principles and Prac-tice. Prentice Hall, third edition, 2002.
[53] D. Stinson. Some Baby-Step Giant-Step Algorithms for the Low Ham-ming Weight Discrete Logarithm Problem. Mathematics of Computa-tion, 71(237):379{391, 2002.
[54] D. Stinson. Cryptography Theory and Practice. Discrete Mathematicsand its Applications. Chapman & Hall, third edition, 2006.
[55] E. Teske. Square-root Algorithms for the Discrete Logarithm Prob-lem (A Survey). In W. Gruyter, editor, Public-key Cryptography andComputational Number Theory, pages 283{301, 2001.
[56] Edlyn Teske. Computing discrete logarithms with the parallelized kan-garoo method. Discrete Applied Mathematics, 130(1):61{82, 2003.
[57] P. van Oorschot and M. Wiener. Improving Implementable Meet-In-The-Middle Attacks by Orders of Magnitude. In N. Koblitz, editor, Ad-vances in Cryptology - CRYPTO '96, 16th Annual International Cryp-tology Conference, volume 1109 of Lectures Notes in Computer Science,pages 229{236, Santa Barbara, California, USA, August, 18{22 1996.Springer.
[58] P. van Oorschot and M. Wiener. Parallel Collision Search with Crypt-analytic Applications. Journal of Cryptology, 12(1):1{28, 1999.
[59] E. Weisstein. Random Walk{1-Dimensional - FromMathWorld - A Wolfram Web Resource. Available in:http://mathworld.wolfram.com/RandomWalk1-Dimensional.html.
[60] M. J. Wiener and R. J. Zuccherato. Faster Attacks on Elliptic CurveCryptosystems. In S. Tavares and H. Meijer, editors, Selected Areas inCryptography '98, SAC'98, volume 1556 of Lectures Notes In ComputerScience, pages 190{200, Kingston, Ontario, Canada, August, 17{181999. Springer.