How to Solve Multiple Short-Exponent Discrete Logarithm Problem

Let \(\mathbb {G}\) be a group of prime order p with a generator g. It is known that one can find \(x_1, \ldots , x_L\) from \(g^{x_1}, \ldots , g^{x_L}\) in time \(O(\sqrt{Lp})\). On the other hand, suppose that \(0 \le x < w\). Then Pollard’s kangaroo algorithm (or Pollard’s lambda algorithm) can find x from \(g^x\) in time \(O(\sqrt{w})\). It is used in the decryption algorithm of the homomorphic encryption scheme of Boneh, Goh and Nissim. Now suppose that \(0 \le x_i < w\) for \(i=1, \ldots , L\). This paper shows that we can find \(x_1, \ldots , x_L\) from \(g^{x_1}, \ldots , g^{x_L}\) in time \(O(\sqrt{Lw})\). We further show an application of our algorithm to the model of preprocessing.