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} \}$?
$\begingroup$
$\endgroup$
Add a comment
|
$\begingroup$
$\endgroup$
2
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.
answered Oct 20 '20 at 7:59
