Discrete-Log With Compressible Exponents

Many key distribution systems are based on the assumption that the Discrete-Log (DL) problem is hard. The implementations could be more efficient if a significantly smaller exponent could be used, without lowering the complexity of the DL problem. When the exponent is known to reside in interval of size w, the DL problem can be computed in time O$$ \sqrt w $$, using Pollard’ “Lambda method for catching Kangaroos”.Suppose we want a level of security of 300 years on a 1 MIP machine, with 1K bit operations per instruction. Then w = 2127 currently seems sufficient (with 512 bit modulus). It is not clear, however, whether methods other than “Kangaroo” exist, with lower complexity.Let s and m denote the number of squarings and multiplications, respectively, required to exponentiate. It is well known that s roughly equals the size in bits of the exponent (L), and m is roughly 1.5 · L/lg₂(L), for the most efficient methods, in the practical range.We show that by using an exponent which is known to be compressible by a factor η, using the Ziv-Lempel method, we reduce m exponentially in η, on the average (integer multiplications may be more than twice as expensive as squarings, hence this is not negligible).This can be used to speed up cryptographic key distribution systems of the Diffie-Hellman family. However, it is not clear how safe compressible exponents are.