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 .