4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Myria Nov 6 '15 at 22:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.