I'm trying to come up with a Zero-Knowledge proof for the following setup.

Using RSA encryption, Peggy chooses a random $M \in \mathbb{Z}^*_n$, computes $C=M^e \mod n$ and sends $C$ to Victor. Peggy wants to prove that she knows $M$.

I've constructed the following protocol, but am unable to justify soundness - which makes me wonder whether this is at all correct:

  • Victor selects a random $\hat{M} \in \mathbb{Z}^*_n$ and sends $D := C\hat{M}^e \mod n$ to Peggy.

  • Peggy computes $(M^{-1} \mod n)^eD=\hat{M}^e \mod n$.

  • Victor verifies that the response indeed matches $\hat{M}^e \mod n$.

Completeness is clear, but for soundness - I cannot seem to formally prove that Peggy cannot cheat somehow, but I also cannot identify what might be wrong with this protocol.

Any help would be much appreciated.

  • 1
    $\begingroup$ On identifying what might be wrong with this protocol: Assume you are an attacker and convince Peggy to run the protocol once with you. Can you learn something that then lets you run the protocol indistinguishably from Peggy, without Peggy? $\endgroup$
    – fgrieu
    Sep 11, 2022 at 14:45
  • $\begingroup$ @fgrieu I think I can see it now - Victor can send $D=1 \mod n $ and learn $(M^{-1} \mod n)^e$ which he could not have learned without her. Did I get it right? Thanks! $\endgroup$
    – Anon
    Sep 11, 2022 at 14:52
  • 1
    $\begingroup$ Yes, "Victor can send $D=1 \mod n $ and learn $(M^{-1} \mod n)^e$ which he could not have learned without her". But you did not quite prove what follows "which". For the later, you may want to invoke that the RSA problem is assumed hard; and then some. $\endgroup$
    – fgrieu
    Sep 11, 2022 at 15:11
  • 1
    $\begingroup$ The standard way of constructing such interactive ZKP is have the randomness to be mixed in on the prover side, and the verifier selecting between two options to be revealed. so that the resulting transcript could have been created without the prover. $\endgroup$
    – Meir Maor
    Sep 12, 2022 at 4:21


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.