Implementation of point-counting algorithms on genus 2 hyperelliptic curves based on the birthday paradox | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2022. № 55. DOI: 10.17223/20710410/55/9

Our main contribution is an efficient implementation of the Gaudry - Schost and Galbraith - Ruprai point-counting algorithms on Jacobians of hyperelliptic curves. Both of them are low memory variants of Matsuo - Chao - Tsujii (MCT) Baby-Step Giant-Step-like algorithm. We present an optimal memory restriction (a time-memory tradeoff) that minimizes the runtime of the algorithms. This tradeoff allows us to get closer in practical computations to theoretical bounds of expected runtime at 2.45√N and 2.38a√N for the Gaudry - Schost and Galbraith - Ruprai algorithms, respectively. Here N is the size of the 2-dimensional searching space, which is as large as the Jacobian group order, divided by small modulus m, precomputed by using other techniques. Our implementation profits from the multithreaded regime and we provide some performance statistics of operation on different size inputs. This is the first open-source parallel implementation of 2-dimensional Galbraith - Ruprai algorithm.
Download file
Counter downloads: 44
  • Title Implementation of point-counting algorithms on genus 2 hyperelliptic curves based on the birthday paradox
  • Headline Implementation of point-counting algorithms on genus 2 hyperelliptic curves based on the birthday paradox
  • Publesher Tomask State UniversityTomsk State University
  • Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 55
  • Date:
  • DOI 10.17223/20710410/55/9
Keywords
hyperelliptic curve, Jacobian, point-counting, birthday paradox
Authors
References
Matsuo K., Chao J., and Tsujii S. An improved baby step giant step algorithm for point counting of hyperelliptic curves over finite fields. LNCS, 2002, vol. 2369, pp. 461-474.
Gaudry P. and Schost E. A low-memory parallel version of Matsuo, Chao and Tsujii’s algorithm. LNCS, 2004, vol. 3076, pp. 208-222.
Galbraith S. and Ruprai R. An improvement to the Gaudry - Schost algorithm for multidimensional discrete logarithm problems. LNCS, 2009, vol. 5921, pp. 368-382.
Cohen H., Frey G., Avanzi R., et al. Handbook of Elliptic and Hyperelliptic Curve Cryptography. CRC Press, 2005.
Gaudry P. and Schost E. Genus 2 point counting over prime fields. J. Symbolic Comput., 2012, vol. 47, iss. 4, pp. 368-400.
Ruprai R. S. Improvements to the Gaudry - Schost Algorithm for Multidimensional Discrete Logarithm Problems and Applications. PhD Thesis, Department of Mathematics, Royal Holloway University of London, 2010. https://www.math.auckland.ac.nz/~sgal018/Ruprai-thesis.pdf.
Nishimura K. and Sibuya M. Probability to meet in the middle. J. Cryptology, 1990, no. 2, pp.13-22.
Hisil H. and Costello C. Jacobian coordinates on genus 2 curves. J. Cryptology, 2017, vol. 30, iss.2, pp. 572-600. https://doi.org/10.1007/s00145-016-9227-7.
Van Oorschot P. C. and Wiener M. J. Parallel collision search with cryptanalytic applications. J. Cryptology, 2013, vol. 12, pp. 1-28.
Gaudry P. C++ NTLJac2 Library, 2003, http://www.lix.polytechnique.fr/Labo/Pierrick.Gaudry/NTLJac2.
 Implementation of point-counting algorithms on genus 2 hyperelliptic curves based on the birthday paradox | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2022. № 55. DOI: 10.17223/20710410/55/9
Implementation of point-counting algorithms on genus 2 hyperelliptic curves based on the birthday paradox | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2022. № 55. DOI: 10.17223/20710410/55/9
Download full-text version
Counter downloads: 157