# How many bits of an exponent are leaked when doing a powmod?

How many bits of the exponent $x$ are leaked when you calculate and reveal $g^x \pmod p$ for some generator $g$ of $\mathbb Z^∗_p$?

The low bit of $x$ is obviously leaked: the low bit equals $1-\frac{\left(\frac{g^x}{p}\right)+1}{2}$, with parentheses representing the Legendre symbol.

The answer depends on the factorization of $p-1$; for any factor $q$ of $p-1$, the attacker can derive $x \bmod q$ in $\sqrt{q}$ steps (by first computing $(g^x)^q = g^{xq}$, and then searching for the value $y$ with $(g^{xq})^y = 1$ using, say, Pollard Rho.
Hence, if the attacker has a computation budget of $n$, and $p-1 = q \cdot r$, where $q$ is $n^2$ smooth, and $r$ has no prime factors $< n^2$, then the attacker can derive $x \bmod q$, which can be analogized to $\log_2 q$ bits. However, if you're interested in the precise bits (and not just bit equivalents), then (unless $p-1$ is $n^2$ smooth, in which case you can derive the entire value of $x$), you're stuck with $m$ bits, where $2^m$ is the largest power of 2 which is a factor for $p-1$.
(Note: I'm ignoring the factor that if $p-1$ might have multiple prime factors near $n^2$, we might take more than $n$ work; not ignoring that makes the analysis more complex, without changing the result substantially)
By this logic, your observation that we can always derive the lower bit of $x$, that is $x \bmod 2$, is equivalent to the observation that $p-1$ is always even.
• I just noticed that the definition of the Legendre symbol, $a^{\frac{p-1}{2}} \pmod p$, is equivalent to the Pöhlig-Hellman algorithm for the group order divisor $2$. Checking whether it's $+1$ or $-1$ is brute-forcing the logarithm of the subgroup. – Myria Nov 6 '15 at 22:13