Hard Bits of the Discrete Log with Applications to Password Authentication

Assuming the intractability of solving the discrete logarithm with short exponent problem, it was recently shown that the trailing $n-omega(log n)$ bits of the discrete logarithm modulo an $n$- bit prime $p$ are simultaneously hard. However, the question of hardness of the leading bits was left open. In this paper we show that the leading $n-omega(log n)$ bits are also simultaneously hard, or equivalently that the distribution of $g^s bmod p$, where $s$ is a uniformly chosen short exponent of $omega(log n)$ bits, is indistinguishable from the uniform distribution on $zstarp$. We further show that this result implies the security of a short exponent version of PAK, a password-authenticated key exchange protocol that protects against offline dictionary attacks.