International Association for Cryptologic Research

International Association
for Cryptologic Research


Robert P. Gallant


Finding discrete logarithms with a set orbit distinguisher
Robert P. Gallant
We consider finding discrete logarithms in a group $\GG$ when the help of an algorithm $D$ that distinguishes certain subsets of $\GG$ from each other is available. For a group $\GG$ of prime order $p$, if algorithm $D$ is polynomial-time with complexity c(\log(p))$, we can find discrete logarithms faster than square-root algorithms. We consider two variations on this idea and give algorithms solving the discrete logarithm problem in $\GG$ with complexity ${\cal O}(p^{\frac{1}{3}}\log(p)^3 + p^{\frac{1}{3}}c(\log(p) )$ and ${\cal O}(p^{\frac{1}{4}}\log(p)^3 + p^{\frac{1}{4}}c( \log(p) )$ in the best cases. When multiple distinguishers are available logarithms can be found in polynomial time. We discuss natural classes of algorithms $D$ that distinguish the required subsets, and prove that for {\em some} of these classes no algorithm for distinguishing can be efficient. The subsets distinguished are also relevant in the study of error correcting codes, and we give an application of our work to bounds for error-correcting codes.
The Static Diffie-Hellman Problem
Daniel R. L. Brown Robert P. Gallant
The static Diffie-Hellman problem (SDHP) is the special case of the classic Diffie-Hellman problem where one of the public keys is fixed. We establish that the SDHP is almost as hard as the associated discrete logarithm problem. We do this by giving a reduction that shows that if the SDHP can be solved then the associated private key can be found. The reduction also establishes that certain systems have less security than anticipated. The systems affected are based on static Diffie-Hellman key agreement and do not use a key derivation function. This includes some cryptographic protocols: basic ElGamal encryption; Chaum and van Antwerpen's undeniable signature scheme; and Ford and Kaliski's key retrieval scheme, which is currently being standardized in IEEE P1363.2.