Jordi Pujol`as Boix (2009) On the Decisional Diffie-Hellman Problem in Genus 2.
Full text access: Open
We investigate the Decisional Diffie-Hellman problem in the Jacobian variety of supersingular curves of genus two over finite fields. A solution to this problem is useful in Public Key Cryptography, for example in Digital Signatures and Identity-Based Cryptography. The existence of a non-degenerate, bilinear pairing reduces the solution to DDH to the existence of sufficiently many distortion maps. These maps are found in the endomorphism ring of the Jacobian variety. We show examples of supersingular curves over finite fields of both even and odd characteristics such that the endomorphism algebra is 16-dimensional over the rationals, and we solve DDH in some cases.
This is a Published version This version's date is: 04/03/2009 This item is peer reviewed
https://repository.royalholloway.ac.uk/items/d954e210-2653-08bb-4ccd-547f472af91c/1/
Deposited by () on 24-Jun-2010 in Royal Holloway Research Online.Last modified on 15-Dec-2010
[Alb39] A. Albert, “Structure of Algebras”, American Mathematical SocietyColloquium Publications, vol. 24, American MathematicalSociety, New York (1939).
[AB04] M. Alsina and P. Bayer, “Quaternion orders, quadratic forms,and Shimura curves”, CRM monograph series, vol. 22, AmericanMathematical Society, Providence R.I. (2004).
[BGOS04] P. Barreto, S. Galbraith, C. O’hEigeartaigh and M. Scott, “EfficientPairing Computation on Supersingular Abelian Varieties”,eprint 2004/375.
[BL04] C. Birkenhake and H. Lange, “Complex Abelian Varieties”,Grundlehren der mathematischen Wissenschaften, vol. 302 (secondedition), Springer-Verlag, Berlin-Heidelberg (2004).
[BSS04] I. Blake, G. Seroussi and N. Smart (eds.), “Advances in EllipticCurve Cryptography”, London Mathematical Society Lecture NoteSeries, vol. 317, Cambridge University Press, Cambridge (2004).
[Bon98] D. Boneh, “The decision Diffie-Hellman problem”, in the Proceedingsof the Third Algorithmic Number Theory Symposium,Lecture Notes in Computer Science, vol. 1423, Springer (1998),48–63.
[BF01] D. Boneh and M. Franklin, “Identity-based encryption from theWeil pairing”, SIAM Journal of Computing, 48 Number 3 (2003),586–615. Extended Abstract in Crypto 2001.
[BLS01] D. Boneh, B. Lynn and H. Shacham, “Short Signatures from theWeil Pairing”, J. Cryptology, 17 Number 4 (2004), 297–319. Firstappeared in Proceedings Asiacrypt 2001.
[Can87] D. Cantor, “Computing in the Jacobian of a hyperelliptic curve”,Mathematics of computation, 48 (1987), 95–101.
[CNP05] G. Cardona, E. Nart and J. Pujol`as, “Curves of genus two overfields of even characteristic”, Mathematische Zeitschrift, 250Number 1 (2005), 177–201.
[CF96] J. W. S. Cassels and E. V. Flynn, “Prolegomena to a middlebrowarithmetic of curves of genus 2”, London Mathematical SocietyLecture Note Series, vol. 230, Cambridge University Press, Cambridge(1996).
[CJL00] Y.-J. Choie, E. Jeong and E. Lee, “Supersingular hyperellipticcurves of genus 2 over finite fields”, preprint (2000)
[CL04] Y.-J. Choie and E. Lee, “Implementation of tate pairing on hyperellipticcurves of genus 2 ”, in J. I. Lim and D. H. Lee (eds.), ICISC2003, Lecture Notes in Computer Science, vol. 2971, Springer(2004), 97–111.
[CS86] G. Cornell and J. Silverman (eds.), “Arithmetic Geometry”,Springer (1986).
[Deu41] M. Deuring, “Die Typen der Multiplicatorenringe elliptischerFunktionenk¨orper”, Abhandlungen aus dem MathematischenSeminar der Univ. Hamburg, 14 (1941), 197–272.
[DL03] I. Duursma and H.-S. Lee, “Tate-pairing implementations for tripartitekey agreement”, Advances in cryptology—ASIACRYPT2003, Lecture Notes in Computer Science, vol. 2894, Springer(2003), 111–123.
[FOS04] Notes taken by J. Pujol`as during Prof. G. Frey’s lectures atthe Oberwolfach Seminar “Arithmetic Geometry and Public KeyCryptography” (2004).
[FL03] G. Frey and T. Lange, “Mathematical Background of Public KeyCryptography”, “S´eminaires et congr`es”, 11 (2003), 41–73.
[FR94] G. Frey and H.-G. R¨uck, “A remark concerning m-divisibilityand the discrete logarithm problem in the divisor class group ofcurves”, Math. Comp. , 52 (1994), 865–874.
[Gag03] M. Gagn´e, “Identity-Based Encryption: a Survey”, CryptoBytes,6 Number 1, RSA Laboratories (2003), 10–19.
[Gal01] S. Galbraith, “Supersingular Curves in Cryptography”, in Advancesin Cryptology- ASIACRYPT 2001, Lecture Notes in ComputerScience, vol. 2248, Springer (2001), 495–513.
[Gal05] S. Galbraith, “Pairings”, in [BSS04].
[GR04] S. Galbraith and V. Rotger, “Easy decision Diffie-Hellmangroups”, LMS J. Comput. Math. , 7 (2004), 201–218.
[GHKRW05] P. Gaudry, T. Houtmann, D. Kohel, C. Ritzenthaler and A.Weng, “The p-adic CM-method for genus 2”, available online athttp://www.arxiv.org/math.NT/0503148 (2005).
[GM06] G. van der Geer and B. Moonen, preliminary versions of“Abelian Varieties”, book in preparation, available on-line athttp://staff.science.uva.nl/~bmoonen/boek/BookAV.html.
[GV92a] G. van der Geer and M. van der Vlugt, “Supersingular Curves ofGenus 2 over finite fields of Characteristic 2 ” , Math. Nachr., 159(1992), 73–81.
[GV92b] G. van der Geer and M. van der Vlugt, “Reed-Muller codes andsupersingular curves. I ” , Compositio Math., 84 (1992), 333–367.
[GKR05] M. Girard, D. Kohel and C. Ritzenthaler, “The Weierstrasssubgroup of a curve has maximal rank”, available online athttp://www.arxiv.org/math.NT/0504130v1 (2005).
[Gor97] E. Z. Goren, “On certain reduction problems concerning abeliansurfaces” Manuscripta Mathematica, 94 (1997) 33–43.
[Har77] R. Hartshorne, “Algebraic Geometry”, Graduate Texts in Mathematics,vol. 52, Springer-Verlag, New York (1977).
[Has34] H. Hasse, “Theorie der relativ-zyklischen algebraischen Funktionk¨orper, insbesondere bei endlichem Konstantk¨orper”, J. ReineAngew. Math., 172 (1934), 37–54.
[Her68] I. Herstein, “Noncommutative Rings”, The Carus MathematicalMonographs, vol. 15, The Mathematical Association of America(Distributed by John Wiley and Sons, Inc.) (1968).
[Hes04] F. Hess, “A Note on the Tate pairing of Curves over FiniteFields”, Arch. Math., 82 (2004), 28–32 .
[Hur03] N. Hurt, “Many Rational Points: Coding Theory and AlgebraicGeometry”, Kluwer Academic Pub (2003).
[Igu60] J. Igusa, “Arithmetic variety of moduli for genus two”, Ann. ofMath., 72 (1960), 612–649.
[JMS04] M. Jacobson, A. Menezes and A. Stein, “Hyperelliptic curve cryptosystems”,in “High Primes and Misdemeanours: Lectures in Honourof the 60th Birthday of Hugh Cowie Williams”, Fields InstituteCommunications Series, 41 (2004), 255–282.
[JSW05] M. Jacobson, R. Scheidler and H.C. Williams,“An Improved Real Quadratic Field BasedKey Exchange Procedure”, available online athttp://www.math.ucalgary.ca/ rscheidl/publications.html(2005).
[Jou00] A. Joux, “A one round protocol for tripartite Diffie-Hellman ”, inthe Proceedings of the Fourth Algorithmic Number Theory Symposium, Lecture Notes in Computer Science, vol. 1838, Springer(2000), 385–394.
[JN03] A. Joux and K. Nguyen, “Separating decision Diffie-Hellman fromcomputational Diffie-Hellman in cryptographic groups”, J. Cryptology,16 Number 4 (2003), 39–47.
[Kob98] N. Koblitz, “Algebraic Aspects of Cryptography”, Algorithms andcomputation in mathematics, 3, Springer, Berlin-London (1998).
[Lan83] S. Lang, “Complex Multiplication”, Die Grundlehren der matematischenWissenchaften in Einzeldarstellungen, vol. 255, Springer-Verlag, Berlin- Heidelberg (1983).
[LO98] K.-Z. Li and F. Oort, “Moduli of supersingular abelian varieties”,Lecture Notes in Mathematics, vol. 1680, Springer (1998).
[Lor96] D. Lorenzini, “An Invitation to Arithmetic Geometry”, GraduateStudies in Mathematics, vol. 9, American Mathematical Society(1996).
[LST64] J. Lubin, J.-P. Serre and J. Tate, “Ellipticcurves and formal groups”, available online athttp://www.ma.utexas.edu/users/voloch/lst.html (1964).
[MN04] D. Maisner and E. Nart, “Zeta functions of supersingularcurves of genus two”, available online athttp://www.arxiv.org/math.NT/0408383v1 (2004).
[Man63] Y. Manin, “The theory of commutative formal groups over fieldsof finite characteristic”, Usp. Math., 18 (1963), 3–90; Russ. Math.Surveys, 18 (1963), 1–80.
[MWZ98] A. Menezes, Y.-H. Wu and R. Zuccherato, “An Elementary Introductionto Hyperelliptic Curves”, in [Kob98], 155–178.
[Mil04] V. Miller, “The Weil Pairing, and Its Efficient Calculation”, J.Cryptology, 17 (2004), 235–261
[Mil86] J. Milne, “Arithmetic Duality Theorems”, AcademicPress (1986), Second Edition available online athttp://www.jmilne.org/math/ (2004).
[MVZ98] V. M¨uller, S. Vanstone and R. Zuccherato, “Discrete logarithmbased cryptosystems in quadratic function fields of characteristic2”, Des. Codes Cryptogr., 14 Number 2 (1998), 159–178.
[Mum84] D. Mumford, “Tata Lectures on Theta”, vol. 2, Birkh¨auser (1992).
[Neu99] J. Neukirch, “Algebraic Number Theory”, Die Grundlehren dermathematischen Wissenchaften, vol. 322, Springer-Verlag, Berlin-London (1999).
[NSW86] J. Neukirch, A. Schmidt and K. Wingberg, “Cohomology of NumberFields”, Die Grundlehren der mathematischen Wissenchaften,vol. 323, Springer, Berlin-London (1986).
[Oor70] F. Oort, “Subvarieties of moduli spaces”, Inv. Math., 24 (1970),95–119.
[Pat02] K. Paterson, “Cryptography from pairings: a snapshot of currentresearch”, Information Security Technical Report, 7 Number 3(2002), 41–54.
[Pat05] K. Paterson, “Cryptography from pairings”, in [BSS04].
[Pie82] R. S. Pierce, “Associative Algebras”, Graduate Texts in Mathematics,vol. 88, Springer, New York-Heidelberg-Berlin (1982).
[Puj02] J. Pujol`as, “Corbes de g`enere dos sobre cossos de caracter´ısticados”, Tesina, Universitat Aut`onoma de Barcelona (2002).
[Rei75] I. Reiner, “Maximal Orders”, London Mathematical SocietyMonographs, Academic Press (1975).
[RS02] K. Rubin and A. Silverberg, “Supersingular abelian varieties incryptology”, in M. Yung (ed.), CRYPTO 2002, Lecture Notes inComputer Science, vol. 2442, Springer (2002), 336–353.
[Sch05] E. Schaefer, “A new proof for the non-degeneracy of the Frey-R¨uck Pairing and a connection to isogenies over the base field”,available online at http://www.iacr.org.
[Sch00] R. Scheidler, “Decision Problems in Quadratic Function Fields ofHigh Genus”, Journal of Complexity, 16 (2000), 411–423.
[SSW96] R. Scheidler, A. Stein and H. C. Williams, “Key exchange in realquadratic congruence function fields”, Des. Codes Cryptogr., 7(1996), 153–174.
[Ser94] J.-P. Serre, “Cohomologie Galoisienne”, Lecture Notes in Mathematics,Number 5, Springer (1994) (reprint).
[Sil86] J. Silverman, “The arithmetic of elliptic curves”, Graduate Textsin Mathematics, Springer (1986).
[Sti93] H. Stichtenoth, “Algebraic Function Fields and Codes”, Springer-Verlag (1993).
[SX95] H. Stichtenoth and C. Xing, “On the structure of the divisor classgroup over a class of curves over finite fields”, Arch. Math., 65(1995), 141–150.
[Tat66] J. Tate, “Endomorphisms of abelian varieties over finite fields”,Inv. Math., 2 (1966), 134–144.
[Ver04] E. Verheul, “Evidence that XTR is more secure than supersingularelliptic curve cryptosystems”, J. Cryptology, 17 (2004), 277–296.
[Vol95] E. Volcheck, “Computing in the Jacobian of a plane algebraiccurve”, in the Proceedings of the First Algorithmic Number TheorySymposium, Lecture notes in Computer Science, vol. 877,Springer (1998), 221–233.
[Wam99a] P. vanWamelen, “Examples of genus two CM curves defined overthe rationals”, Math. Comp. , 68 Number 225 (1999), 307–320.
[Wam99b] P. van Wamelen, “Proving that a genus 2 curve has ComplexMultiplication”, Math. Comp. , 68 Number 228 (1999), 1663–1677.
[Wat79] W. C. Waterhouse, “Introduction to Affine Group Schemes”,Graduate Texts in Mathematics 2066, Springer (1979).
[Wei67] A. Weil, “Basic Number Theory”. Die Grundlehren der matematischenWissenchaften in Einzeldarstellungen, vol. 144, Springer-Verlag, Berlin- Heidelberg (1967).
[Yui78] N. Yui, “On the jacobian varieties of hyperelliptic curves over fieldsof characteristic p > 2”, J. Alg., 52 (1978), 378–410.
[Zag81] D. Zagier, “Zetafunktionen und quadratische K¨orper. EineEinf¨uhrung in die h¨ohere Zahlentheorie”, Hochschultext, Springer-Verlag, Berlin-New York (1981).
[Zuc97] R. Zuccherato, “The continued fraction algorithm and regulatorfor quadratic function fields of characteristic 2”, J. Algebra, 190Number 2 (1997), 563–587.
[Zuc98] R. Zuccherato, “The Equivalence between Elliptic Curve andQuadratic Function Field Discrete Logarithms in Characteristic2”, Algorithmic number theory (Portland, OR, 1998), 621–638, inLecture Notes in Computer Science, vol. 1423, Springer, Berlin(1998).