If the given protocol is non interactive then how can one prove that the modified protocol is complete and determine whether it is zero-knowledge?

Let $N = p q$ as in an RSA algorithm, with $\text{gcd}(e, \phi(N)) = 1, e$ prime. $P$ wants to prove knowledge of $x \in \mathbb{Z}_N$, where $y = x^e$ is public. $P$ chooses $r \in \mathbb{Z}_N$, and calculates $a = r^e \bmod N$, and sends them to the verifier $V$. $V$ sends $0 \leq c \leq e - 1$ to $P$, and $P$ calculates and sends back $f = rx^c \bmod N$. $V$ accepts this proof if $f^e = ay^c = r^ex^{ec} = (rx^c)^e$.

  • $\begingroup$ I'm confused by your statement "if the given protocol is non interactive". It's clearly not. $\endgroup$
    – Maeher
    Commented Jun 18, 2020 at 8:18
  • 1
    $\begingroup$ "calculates $a = r^e \bmod N$, and sends them to the verifier"; actually, the prover sends back only $a$ (otherwise it's not a zero-knowledge proof, as someone could deduce $x$ if they selected $c=1$) $\endgroup$
    – poncho
    Commented Jun 18, 2020 at 14:30

1 Answer 1


Let's analyze the correctness, zero-knowledge and soundness properties of this protocol proving the pre-image of a group-homomorphism $(\psi(w):w\rightarrow w^e\bmod{N})$ over a group of unknown order ($\mathbb{Z}^{*}_{N}$)!

  • Correctness

The correctness of the above protocol is straightforward to see. If the claimed relation, $y=x^e\bmod{N}$, holds then the verifier always accepts the proof. This is because $f^e=(rx^c)^e=r^ex^{ce}=ay^c$. The first equality follows from the definition of $f$ and the last equality follows from the definition of $a$ and $y$.

  • Zero-knowledge

It is also quite easy to build a simulator for this protocol. The verifier can simulate the protocol transcript on its own, without interacting with a prover as follows. It chooses a random $f'\in_R\mathbb{Z}^{*}_{N}$ and $c'\in_R[0,e-1]$, then $a'=f'^{e}y'^{-c}$. Put differently, the simulated transcript $(a',c',f')$ is computationally indistinguishable from a "real" transcript $(a,c,f)$, i.e., $(a,c,f)\approx_c(a',c',f')$. They are just random integers in $\mathbb{Z}^{*}_{N}$ that also satisfy the verification equation, $f^e=ay^c$.

  • Soundness

Even though this was not part of the question, but still this is the most interesting part of the analysis of any sigma protocol over groups of unknown order. The knowledge error (the probability that a malicious prover can convince the verifier that $y=x^e\bmod{N}$ without actually knowing $x$) of this sigma protocol is at least $1/d$, where $d$ is the smallest divisor of $e$. Practically speaking, this means that any application relying on this protocol needs to run this protocol multiple times in order to achieve reasonable levels of soundness of the zero-knowledge protocol. For more details on this inherent efficiency, see this work by Bangerter et al.


Your Answer

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

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