Assume there is an RSA public key $(e,n)$ such that factarization of $n$ is unknown to both prover and verifier parties. We also have a prime order group $G$ and a generator $g$ for the group. For $m\in QR_n$, is there a zero-knowledge proof protocol to prove that $C_1=m^e$ and $C_2=g^m$, for public values $(C_1, C_2, e, n, g)$?

  • $\begingroup$ What makes me uncomfortable is that $QR_n$ defines values modulo $n$ where as in $g^m$ the value $m$ is defined modulo $\varphi(n)$ (more precisely modulo $|G|$, whatever). And these values are "orthogonal" so it's not well defined. Forcing $QR_n$ to be precisely a subset of $\{0,\ldots,n-1\}$ is hacky/non-algebraic. $\endgroup$
    – Fractalice
    Jun 17, 2021 at 14:51
  • $\begingroup$ Also, why restriction $m\in QR_n$? $\endgroup$
    – Fractalice
    Jun 17, 2021 at 14:52
  • $\begingroup$ Thank you for your feedback. $m\in QR_n$ because it is not a random message but a specific value from the protocol, and both parties know that $m\in QR_n$. My concern was exactly the same with yours. I could not figure out if we can provide such proof under the case that we know that m is a quadratic residue, or we can't. $\endgroup$
    – kentakenta
    Jun 17, 2021 at 16:51

1 Answer 1


TL,DR: a conjuction of simple $\Sigma$-protocols can prove this compound statement in zero-knowledge. However, the proof is somewhat large.

First, let's break down your compound statement into simpler statements. Observe that essentially you want to prove in zero knowledge for $C_1=m^e$ and $C_2=g^m$ that the following relation $\mathcal{R}(x,\omega)$ ($x$ is the public parameter and $\omega$ is the witness) holds: $$\mathcal{R}=\{((C_1,C_2),(m,l)):m\in QR_{N}\land C_1=m^e\bmod{N}\land C_2=g^m\bmod{p}\}, $$ where $l$ is the square root of $m\bmod{N}$, i.e., the witness is the $(m,l)$ pair. For the sake of simplicity let's use the following notation for the elementary statements: $$\mathcal{R}_1=\{((C_1,C_2),(m,l)):m\in QR_{N}\}, $$ $$\mathcal{R}_2=\{((C_1,C_2),(m,l)): C_1=m^e\bmod{N}\}, $$ $$\mathcal{R}_3=\{((C_1,C_2),(m,l)):C_2=g^m\bmod{p}\}. $$

Note that both elementary statements $\mathcal{R}_2$ and $\mathcal{R}_3$ are easy to prove with $\Sigma$-protocols, since both of the relations prove knowledge of a preimage under a group homomorphism (i.e., of $w$ satisfying $x=\phi(w)$). In the case of $\mathcal{R}_2$ the group homomorphism $\phi(\omega)=\omega^e$, while in $\mathcal{R}_3$, the homomorphism is $\phi(\omega)=g^{\omega}$. These are quite standard statements and you can find how to prove the preimage of a homomorphism in Bangerter et al. or in the Boneh-Shoup book, among many others.

To prove $\mathcal{R}_1$ is a little bit tricky at the first sight, since $m$ needs to be kept secret and we want to prove that $m$ is a quadratic residue, i.e., $m\in QR_N$. In almost all deployments of the RSA cryptosystem $e$ is odd (I assume this is also the case in your application), so $C_1=m^e\in QR_{N} \iff m\in QR_{N}$. I also assume that the encryptor knows $l$, one of the square roots of $m$, since the factorization is unknown. If the encryptor does not know such an $l$, then it cannot prove that it is a quadratic residue, because it does not know the factorization. Given this discussion, now $\mathcal{R}_1$ essentially entails proving the following statement: $$\mathcal{R}_1=\{((C_1),(l)):C_1=l^{2e}\bmod{N}\}, $$ which is again a proof of the knowledge of a preimage of a group homomorphism. We know how to prove this statement.

To combine all these to obtain a zero-knowledge proof for the compound statement $\mathcal{R}$, the verifier just needs to send the same random challenge for all the elementary statements (the random challenge is different across the repetitions of the protocol though!).

What's the size of the proof? For $\Sigma$-protocols in groups of unknown order, the soundness error is high, so one needs to repeat the $\Sigma$-protocol many times to obtain reasonable levels of soundness. In each repetition, the soundness error decreases by $\approx 1/2$. Hence, the protocol must be repeated sequentially to get a sufficiently small knowledge error (e.g., $80$ sequential repetitions are required to obtain a knowledge error of $1/2^{80}$). This would result in a proof consisting of $2*2*80=320$ group elements for the $3$ elementary statements (2 of the statements occur in an RSA group, hence we need to repeat many times).

To circumvent this efficiency limitation you need to use a common reference string in order to reduce the proof size. See Bangerter et al.

Hopefully, this helps! Let me know if I left any grey area in the answer!

  • $\begingroup$ Thank you so much for such detailed explanation, I saw the paper of Bangerter et al. first time. @fractalice pointed out another concern I have beside efficiency as a comment. Do you have an idea about that situation? $\endgroup$
    – kentakenta
    Jun 17, 2021 at 16:58
  • 2
    $\begingroup$ To alleviate the issues mentioned by @fractalice (namely that $m$ might not be well defined), you might want to add a range proof to ensure that $m\leq p$. I think that would fix the issue. $\endgroup$ Jun 18, 2021 at 6:33
  • 1
    $\begingroup$ That really makes sense. Another idea I come up was instead of proving equivalance, I may try to add a hashing from $QR_n$ to $\mathbb{Z}_p^*$. Thanks again for your reply. $\endgroup$
    – kentakenta
    Jun 18, 2021 at 10:08
  • 1
    $\begingroup$ Another option is to define your group $\mathbb{G}$ to be of order $n$, the same as the RSA group. This leads to a big elliptic curve, but then you do not need expensive range proofs to guarantee soundness. $\endgroup$ Jun 19, 2021 at 11:25

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.