Paper 2023/160

Improving Gaudry-Schost algorithm for multi-dimensional discrete logarithm calculations: Implementations relevant to electronic voting and cash schemes

Abstract

We focus on improving the Gaudry-Schost algorithm, which solves multi-dimensional discrete logarithm problem. We have proposed a modified algorithm that reduces the cost of each iteration of Gaudry-Schost algorithm by a factor of $\frac{\frac{D-1}{\Delta}+\frac{1}{l}+\frac{C_{\overline{s}_{D}}}{C_f}}{\frac{D-1}{\Delta}+1}$ where $D$ is the dimension of the problem, $l$ a specially designed quantity, $C_g$ is the cost of computing any function $g$, $\overline{s}_D,f$ are functions and $(\frac{1}{l}+\frac{C_{\overline{s}_{D}}}{C_f})<1$. The cost of our algorithm for subgroups modulo prime $p$, which arises in electronic voting and cash schemes diminishes by a factor of $\frac{\frac{||p||}{\Delta_{gs}}}{l\frac{\log(||p||)}{\Delta_{tt}}}$ where $\Delta$'s are the iterations to reach a certain type of points. Our implementation of the algorithm confirms theoretical analysis. The reduction of cost per iteration sums to be much advantegeous when complete number of iterations have to be done to find the logarithms. Also, both theory and experiments confirm that the new algorithm reduces the dominant multiplication cost along with other additional costs, and the gain would be more as we increase the size of the group. We obtained about $12$ times speed-up for groups of size $2076$ bits. Our algorithm will lead to a reduction of security of schemes based on multi-dimensional discrete logarithm problem or using multi-dimensional pseudo-random walk like electronic voting, cash schemes point-counting, speeding-up elliptic-curve arithmetic, group-actions, CSIDH etc.