Zero-knowledge proof of knowledge of RSA decryption exponent

Question

I'm looking for a zero-knowledge proof of knowledge of RSA decryption exponent.

More precisely, let as usual $p,q$ be prime numbers, $n = pq$, and $e,d \in (\mathbb{Z}/\varphi(n)\mathbb{Z})^*$ be the encryption and decryption exponent of RSA, that is, $de \equiv 1 \pmod{\varphi(n)}$, where $\varphi$ is the Euler function. Assume that $n$ and $e$ are public, while $p,q,d$ are secret.

Suppose that a prover wants to convince a verifier that the prover knows $d$, without revealing any information on $d$, that is, in a zero-knowledge way.

One obvious idea would be that the verifier sends $y = x^e$, for random $x \in (\mathbb{Z}/n\mathbb{Z})^*$, to the prover and the prover computes $x = y^d$ and send it back to the verifier, which checks if the received value is indeed equal to $x$.

Under the RSA assumption, the prover should not be able to pass this test with nonnegligible probability unless he knows $d$. However, this says nothing about zero-knowledge and I suspect it is fact not zero-knowledge (there is no commitment) or not currently proved to be so.

Is there some proved zero-knowledge proof of knowledge for $d$?

Answer 1

Your proposed protocol is, in fact, not zero-knowledge. For example, it can be used by an attacker as an RSA decryption oracle.

Now, with public $e$, the knowledge of $d$ and the knowledge of the factorization of $n$ are equivalent.

So, one obvious way is to create a zero-knowledge proof of the factorization, and call it a day. Since there are known zero-knowledge proofs of factorization, that answers your question.

On the other hand, if you want something more similar to the RSA problem (rather than just being mathematically equivalent to it), we can use the standard cut-and-choose protocol (note: updated):

• The verifier proposes an $x$

• The prover selects $y \ne 0$ and responds with $x^{dy}$ and $x^{y}$

• The verifier verifies that $(x^{dy})^e = x^y$ and then asks either for $dy$ or $y$

• The prover generates the requested output (that is, either $dy$ or $y$).

• The verifier validates that output, by raising $x$ to that power.

It is easy to see that:

• A prover with knowledge of $d$ can generate all requested output

• The verifier can validate the requested output

• The verifier cannot learn anything about either $d$ or $x^d$ from the output

• Assuming that the verifier's choice of output is unpredictable and equiprobable, someone without knowledge of $d$ will fail to be able to generate the response with probability 1/2.

• Someone else (without knowledge of $d$) can easily generate a valid-looking transcript of the output.

• With both outputs, we could recover the value $d$. Actually, that's rather more subtle than it would appear at first, because the multiplication in $dy$ is modulo a secret (that is, $\bmod \text{lcm}( p-1, q-1)$, which we cannot assume access to). However, what they could do is compute the value $e(dy) - y = y(de-1)$ (which holds even if the modulus is unknown), and knowledge of that value yields an efficient factorization (and thus efficient recovery of $d$).