Sigma protocol when order is unknown In the following paper (page 5) they have a proof that a triple $\left(g,b_{i-1},b_{i}\right)$ is of the form: $\left(g,g^{x},g^{x^{2}}\right)$ for some x.

The relevant text from the paper is as follows:




They say the protocol is based on a classic proof that a tuple is a DH tuple, however I don't agree because I think they're missing a fundamental issue: 

In the ZKP of a DH tuple, the order of g is known, however, here - the order of g is not known because it might leak information about $\phi(N)$. 

My goal is to turn the protocol in the paper to a Sigma protocol to make it non-interactive. 

I tried to construct a witness extraction (to prove the special soundness property) for the protocol in the paper but I constantly hit a wall where I have to know the order of g:

So assume that we have 2 different transcripts with the same $z_{i},w_{i} $ but different challenges $c_{i},c'_{i}$ that the verifier accepts.

Thus, the following equations hold:

$(1)~\,g^{y_{i}}\cdot b_{i-1}^{-c_{i}}=z_{i}$

$(2)~b_{i-1}^{y_{i}}\cdot b_{i}^{-c_{i}}=w_{i}$

$(3)~ g^{y_{i}'}\cdot b_{i-1}^{-c'_{i}}=z'_{i}$

$(4)~ b_{i-1}^{y'_{i}}\cdot b_{i}^{-c'_{i}}=w'_{i}$

From the first equation and the third equation we get that:

$g^{y_{i}}\cdot b_{i-1}^{-c_{i}}=g^{y_{i}'}\cdot b_{i-1}^{-c'_{i}}$ , thus   $g^{y_{i}-y'_{i}}=b_{i-1}^{c_{i}-c'_{i}}. $

However, now I'm stuck because I cannot find $\left(c_{i}-c'_{i}\right)^{-1}mod\,\phi(N)$ because I don't know $\phi(N)$ in the first place  (as an efficient witness extractor), nor I can do some kind of $gcd(a,b)=1$ trick . 

At the same time, this paper hints that it's probably not possible to construct a Sigma protocol while working in groups of unknown order.

However, the protocol in the timed commit paper argues that each ZKP of the $(g, g^x, g^{x^2})$ triples has negligible soundness so it seems to have all the preconditions for a candidate for a Sigma protocol.

What am I missing? 

How do you prove the soundness property of the ZKP from the paper without witness extraction (which seems not possible)?

(By the way - I am aware of a paper that proves this in a different way, I merely want to understand what I'm missing here).

Many thanks in advance.
How do you prove the soundness property of the ZKP from the paper without witness extraction (which seems not possible)?


It is perfectly possible and you've almost done it already! You are right that unknown order groups make your life very complicated when you want to build proofs of knowledge - we know results in this direction (the one you cite) -- although it should be mentioned that they break down as soon as you use a CRS (e.g. as we did in this paper).

But if you only want soundness and not the stronger knowledge extraction, you do not need to compute this cumbersome $(c_i-c'_i)^{-1}\bmod \varphi(n)$.

Let $z_i \gets y_i - y'_i$ and $d_i \gets c_i - c'_i$.

From equations (1) and (3), you get $g^{z_i} = b_{i-1}^{d_i}$.

From equations (2) and (4), you get $b_{i-1}^{z_i} = b_{i}^{d_i}$.

Therefore, it is necessarily, mathematically true that there exists an exponent $x$ such that $g^x = b_{i-1}$ and $b_{i-1}^x = b_i$. Indeed, this $x$ is equal to $z_i\cdot d_i^{-1}\bmod \varphi(n)$. So sure, you can't compute it - but the fact that it exists suffices to prove soundness of the protocol! In other words, $(z_i, d_i)$ still constitute a certificate that the word is in the language, which you can extract whenever the prover produces an accepting proof. This certificate is not a witness with respect to the target relation, but it's existence still suffices to guarantee membership to the language.

Answering questions from the comments


  Can you please point to the witness that we can extract with their protocol ? (and how? :-) )


Consider the following relation $R$: $(a,b,c)$ is in the language if there exists values $(x,y)$ such that $a^x = b^y$ and $b^x = g^y$. That is, $R((a,b,c), (x,y))$ returns 1 iff $a^x = b^y$ and $b^x = g^y$ (and $0$ otherwise). A witness for this relation is a pair $(x,y)$.

First, observe that the language captured by this relation is exactly the same as the language of tuples $(a,b,c) = (g,g^z,g^{z^2})$. The difference is that in the first case, what you see as a witness is a pair $(x,y)$ such that $a^x = b^y$ and $b^x = g^y$, while in the second case, it is a single exponent $z$ such that $a^z = b$ and $b^z = c$. This correspond to a different relation $R'$ for the same language: $R'((a,b,c), z) = 1$ iff $a^z = b$ and $b^z = c$.

In the protocol above, you indeed extract a pair $(x,y)$, which is a witness according to the relation $R$ (hence suffices to prove knowledge for a witness of membership to this language - but a witness with respect to a different relations compared to the one you had in mind, which is the second one, $R'$). Indeed, just set $y_i - y'_i$ to be the $x$ and $c_i - c'_i$ to be the $y$, and you have exactly your extracted witness (since the extractor knows of course $y_i, y'_i, c_i, c'_i$).


  But what is the proof of this soundness? To prove this, you need to prove that if a cheating prover can convince the verifier that a pair not in the language, is in the language - then it can also do something intractable. Can you perhaps tell how would you prove such a thing?


You are getting confused with the situation where we prove computational soundness using some hard problem. If a protocol is only computationally sound, then a proof will look as follow: suppose the word is not in the language, and the prover manages to provide a convincing proof of membership. Then I can use this prover to break a hard problem.

Here, we are in a scenario where the proof is much more direct: the soundness is unconditional. This means that I do not have to show that a prover that proves membership of a word outside the language can be used to break a hard problem: I can directly show that if any prover provides a successful membership proof, then necessarily, the word has to be in the language. No hard problem involved.

To spell it (a bit more) formally:

soundness: the protocol above is unconditionally sound if there does not exist a malicious prover $P$ (even with unbounded power) and a word $(a,b,c)$ outside of the language $L = \{(a,b,c) = (g,g^z,g^{z^2})\}$ such that $P$ provides a convincing membership proof for $(a,b,c)\in L$.

proof of soundness: Fix any word $(g,b_{i-1},b_i)$, and any prover $P$. Use rewinding; with non-negligible probability, we get values $(y_i, y'_i, c_i, c'_i)$ satisfying equations (1) to (4) of your questions. But this implies that there exists values $(z_i,d_i)$ such that $g^{z_i} = b_{i-1}^{d_i}$ (by 1 and 3) and $b_{i-1}^{z_i} = b_{i}^{d_i}$ (by 2 and 4). But now, those two equations imply that there exists some value $z$ such that $(g,b_{i-1},b_i) = (g, g^z, g^{z^2})$. This $z$ is in fact equal to $z_i/d_i \bmod \varphi(n)$: it exists, but you cannot compute it. But since it exists, we can conclude that the word $(g,b_{i-1},b_i)$ does in fact belong to the language $L$! In other terms: each time the prover produces a convincing proof for $(g,b_{i-1},b_i) \in L$, then it is indeed the case that $(g,b_{i-1},b_i) \in L$ -- hence, the prover cannot possibly produce an accepting proof when $(g,b_{i-1},b_i) \notin L$, which proves soundness.


  If the prover guesses the $c_i$ the verifier would send, it can send $z_i = g^{y_i}\cdot b_{i-1}^{-c_i}$ and $w_i = b_{i-1}^{y_i}\cdot b_{i}^{-c_i}$ and the verifier would accept any $b_i,b_{i-1}$ no? Now if it can do it once, it can do it twice, with probability $1/R^2$ which is negligible but still not exactly   ⇒$(g,b_{i-1},b_i) \in L$... what am I missing?


The above attack you suggest does not work, for the following reason: to execute the attack, you must guess $c_i$ and send $z_i = g^{y_i}\cdot b_{i-1}^{-c_i}$ and $w_i = b_{i-1}^{y_i}\cdot b_{i}^{-c_i}$. Then, you say "if it can do it once, it can do it twice, with probability $1/R^2$". But this is not true! Remember that when rewinding the protocol, the same first flow is reused for the two rewinds. Hence, the prover does not get any occasion to create "another" pair $(z_i, w_i)$ by guessing $c'_i$.

Now, it is still true that the above soundness proof can fail, because there is some probability, when you sample a random $c'_i$, that it is equal to $c_i$; when this happens, $c_i-c'_i = 0$, and therefore the word is not guaranteed anymore to be in the language.

But in fact, the only reason this trivial attack applies is because I decided to keep things simple, for the sake of readability. If you want to understand exactly why this issue is not a real problem, here is a high-level sketch of how the fully formal security analysis would proceed:

Sketch of the Fully Formal Proof

Assume that there is a prover $P$ that can break soundness. What (statistical) soundness formally says is that for any (possibly unbounded) candidate prover $P$ which picks a word $X$ and interacts with the verifier $V$, the probability that ($X \notin L$) AND ($V$ is convinced) must be negligible. So assuming a prover that can break soundness means assuming that there exists a $P$ which outputs a word $X$ and interacts with the honest verifier $V$, such that

$\mathsf{Pr}[X \notin L \wedge V \text{ is convinced}] \geq \varepsilon,$

for some non-negligible quantity $\varepsilon$ (warning: I'm again hiding some technicalities here about the exact quantifiers when defining "negligible" and "non-negligible").

Hence, what we have is a prover that outputs a word $X$ and interacts with $V$ such that it happens simultaneously that $X$ is not in $L$ and $V$ accept the interaction, with some non-negligible probability $\varepsilon$.

The first question is:
How do we extract from this prover the values which satisfy equations (1) to (4) in your question?

The answer I gave before was just "we use rewinding", but this does not explain why it works. A single run of the prover outputs a word $X$ and a transcript $T$ of his interaction with $V$, such that $X \notin L$ and $V$ accepts, with proba $\varepsilon$. But what we want is to get two accepting transcript, with respect to the same word $X \notin L$, and also with respect to the same first flow.

It turns out that there is a simple lemma, the splitting lemma, that allows exactly to do that -- see for example page 10 of my paper (which I already mentioned in this answer). This lemma allows to show that we can fix the word and the first flow, and repeat the rest of the protocol twice; and still, the word $X$ will not be in $L$ yet both transcripts (with the same first flow, but a different second flow) will be accepted, with overall probability at least $\varepsilon^2/4$. This is not too hard, but not entirely trivial either - it's a good exercise in probabilities.

Now, if we found two transcripts as above, then we can do exactly as I said previously and use equations (1) to (4) to verify that $X$ must be in the language, therefore reaching a contradiction (hence such a cheating prover $P$ does not exist). Note that we do not need to find these transcripts with probability 1: the simple fact that we could find them with some non-negligible probability already suffices to reach the contradiction.

Another way to view it is that extracting the witness (for the relation $R$) cannot usually be done with a single run of the protocol: you need to repeat the above procedure on average $4/\varepsilon^2$ times (which is polynomial) to successfully extract a witness by the above procedure. This issue is exactly the reason why the standard definition of proofs of knowledge does not say that the witness can be extracted in strict polynomial time, but rather in expected polynomial time. Here, we can extract a witness successfully, but the running time of the extraction procedure will only be $O(4/\varepsilon^2)$ in expectation.