Improving the Gaudry-Schost algorithm for multidimensional discrete logarithms
type: Item
instance of: scholarly article
title: Improving the Gaudry-Schost algorithm for multidimensional discrete logarithms
zbMATH Open document ID: 1482.11162
author: Haoxuan Wu
author: Jincheng Zhuang
published in: Designs, Codes and Cryptography
publication date: 2022-01-19T00:00:00Z
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.
Mathematics Subject Classification ID: 11T71
Mathematics Subject Classification ID: 94A60
Mathematics Subject Classification ID: 11Y16
zbMATH DE Number: 7459696
zbMATH Keywords: discrete logarithm problem
zbMATH Keywords: multidimensional discrete logarithm problem
zbMATH Keywords: tame and wild kangaroos
zbMATH Keywords: Gaudry-Schost algorithm
reviewed by: Juan Tena Ayuso
MaRDI profile type: Publication
full work available at URL: s10623-021-00966-5
OpenAlex ID: W3210434013
cites work: Q2949487
cites work: Q4249317
cites work: New directions in cryptography
cites work: A public key cryptosystem and a signature scheme based on discrete logarithms
cites work: An Improvement to the Gaudry-Schost Algorithm for Multidimensional Discrete Logarithm Problems
cites work: Using Equivalence Classes to Accelerate Solving the Discrete Logarithm Problem in a Short Interval
cites work: Mathematics of public key cryptography.
cites work: A non-uniform birthday problem with applications to discrete logarithms
cites work: Computing discrete logarithms in an interval
cites work: Q4783726
cites work: Algorithmic Number Theory
cites work: Q2739453
cites work: Q4737507
cites work: О сложности двупараметрической задачи дискретного логарифмирования в конечной циклической группе с эффективным автоморфизмом
cites work: Modified Gaudry-Schost algorithm for the two-dimensional discrete logarithm problem
cites work: Monte Carlo Methods for Index Computation (mod p)
cites work: Q3210171
cites work: On waiting time in the scheme of random allocation of coloured particies
cites work: Q5628224
cites work: Parallel collision search with cryptanalytic applications
cites work: A variant of the Galbraith-Ruprai algorithm for discrete logarithms with improved complexity
DOI: 10.1007/S10623-021-00966-5
Recommended article: An Improvement to the Gaudry-Schost Algorithm for Multidimensional Discrete Logarithm Problems
Recommended article: Computing discrete logarithms with the parallelized kangaroo method.
Recommended article: Computing discrete logarithms in an interval
Recommended article: Accelerating Pollard's rho algorithm on finite fields
Recommended article: Square-root algorithms for the discrete logarithm problem (a survey)
Recommended article: A variant of the Galbraith-Ruprai algorithm for discrete logarithms with improved complexity
Recommended article: A general framework for subexponential discrete logarithm algorithms
Recommended article: Q3615927
Recommended article: On the complexity of two-dimensional discrete logarithm problem in a finite cyclic group with effective automorphism of order
Recommended article: Q4950035
description: scientific article; zbMATH DE number 7459696