Abstract
Nagao proposed a decomposition method for divisors of hyperelliptic curves defined over a field \({\mathbb {F}}_{q^n}\) with \(n\ge 2\). Joux and Vitse later proposed a variant which provided relations among the factor basis elements. Both Nagao’s and the Joux–Vitse methods require solving a multi-variate system of polynomial equations. In this work, we revisit Nagao’s approach with the idea of avoiding the requirement of solving a multi-variate system. While this cannot be done in general, we are able to identify special cases for which this is indeed possible. Our main result is for curves \(C:y^2=f(x)\) of genus g defined over \({\mathbb {F}}_{q^2}\) having characteristic >2. If there is no restriction on f(x), we show that it is possible to obtain a relation in \((4g+4)!\) trials. The number of trials, though high, quantifies the computation effort needed to obtain a relation. This is in contrast to the methods of Nagao and Joux–Vitse which are based on solving systems of polynomial equations, for which the computation effort is hard to precisely quantify. The new method combines well with a sieving technique proposed by Joux and Vitse. If f(x) has a special form, then the number of trials can be significantly lower. For example, if f(x) has at most g consecutive coefficients which are in \({\mathbb {F}}_{q^2}\) while the rest are in \({\mathbb {F}}_q\), then we show that it is possible to obtain a single relation in about \((2g+3)!\) trials. Our implementation of the resulting algorithm provides examples of factor basis relations for \(g=5\) and \(g=6\). To the best of our knowledge, none of the previous methods known in the literature can provide such relations faster than our method. Other than obtaining such decompositions, we also explore the applicability of our approach for \(n>2\) and for binary characteristic fields.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Notes
This explanation was provided by an anonymous reviewer.
References
Adleman, L.M., DeMarrais, J., Huang, M.-D.A.: A subexponential algorithm for discrete logarithms over the rationalsubgroup of the jacobians of large genus hyperelliptic curves over finite fields.In: Algorithmic Number Theory, First International Symposium, ANTS-I, Ithaca, NY, USA, May 6-9, 1994, Proceedings, pp. 28–40. Springer-Verlag Berlin Heidelberg New York (1994)
Bosma, W., Cannon, J., Playoust, C.: The Magma algebra system. I. The user language. J. Symbolic Comput. 24(3—-4), 235–265 (1997). Computational algebra and number theory (London, 1993)
Diem, C.: On the discrete logarithm problem in elliptic curves. Compos. Math. 147(1), 75–104 (2011)
Diffie, W., Hellman, M.E.: New directions in cryptography. IEEE Trans. Inf. Theory 22(6), 644–654 (1976)
Enge, A.: Computing discrete logarithms in high-genus hyperelliptic Jacobians in provably subexponential time. Math. Comput. 71(238), 729–742 (2002)
Enge, A., Gaudry, P.: A general framework for subexponential discrete logarithm algorithms. Acta Arith. 102, 83–103 (2002)
Faugère, J.-C., Gianni, P.M., Lazard, D., Mora, T.: Efficient computation of zero-dimensional gröbner bases by change of ordering. J. Symb. Comput. 16(4), 329–344 (1993)
Flassenberg, R., Paulus, S.: Sieving in function fields. Exp. Math. 8(4), 339–349 (1999)
Galbraith, S.D., Smart, N.P.: Evaluation report for CRYPTREC: security level of cryptography—ECDLP mathematical problem. http://www.ipa.go.jp/security/enc/CRYPTREC/fy15/doc/1029_report.pdf (2001)
Gaudry, P.: An algorithm for solving the discrete log problem on hyperelliptic curves. In: Preneel, B. (ed.), Advances in Cryptology - EUROCRYPT 2000, International Conference on the Theory and Application of Cryptographic Techniques, Bruges, Belgium, May 14-18, 2000, Proceeding, vol. 1807 of Lecture Notes in Computer Science, pp. 19–34. Springer (2000)
Gaudry, P.: Index calculus for abelian varieties of small dimension and the elliptic curve discrete logarithm problem. J. Symb. Comput. 44(12), 1690–1702 (2009)
Gaudry, P., Thomé, E., Thériault, N., Diem, C.: A double large prime variation for small genus hyperelliptic index calculus. Math. Comput. 76(257), 475–492 (2007)
Joux, A., Vitse, V.: Cover and decomposition index calculus on elliptic curves made practical - application to a previously unreachable curve over \(\mathbb{F} _{p^6}\). In: Pointcheval, D., Johansson, T., (eds.), Advances in Cryptology - EUROCRYPT 2012 - 31st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cambridge, UK, April 15–19, 2012. Proceedings, vol. 7237 of Lecture Notes in Computer Science, pp. 9–26. Springer (2012)
Koblitz, N.: Elliptic curve cryptosystems. Math. Comp. 48(177), 203–209 (1987)
Koblitz, N.: Hyperelliptic cryptosystems. J. Cryptology 1(3), 139–150 (1989)
Lidl, R., Niederreiter, H.: Introduction to Finite Fields and Their Applications, revised edn. Cambridge University Press, Cambridge (1994)
Menezes, A., Wu, Y.-H., Zuccherato, R.: An elementary introduction to hyperelliptic curves. In: Koblitz, N. (ed.) Appendix to Algebraic Aspects of Cryptography, pp. 155–178. Springer (1998)
Miller, V.S.: Use of elliptic curves in cryptography. In: Williams, H.C. (ed.) Advances in Cryptology - CRYPTO’85. Santa Barbara, California, USA, August 18–22, 1985, Proceedings, volume 218 of Lecture Notes in Computer Science, pp. 417–426. Springer, Berlin Heidelberg (1985)
Nagao, K: Decomposition attack for the Jacobian of a hyperelliptic curve over an extension field. In: Algorithmic number theory, vol. 6197 of Lecture Notes in Computer Science, pp. 285–300. Springer, Berlin (2010)
Sarkar, P., Singh, S.: A new method for decomposition in the jacobian of small genus hyperelliptic curves. Designs, Codes and Cryptography, pp. 1–16, (2016). http://dx.doi.org/10.1007/s10623-016-0184-9
Semaev, I.: Summation polynomials and the discrete logarithm problem on elliptic curves. Cryptology ePrint Archive, Report 2004/031. http://eprint.iacr.org/ (2004)
Thériault, N.: Index calculus attack for hyperelliptic curves of small genus. In: Laih, C.-S., (ed.), Advances in Cryptology - ASIACRYPT 2003, 9th International Conference on the Theory and Application of Cryptology and Information Security, Taipei, Taiwan, November 30 - December 4, 2003, Proceedings, vol. 2894 of Lecture Notes in Computer Science, pp. 75–92. Springer (2003)
Velichka, M.D., Jacobson Jr., M.J., Stein, A.: Computing discrete logarithms in the Jacobian of high-genus hyperelliptic curves over even characteristic finite fields. Math. Comput. 83(286), 935–963 (2014)
Yui, N.: On the jacobian varieties of hyperelliptic curves over fields of characteristic \(p>2\). J. Algebra 52(2), 378–410 (1978)
Acknowledgments
We thank the reviewers of a previous version of the paper for providing comments which helped in improving the work. In particular, we thank an anonymous reviewer for suggesting the summary of the paper given in the conclusion and for providing the explanation of why Magma is unable to solve a system of 12 equations in 10 variables.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Sarkar, P., Singh, S. A simple method for obtaining relations among factor basis elements for special hyperelliptic curves. AAECC 28, 109–130 (2017). https://doi.org/10.1007/s00200-016-0299-2
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00200-016-0299-2