Zero-knowledge proof for multiplication in the exponent

Question

We have $c_1=g_1^x$, $c_2=g_2^y$ and $c_3=g_3^{x/y}$, where $g_1,g_2,g_3$ are generator of a group of order $n$ and we don't know the DL between them. Is there any sigma protocol or zkp that can prove the language $L=\{c_1,c_2,c_3\mid \exists\, x,y, \text{ such that } c_1=g_1^x \ \& \ c_2=g_2^y \ \& \ c_3=g_3^{x/y} \}$?

Answer 1

If the generators were the same, then this would be a standard Diffie-Hellman tuple sigma protocol. In order to see this, note that a Diffie-Hellman tuple is defined to be $(c_1,c_2,c_3)$ such that $c_1 = g^a$, $c_2 = g^b$ and $c_3 = g^{ab}$. Setting $a=y$ and $b = x/y$, we have that $ab = x$. Thus, all you need to prove is that $(c_2,c_3,c_1)$ is a Diffie-Hellman tuple.

However, given that they are not the same, the above isn't correct. The first thing to notice about this language with different generators is that it is actually trivial. That is, it is always possible to solve and find $x,y$ that fulfil the equations. Thus, such a proof would only be interesting as a proof of knowledge (as such, one should refer to the relation and not the language, and $g_1,g_2,g_3$ must of course be part of the public statement).

Beyond that, I don't think it's trivial. I have played around a bit for a few minutes and the naive things one could do won't work. However, from experience, sigma protocols typically aren't that hard to build, and this looks like something that should work. But it may be hard and require research. I am leaving this partial answer here, even though it isn't correct, in order to be of some help regarding finding the direction.

Answer 2

As already stated by Yehuda Lindell, the language is actually trivial, however the proof-of-knowledge is interesting. I'll attempt to give a sigma protocol for proving knowledge of $(x, y)$ s.t. the relation $R: (C_1 = xG_1, C_2=xG_2, C_3=xy^{-1}G_3)$ holds for comitted $C_{1,\dots,3},G_{1,\dots,3}$, with the (probably unnecessary) apologies for using additive notation.

Peggy draws two elements $r_1, r_2 \in \mathbb{F}_p$ and sends to Victor $$ A=r_1G_1, \quad B=r_2G_2,\\ X=r_1r_2G_3, \quad Y=(r_1y^{-1}+xr_2)G_3 $$

Victor responds with a challenge $s \in \mathbb{F}_p$, to which Peggy responds with $$a=r_1-xs, \quad b= r_2-y^{-1}s$$

Victor now verifies knowledge of $(x, y^{-1})$ through the Schnorr-inspired

$$ aG_1 = A-sC_1, \quad bG_2=B-sC_2 $$ and for well-formedness of their relation, Victor checks $$ ab G_3 = X-sY+s^2C_3 $$

---

Sketch of a witness extractor: using two transcripts for $(s, s')$, Victor may easily extract $x, y, r_1, r_2$. We now argue that $R$ holds for $(x, y)$.

For $C_1$, we have $aG_1 = A-sC_1$: $$ \begin{align*} aG_1 &= A-sC_1\\ sC_1 &= A - aG_1\\ C_1 &= s^{-1}A - s^{-1}r_1G_1 + xG_1\\ \end{align*} $$

This means that either $A=r_1G_1$ or Peggy knows something about discrete logarithms that we don't (it would violate CDH). The same argument can be used with $b$ for $C_2$.

For $C_3$, we know $abG_3=X-sY+sC_3$:

$$ \begin{align*} abG_3&=X - sY + s^2 C_3\\ sC_3&=s^{-1}(r_1-xs)(r_2-y^{-1}s) G_3 - s^{-1}X + Y \\ &=s^{-1}(r_1r_2-r_1y^{-1}s-xsr_2+xy^{-1}s^2)G_3 - s^{-1}X+Y \\ &=s^{-1}r_1r_2G_3 -r_1y^{-1}G_3-xr_2G_3+sxy^{-1}G_3 - s^{-1}X+Y \\ \end{align*} $$

Now, if we assume Peggy does not know how to compute discrete logarithms, $X$ and $Y$ are both in terms of $G_3$. Additionally, Peggy did not know $s$ before hand, so we can group terms based on coefficients:

$$ \begin{align*} s^{-1}X &= s^{-1}r_1r_2 C_3\\ Y &= (r_1y^{-1} + xr_2)G_3\\ sC_3 &= sxy^{-1}G_3 \end{align*} $$

The latter of this result is what we wanted to prove, after multiplying with $s^{-1}$.

---

I fail to prove, or even convince you about:

• zero-knowledgeness (it certainly is not, but should be possible by adding blindness terms and massaging the protocol a little).
• optimality in terms of efficiency

---

This is slightly more efficient than the approach of Vadym, and only gives two degrees of freedom to the prover ($r_1$ and $r_2$), which feels more natural to me. That said, I scribbled this down with a headache, so I might have done something incredibly stupid.

The general approach seems to hold, however: given two secrets, allow two degrees of freedom, a set of commitments to setup the transformation, require a challenge and show that the transformed commitments hold. With some more work, you might even get rid of $X$.

Answer 3

This proof of knowledge could be solved as a Schnorr-like system by testing polynomials that are quadratic in challenge $d$. In particlular, Prover picks 3 random field elements $(a_1, a_2, a_3)$, and creates 5 initial commitments $(b_1, b_2, b_3, b_4, b_5)$ and 3 responses $(X, Y, Z)$. Last verification equation is a new research (IACR 2008/363 and MFCS 2012).

\begin{gather} b_1 = g_1^{a_1}, \; b_2 = g_2^{a_2}, \; b_3 = g_3^{a_3}, \; b_4 = g_1^{a_2 \frac{x}{y} + y a_3 - a_1}, \; b_5 = g_1^{a_2 a_3} \end{gather}

\begin{gather} X = a_1 + d x, \; Y = a_2 + d y, \; Z = a_3 + d \frac{x}{y} \end{gather}

\begin{gather} g_1^X c_1^{-d} = b_1, \; g_2^Y c_2^{-d} = b_2, \; g_3^Z c_3^{-d} = b_3, \; g_1^{YZ - dX} = b_4^d b_5 \end{gather}

This could be explained as \begin{equation} YZ - dX = d^2 \left( y \frac{x}{y} - x \right) + d \left( a_2 \frac{x}{y} + y a_3 - a_1 \right) + (a_2 a_3) \end{equation} At MFCS, it was shown a set of $k$ non-zero field elements as an invertible product, for a colorable graph with $k$ edges and per-edge color differences.