## CryptoDB

### Robert P. Gallant

#### Publications

**Year**

**Venue**

**Title**

2010

EPRINT

Finding discrete logarithms with a set orbit distinguisher
Abstract

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.

2004

EPRINT

The Static Diffie-Hellman Problem
Abstract

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.

#### Coauthors

- Daniel R. L. Brown (1)
- Robert J. Lambert (1)
- Scott A. Vanstone (1)