Zero-knowledge proof of a product

Question

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).

Answer 1

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} & & \mathcal{V} \\ u \xleftarrow{\$} \mathbb{Z}_q & & \\ v \leftarrow b^u & & \\ & \xrightarrow{\quad v \quad} & \\ & & e \xleftarrow{\$} \mathbb{Z}_q \\ & \xleftarrow{\quad e \quad} & \\ r \leftarrow se + u \mod q & & \\ & \xleftarrow{\quad r \quad} & \\ & & 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} & & \mathcal{V} \\ u \xleftarrow{\$} \mathbb{Z}_q & & \\ v_1 \leftarrow b_1^u & & \\ v_2 \leftarrow b_2^u & & \\ & \xrightarrow{\quad v_1,v_2 \quad} & \\ & & e \xleftarrow{\$} \mathbb{Z}_q \\ & \xleftarrow{\quad e \quad} & \\ r \leftarrow se + u \mod q & & \\ & \xleftarrow{\quad r \quad} & \\ & & b_1^r \stackrel{?}{=} a_1^ev_1 \\ & & 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 $>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.

Answer 2

To prove that product holds over integers, one would start from commitments with groups of a hidden order. That is, proving party should not know order of the group, which is the case with RSA-like multiplicative group.

Consider Prover responses $\rho_x = tx + \alpha_x$, $\rho_y = ty + \alpha_y$, $\rho_z = tz + \alpha_z$ to Verifier challenge $t$ with initial random coins $\alpha_x, \alpha_y, \alpha_z$ calculated over integers. Consider a polynomial $f(t) = \rho_x(t) \rho_y(t) - t \rho_z(t)$. Degree of this polynomial is quadratic iff relation over secrets $x,y,z$ does not hold. Consider yet another polynomial $F(t) = f(t) - (v_1 t + v_0)$ for $v_1 = x \alpha_y + y \alpha_x - \alpha_z$, $v_0 = \alpha_x \alpha_y$.

One would go for an extended Schnorr-like protocol from probabilistic identity testing $F(t) \equiv 0$ with Schwartz-Zippel lemma. At the first step of such a protocol, one sends commitments to $v_1$ and $v_0$. For details please take a look at An argument for Hamiltonicity.

For easy example, consider secrets $x$, $y$, $z$ from $\mathbb Z_q$ for a large prime $q$. Let $g$, $h$ be generators of a group of order $q$ of Pedersen commitment scheme.

Step 1: Prover chooses $\alpha_x$, $\alpha_y$, $\alpha_z$, $\beta_1$, $\beta_2$ at random from $\mathbb Z_q$, computes and sends commitments to Verifier: $$ v_1 = x \alpha_y + y \alpha_x - \alpha_z, \; v_0 = \alpha_x \alpha_y \\ D_1 = g^{v_1} h^{\beta_1}, \; D_0 = g^{v_1} h^{\beta_1} $$

Step 2: Verifier chooses a challenge $c$ at random from $\mathbb Z_q$ and sends it to Prover.

Step 3: Prover computes responses $\rho_x$, $\rho_y$, $\rho_z, \eta$ and sends them to Verifier: $$ \rho_x = c x + \alpha_x \pmod{q} \\ \rho_y = c y + \alpha_y \pmod{q} \\ \rho_z = c z + \alpha_z \pmod{q} \\ \eta = c \beta_1 +\beta_0 \pmod{q} $$

Step 4: Verifier accepts if $\rho_x$, $\rho_y$, $\rho_z$ open commitments to secrets and $$ g^{\rho_x \rho_y - c \rho_z} h^{\eta} D_1^{-c} D_0^{-1} = 1 $$

Soundness of this proof can be derived from observation that, for invalid secrets, verification equation can only hold for at most two values of challenge, to be compared to at most one such value with the well-known proof. It follows, soundness error is $\frac{2}{q}$.

Efficient range proof from Lagrange 4-squares theorem was introduced at On Diophantine Complexity and Statistical Zero-Knowledge Arguments and was adopted here at ..whether a number is greater than another number without knowing the numbers?. Integer commitment scheme with a group of a hidden order fits range proofs just fine.