Zero-knowledge proof of a product I have non-negative integers $x,y,z$.  I'm going to give you commitments $C(x),C(y),C(z)$ to them.  Then, I would like to prove in zero knowledge that $xy=z$.  I can choose the commitment scheme to make the zero-knowledge proof easy, if that helps.  What protocol should I use?  Is there a highly efficient protocol for this?

Details: Assume I know that all three of $x,y,z$ fit in $k$-bit integers, i.e., $x,y,z \in [0,2^k-1]$, and $k$ is publicly known.  Given commitments $c_x,c_y,c_z$, I want a zero-knowledge proof of knowledge that I know $k$-bit non-negative integers $x,y,z$ such that $xy=z$ (over the integers) and $c_x,c_y,c_z$ can be opened to $x,y,z$.  It is not sufficient to prove that $xy=z \pmod q$; I want a proof that the equation holds over the integers.  I don't care whether the commitment scheme is information-theoretically hiding or computationally hiding; either is fine.

Preferably, the commitment scheme should also allow me to do range proofs (to prove in zero knowledge that $x,y,z$ are in a particular range).
Use the exponential variant of ElGamal, where the plaintext is encoded in the exponent. Elliptic curve ElGamal is fine. In fact, any public key cryptosystem which allows raising ciphertexts to a power such that this operation corresponds homomorphically to multiplication for the plaintext.

Your commitments are $c_x = \mathsf{E}(x)$; $c_y = \mathsf{E}(y)$; and $c_z = \mathsf{E}(z)$. Additionally, you must commit to an encryption of one: $c_1 = \mathsf{E}(1)$, and prove that it is an encryption of one using a Schnorr proof.

Next, use the Chaum-Pedersen proof of equivalent discrete logarithms to prove the following relation: dlog$_{c_1}c_y = $ dlog$_{c_x}c_z$.

Schnorr proof:

Public knowledge: $a, b$

Private knowledge for $\mathcal{P}$: $s$

Claim: $a = b^s$

$\begin{matrix}
\mathcal{P} &amp; &amp; \mathcal{V} \\
u \xleftarrow{\$} \mathbb{Z}_q &amp; &amp; \\
v \leftarrow b^u &amp; &amp; \\
 &amp; \xrightarrow{\quad v \quad} &amp; \\
 &amp; &amp; e \xleftarrow{\$} \mathbb{Z}_q \\
 &amp; \xleftarrow{\quad e \quad} &amp; \\
r \leftarrow se + u \mod q &amp; &amp; \\
 &amp; \xleftarrow{\quad r \quad} &amp; \\
 &amp; &amp; b^r \stackrel{?}{=} a^ev
\end{matrix}$

The Chaum-Pedersen proof is very similar:

Public knowledge: $a_1, a_2, b_1, b_2$

Private knowledge for $\mathcal{P}$: $s$

Claim: $s = $ dlog$_{b_1}a_1 = $ dlog$_{b_2}a_2$

$\begin{matrix}
\mathcal{P} &amp; &amp; \mathcal{V} \\
u \xleftarrow{\$} \mathbb{Z}_q &amp; &amp; \\
v_1 \leftarrow b_1^u &amp; &amp; \\
v_2 \leftarrow b_2^u &amp; &amp; \\
 &amp; \xrightarrow{\quad v_1,v_2 \quad} &amp; \\
 &amp; &amp; e \xleftarrow{\$} \mathbb{Z}_q \\
 &amp; \xleftarrow{\quad e \quad} &amp; \\
r \leftarrow se + u \mod q &amp; &amp; \\
 &amp; \xleftarrow{\quad r \quad} &amp; \\
 &amp; &amp; b_1^r \stackrel{?}{=} a_1^ev_1 \\
 &amp; &amp; b_2^r \stackrel{?}{=} a_2^ev_2 \\
\end{matrix}$

At this point, I thought my answer was complete, but the questioner correctly notes: "This is an excellent start, but it proves that $xy \equiv z \pmod q$, rather than that $xy=z$. I think if you choose $q$ to be $&gt;2k$ bits long, and combine it with a range proof of the size of $x,y,z$, though, this might work."

It is nice that you specify that $x, y$ and $z$ are in $[0,2^k]$, because that makes the range proof a little easier. In order to prove this range of $x$ (same for $y$ and $z$), do the following:


Commit to $k$ bits of $x$, i.e.: send $\mathsf{E}(x_i)$ to the verifier, where $x_i$ is the $i$th bit of x.
Prove the commitments are encryptions of either 1 or 0.
The verifier can aggregate the bits homomorphically: $\mathsf{E}(x) = \prod_i \mathsf{E}(x_i)^{2^i}$. Use this as the commitment of $x$.


It remains to be shown how to prove that an encryption is an encryption either of 1 or else of 0. This can be done using the CDS proof linking technique (link).

First, note that in the ElGamal cryptosystem, it is easy to prove that an encryption $\mathsf{E}(a)$ encrypts a plaintext $a$. The encryption is given by $\mathsf{E}(a) = (g^y, g^{a+xy})$. Divide $g^a$ out of the second value and then produce a (Chaum-Pedersen) proof that dlog$_g g^y = $ dlog$_{g^x}g^{xy}$.

Second, note that it is also easy to falsely "prove" that an encryption $\mathsf{E}(a)$ encrypts a different plaintext $b$, provided that you control the challenge $e$ sent by the challenger. The claim to be proved is dlog$_g g^y = $ dlog$_{g^x}g^{-b+a+xy}$. Generate the proof transcript as follows (let $a_1$ correspond to $g^y$, $b_1$ to $g$, $a_2$ to $g^{xy}$ and $b_2$ to $g^x$): $e, r \xleftarrow{\$} \mathbb{Z}_q$; $v_1 \leftarrow b_1^ra_1^{-e}$; $v_2 \leftarrow b_2^ra_2^{-e}$.

The central idea of the CDS technique is to generate two proof transcripts, one of which is made interactively with the verifier and the other of which was generated beforehand. This is done in such a way that the verifier cannot tell which one of the two proofs was interactively made and which one was generated earlier. In particular,


The prover generates a proof transcript $T_f$ of the false claim: $T_f = (c_f,e_f,t_f)$, and a first message of the true claim: $c_t$.
The prover sends the two first messages to the verifier: $\mathcal{P} \xrightarrow{\quad c_f, c_t \quad} \mathcal{V}$.
The verifier chooses a random challenge $e \xleftarrow{\$} \mathbb{Z}_q$ and sends it to the prover: $\mathcal{P} \xleftarrow{\quad e \quad} \mathcal{V}$.
The prover interpolates on the line defined by the two points $(0,e), (1,e_f)$ and evaluates it in $2$ to obtain $e_t$.
The prover completes the transcript $T_t$ of the proof of the true claim using $e_t$.
The prover sends both transcripts to the verifier: $\mathcal{P} \xrightarrow{\quad T_f, T_t \quad} \mathcal{V}$.
The verifier verifies the proof transcripts and verifies that $(0,e), (1,e_f), (2,e_t)$ are on the same straight line.


The reason this technique works is because the prover can prove only one of the claims. Having committed to the false proof, he has no degrees of freedom left to choose his challenge for the true proof. Thus, the verifier knows that at least one of the transcripts was produced interactively. Obviously, the order of $T_t$ and $T_f$ must be random because otherwise the verifier can easily tell which one is true and which one is false.