Linear Complexity of Sequences on Koblitz Curves of Genus 2

Anupindi, Vishnupriya

doi:10.2478/udt-2022-0010

Abstract

In this paper, we consider the hyperelliptic analogue of the Frobenius endomorphism generator and show that it produces sequences with large linear complexity on the Jacobian of genus 2 curves.

References

[1] ANUPINDI, V.—MÉRAI, L.: Linear complexity of some sequences derived from hyper-elliptic curves of genus 2, Cryptogr. Commun. 14 (2022), 117–134.10.1007/s12095-021-00521-y
Search in Google Scholar Back to article
[2] Handbook of Elliptic and Hyperelliptic Curve Cryptography. (H. Cohen, G. Frey, R. Avanzi, C. Doche, T. Lange, K. Nguyen, F. Vercauteren, eds.). Discrete Mathematics and its Applications (Boca Raton). Chapman & Hall/CRC, Boca Raton, FL, 2006.
Search in Google Scholar Back to article
[3] GALBRAITH, S. D.: Mathematics of Public Key Cryptography. Cambridge University Press, Cambridge, 2012.10.1017/CBO9781139012843
Search in Google Scholar Back to article
[4] GRANT, D.: Formal groups in genus two,J.Reine Angew. Math. 411 (1990), 96–121.
Search in Google Scholar Back to article
[5] GÜNTHER, C.—LANGE, T.—STEIN, A.: Speeding up the arithmetic on Koblitz curves of genus two.In: Selected Areas in Cryptography (Waterloo, ON, 2000),In: Lecture Notes in Comput. Sci. Vol. 2012, Springer, Berlin, 2001, pp. 106–117.
Search in Google Scholar Back to article
[6] HARTSHORNE, R.: Algebraic Geometry.In: Graduate Texts in Mathematics, No. 52. Springer-Verlag, New York-Heidelberg, 1977.10.1007/978-1-4757-3849-0
Search in Google Scholar Back to article
[7] HINDRY, M.—SILVERMAN, J. H.: Diophantine Geometry (An introduction). In: Graduate Texts in Math. Vol. 201, Springer-Verlag, New York, 2000.
Search in Google Scholar Back to article
[8] KOBLITZ, N.: CM-curves with good cryptographic properties. In:Advances in Cryptology—CRYPTO ’91 (Santa Barbara, CA, 1991),In:Lecture Notes in Comput. Sci. Vol. 576, Springer-Verlag, Berlin, 1992. pp. 279–287.10.1007/3-540-46766-1_22
Search in Google Scholar Back to article
[9] KOBLITZ, N.: Algebraic Aspects of Cryptography. (With an appendix by Alfred J. Menezes, Yi-Hong Wu and Robert J. Zuccherato). In: Algorithms and Computation in Mathematics Vol. 3, Springer-Verlag, Berlin, 1998.10.1007/978-3-662-03642-6_1
Search in Google Scholar Back to article
[10] LACHAUD, G.—ROLLAND, R.: On the number of points of algebraic sets over finite fields, J. Pure Appl. Algebra 219 (2015), 5117–5136.10.1016/j.jpaa.2015.05.008
Search in Google Scholar Back to article
[11] LANGE, T.: Koblitz curve cryptosystems, Finite Fields Appl. 11 (2005), 200–229.10.1016/j.ffa.2004.07.001
Search in Google Scholar Back to article
[12] LANGE, T.—SHPARLINSKI, I.: Collisions in fast generation of ideal classes and points on hyperelliptic and elliptic curves, Appl. Algebra Engrg. Comm. Comput. 15 (2005), 329–337.10.1007/s00200-004-0161-9
Search in Google Scholar Back to article
[13] LANGE, T.—SHPARLINSKI, I. E.: Certain exponential sums and random walks on elliptic curves, Canad. J. Math. 57 (2005), 338–350.10.4153/CJM-2005-015-8
Search in Google Scholar Back to article
[14] LANGE, T.—SHPARLINSKI, I. E.: Distribution of some sequences of points on elliptic curves,J. Math. Cryptol. 1 (2007), 1–11.10.1515/JMC.2007.001
Search in Google Scholar Back to article
[15] MEIDL, W.—WINTERHOF, A.: Linear Complexity of Sequences and Multisequences. In: Handbook of Finite Fields. CRC Press, Boca Raton, 2013.
Search in Google Scholar Back to article
[16] MÉRAI, L.: On pseudorandom properties of certain sequences of points on elliptic curve. In: Arithmetic of Finite Fields,In: Lecture Notes in Comput. Sci. Vol. 10064, Springer, Cham, 2016. pp. 54–63.
Search in Google Scholar Back to article
[17] MÜLLER, V.: Fast multiplication on elliptic curves over small fields of characteristic two, J. Cryptology 11 (1998), 219–234.10.1007/s001459900045
Search in Google Scholar Back to article
[18] MUMFORD, D.: Tata Lectures on Theta. II. Jacobian theta functions and differential equations, With the collaboration of C. Musili, M. Nori, E. Previato, M. Stillman and H. Umemura, Modern Birkh¨auser Classics. Birkh¨auser Boston, Inc., Boston, MA, 2007. (Reprint of the 1984 original).
Search in Google Scholar Back to article
[19] NIEDERREITER, H.: Linear complexity and related complexity measures for sequences. In: Progress in Cryptology—INDOCRYPT 2003, Lecture Notes in Comput. Sci. Vol. 2904, Springer-Verlag, Berlin, 2003, pp. 1–17.
Search in Google Scholar Back to article
[20] SMART, N. P.: Elliptic curve cryptosystems over small fields of odd characteristic, J.Cryptology 12 (1999), 141–151.10.1007/PL00003820
Search in Google Scholar Back to article
[21] SOLINAS,J.A.: Efficient arithmetic on Koblitz curves. Towards a quarter-century of public key cryptography. vol. 19, 2000, pp. 195–249.10.1007/978-1-4757-6856-5_6
Search in Google Scholar Back to article
[22] STICHTENOTH, H.: Algebraic function fields and codes (2nd edition) In: Graduate Texts in Mathematics Vol. 254, Springer-Verlag, Berlin, 2009.10.1007/978-3-540-76878-4
Search in Google Scholar Back to article
[23] WINTERHOF, A.: Linear complexity and related complexity measures.In:Selected Topics in Information and Coding Theory, Ser. Coding Theory Crypto. Vol. 7 World Sci. Publ. Hackensack, NJ, 2010, pp. 3–40.10.1142/9789812837172_0001
Search in Google Scholar Back to article

Linear Complexity of Sequences on Koblitz Curves of Genus 2

Abstract

Paradigm

My account