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} \}$?


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.

  • $\begingroup$ Thank you, sir! But in my question, the generators are different, they are g1, g2, g3, respectively. $\endgroup$ – Felix LL Oct 20 '20 at 8:02
  • $\begingroup$ I think the $s,t$ in the question are meant to be the textual "s.t." aka "such that"... $\endgroup$ – SEJPM Oct 20 '20 at 9:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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