Improving the Gaudry-Schost algorithm for multidimensional discrete logarithms

DOI10.1007/S10623-021-00966-5MaRDI QIDQ2068384zbMATH OpenOpenAlexFDO

Authors Haoxuan Wu, Jincheng Zhuang

Publication date 19 January 2022

Published in Designs, Codes and Cryptography (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10623-021-00966-5

zbMATH Keywords

discrete logarithm problemGaudry-Schost algorithmmultidimensional discrete logarithm problemtame and wild kangaroos

Mathematics Subject Classification ID

Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Number-theoretic algorithms; complexity (11Y16) Cryptography (94A60)

Review text

This paper proposes two variants of the Gaudry-Schost algorithm to attack the multidimensional discrete logarithm problem, variants improving the time cost.\par Giving a suitable finite abelian group \(G\)\, (for example the group of points of an elliptic curve defined over a finite group) the d-dimensional DLP asks, given \(g_1,\dots, g_d\in G\)\, elements of orders \(N_1,\dots, N_d\)\, and \(h=g_1^{a_1}\dots g_d^{a_d}\),\, with \(a_i\in [0,N_i]\),\, how to find the exponents \(a_i\).\par For \(d=1\)\, this is the classical DLP, widely used in Public-key Cryptography. One way to solve this problem it is the called tame and wild kangaroo method of \textit{J. M. Pollard} [Math. Comput. 32, 918--924 (1978; Zbl 0382.10001)]. For the multidimensional case \textit{P. Gaudry} and \textit{É. Schost} [Lect. Notes Comput. Sci. 3076, 208--222 (2004; Zbl 1125.11360)] gave a similar low-memory algorithm based on tame and wild walks.\par Several improvements to the Gaudry-Schost have been proposed in the literature. \textit{S. D. Galbraith} and \textit{R. S. Ruprai} [Lect. Notes Comput. Sci. 6056, 368--383 (2010; Zbl 1270.11124)] gave an algorithm.with an specific overlap of tame and wild regions.\par The first variant of the present paper follows the paths of the Galbraith-Ruprai algorithm. This variant is discusses in Section 3 and the comparison of the expected time complexity for this variant and the Gaudry-Schost and Galbraith-Ruprai algorithms is provided in Table 1.\par Section 4 deals with the second proposed variant which fixes the tame region and it adjusts the size of the wild one. Table 2 shows the comparison of the expected tome complexity of this second variant and the complexity of the Gaudry-Schost and Galbraith-Ruprai algorithms.

Recommendations

• An Improvement to the Gaudry-Schost Algorithm for Multidimensional Discrete Logarithm Problems
• Computing discrete logarithms with the parallelized kangaroo method.
• Computing discrete logarithms in an interval
• Accelerating Pollard's rho algorithm on finite fields
• Square-root algorithms for the discrete logarithm problem (a survey)
• A variant of the Galbraith-Ruprai algorithm for discrete logarithms with improved complexity
• A general framework for subexponential discrete logarithm algorithms
• Elementary thoughts on discrete logarithms
• On the complexity of two-dimensional discrete logarithm problem in a finite cyclic group with effective automorphism of order 6
• scientific article; zbMATH DE number 1440049

Cites work

• A non-uniform birthday problem with applications to discrete logarithms
• A public key cryptosystem and a signature scheme based on discrete logarithms
• A variant of the Galbraith-Ruprai algorithm for discrete logarithms with improved complexity
• Algorithmic Number Theory
• An Improvement to the Gaudry-Schost Algorithm for Multidimensional Discrete Logarithm Problems
• Computing discrete logarithms in an interval
• scientific article; zbMATH DE number 1643934 (Why is no real title available?)
• scientific article; zbMATH DE number 6488034 (Why is no real title available?)
• scientific article; zbMATH DE number 4191111 (Why is no real title available?)
• scientific article; zbMATH DE number 1302835 (Why is no real title available?)
• scientific article; zbMATH DE number 2086905 (Why is no real title available?)
• scientific article; zbMATH DE number 1842492 (Why is no real title available?)
• scientific article; zbMATH DE number 3353398 (Why is no real title available?)
• Mathematics of public key cryptography.
• Modified Gaudry-Schost algorithm for the two-dimensional discrete logarithm problem
• Monte Carlo Methods for Index Computation (mod p)
• New directions in cryptography
• On waiting time in the scheme of random allocation of coloured particies
• Parallel collision search with cryptanalytic applications
• Using equivalence classes to accelerate solving the discrete logarithm problem in a short interval
• О сложности двупараметрической задачи дискретного логарифмирования в конечной циклической группе с эффективным автоморфизмом

Cited in

(5)

• A variant of the Galbraith-Ruprai algorithm for discrete logarithms with improved complexity
• Improving the DISPGB algorithm using the discriminant ideal
• Modified Gaudry-Schost algorithm for the two-dimensional discrete logarithm problem
• An Improvement to the Gaudry-Schost Algorithm for Multidimensional Discrete Logarithm Problems
• scientific article; zbMATH DE number 1440049 (Why is no real title available?)

This page was built for publication: Improving the Gaudry-Schost algorithm for multidimensional discrete logarithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2068384)