Geodesic
Implementation of point-counting algorithms on genus~$2$ hyperelliptic curves based on the birthday paradox
Prikladnaâ diskretnaâ matematika, no. 1 (2022), pp. 120-128.

Voir la notice de l'article provenant de la source Math-Net.Ru

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\sqrt{N}$ and $2.38\sqrt{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.
Keywords: hyperelliptic curve, point-counting, birthday paradox.
Mots-clés : Jacobian 
@article{PDM_2022_1_a8,
     author = {N. S. Kolesnikov},
     title = {Implementation of point-counting algorithms on genus~$2$ hyperelliptic curves based on the birthday paradox},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {120--128},
     publisher = {mathdoc},
     number = {1},
     year = {2022},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/PDM_2022_1_a8/}
}
TY  - JOUR
AU  - N. S. Kolesnikov
TI  - Implementation of point-counting algorithms on genus~$2$ hyperelliptic curves based on the birthday paradox
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2022
SP  - 120
EP  - 128
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2022_1_a8/
LA  - en
ID  - PDM_2022_1_a8
ER  - 
%0 Journal Article
%A N. S. Kolesnikov
%T Implementation of point-counting algorithms on genus~$2$ hyperelliptic curves based on the birthday paradox
%J Prikladnaâ diskretnaâ matematika
%D 2022
%P 120-128
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2022_1_a8/
%G en
%F PDM_2022_1_a8
N. S. Kolesnikov. Implementation of point-counting algorithms on genus~$2$ hyperelliptic curves based on the birthday paradox. Prikladnaâ diskretnaâ matematika, no. 1 (2022), pp. 120-128. http://geodesic.mathdoc.fr/item/PDM_2022_1_a8/

[1] 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, 461–474 | MR | Zbl

[2] Gaudry P., Schost E., “A low-memory parallel version of Matsuo, Chao and Tsujii's algorithm”, LNCS, 3076, 2004, 208–222 | MR | Zbl

[3] Galbraith S., Ruprai R., “An improvement to the Gaudry — Schost algorithm for multidimensional discrete logarithm problems”, LNCS, 5921, 2009, 368–382 | MR | Zbl

[4] Cohen H., Frey G., Avanzi R., et al., Handbook of Elliptic and Hyperelliptic Curve Cryptography, CRC Press, 2005

[5] Gaudry P., Schost E., “Genus 2 point counting over prime fields”, J. Symbolic Comput., 47:4 (2012), 368–400 | DOI | MR | Zbl

[6] 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/s̃gal018/Ruprai-thesis.pdf | Zbl

[7] Nishimura K., Sibuya M., “Probability to meet in the middle”, J. Cryptology, 1990, no. 2, 13–22 | DOI | MR | Zbl

[8] Hisil H., Costello C., “Jacobian coordinates on genus 2 curves”, J. Cryptology, 30:2 (2017), 572–600 | DOI | MR | Zbl

[9] Van Oorschot P. C., Wiener M. J., “Parallel collision search with cryptanalytic applications”, J. Cryptology, 12 (2013), 1–28 | MR

[10] Gaudry P., C++ NTLJac2 Library, , 2003 http://www.lix.polytechnique.fr/Labo/Pierrick.Gaudry/NTLJac2 | Zbl