Welcome to the resource topic for
**2023/160**

**Title:**

Practical Improvement to Gaudry-Schost Algorithm on Subgroups of \mathbb{Z}^{*}_{p}

**Authors:**
Madhurima Mukhopadhyay

**Abstract:**

The discrete logarithm problem forms the basis of security of many practical schemes. When the

number of bases is more than one, the problem of finding out the exponents is known as the multi-

dimensional discrete logarithm problem. It arises in several circumstances both in groups modulo

some integer or elliptic curve groups. Gaudry and Schost proposed a low-memory algorithm for this

problem which performs a pseudo-random walk in the group. Tag tracing is a technique to practi-

cally speed-up a pseudo-random walk. We have incorporated this technique into the Gaudry-Schost

algorithm to observe the results of practical differences in time. We implemented the new algorithm

in subgroups of \mathbb{Z}^{*}_{p}. Such subgroups are cryptographically relevant in the context of electronic voting

and cash schemes. Our algorithm showed a substantial decrease in run-time with a gain in time by

some integral multiple. For example, on a single core of Intel Xeon E7-8890 @ 2.50 GHz we showed

our algorithm required 12 times less time than the Gaudry-Schost algorithm. This leads to better

practical behaviour of the algorithm over such groups. We also point out a few more optimizations

that can be adopted along with future applications for other scenarios.

**ePrint:**
https://eprint.iacr.org/2023/160

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

**Example resources include:**
implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .