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

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 the theoretical analysis. The reduction of cost per iteration sums to be much advantageous 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 withother 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.