# How should I prove this protocol?

I'm recently reading Berry Schoenmakers's Lecture Notes Cryptographic Protocols (page. 53) and confused about this following question:

Let $g$, $h$ denote generators of a group of large prime order $n$ such that $log_gh$ is unknown to anyone. Design Σ-protocols (and prove correctness) for the following relations:

{($A, B; x, y, z$) : $A = g^xh^y,B = g^{1/x}h^z, x \neq 0$};

My prove intuition is using Okamoto's protocol for $A = g^xh^y$ and $B = g^{1/x}h^z$, then how to prove the relation between $x$ in $A$ and $1/x$ in $B$? Or is there any other way to prove it?

## 3 Answers

The two previous answers certainly solve the problem. Soundness of Geoffroy's protocol is fine indeed, but there is the appearance of the witness $$x$$ in the computation of the announcement $$(A',B')$$ as $$B'=g^{r_x/x} h^r$$. This can be avoided, however, and at the same time one can find the protocol maybe in a bit more natural way as follows.

Starting with $$A=g^x h^y$$ and $$B=g^{1/x} h^z$$, we see that $$B$$ is a Pedersen commitment to the (multiplicative) inverse $$1/x$$ of the committed value $$x$$ in the Pedersen commitment $$A$$. So, $$x$$ appears both in $$A$$ and $$B$$ and these two occurrences need to be connected somehow. EQ-composition is a very effective way to accomplish this, but we cannot directly apply it to exponents of the form $$x$$ and $$1/x$$. A simple way out is to move $$x$$ around a bit in the equation for $$B$$ by raising both sides to the power of $$x$$, such that we get: $$A=g^x h^y,\qquad g=B^x h^{-zx}.$$ We can now apply EQ-composition to the factors $$g^x$$ and $$B^x$$, but one may wonder about the new factor $$h^{-zx}$$ which also depends on $$x$$. Fortunately, such a factor causes no problems because we can think of $$h^{z'}=h^{-zx}$$ as a factor that is independent of $$x$$; it's like replacing $$z$$ with $$z'=-zx$$, which is fine because this is a one-to-one transformation for nonzero $$x$$.

For the $$\Sigma$$-protocol we get:

1. Prover sends announcement $$(a,b)=(g^u h^v, B^u h^w)$$ with $$u,v,w\in_R\mathbb{Z}_n$$.

2. Verifier sends challenge $$c\in_R\mathbb{Z}_n$$.

3. Prover sends response $$(r,s,t)=(u+c\,x, v+c\,y, w-c\,z\,x) \bmod n$$. Verifier accepts if $$g^r h^s = a A^c$$ and $$B^r h^t = b g^c$$.

It is instructive to see why special soundness holds. So, let's consider two accepting conversations $$(a,b;c;r,s,t)$$ and $$(a,b;c';r',s',t')$$ with $$c\neq c'$$. Then we find: $$\begin{array}{cl} & g^r h^s = a A^c,\ g^{r'} h^{s'} = a A^{c'},\quad B^r h^t = b g^c,\ B^{r'} h^{t'} = b g^{c'}\\ \Rightarrow& g^{r-r'} h^{s-s'} = A^{c-c'} ,\quad B^{r-r'} h^{t-t'} = g^{c-c'} \\ \Leftrightarrow& A = g^{\frac{r-r'}{c-c'}} h^{\frac{s-s'}{c-c'}},\quad B = g^{\frac{c-c'}{r-r'}} h^{-\frac{t-t'}{r-r'}}. \end{array}$$ Here, we are using that $$r\neq r'$$ holds as well: otherwise we see that $$B^{r-r'} h^{t-t'} = g^{c-c'}$$ is equivalent to $$h^{t-t'} = g^{c-c'}$$, and we would have $$\log_g h = (t-t')/(c-c')$$, contradicting the assumption that $$\log_g h$$ is unknown. Hence, a witness is obtained as $$x=(r-r')/(c-c')$$, $$y=(s-s')/(c-c')$$, and $$z=-(t-t')/(r-r')$$. Clearly, $$x\neq0$$ and $$B=g^{1/x} h^z$$ holds, as well as $$A=g^x h^y$$.

The same line of reasoning can be applied to show special soundness for Geoffroy's protocol.

• This solution is to modify the original relation first, it expects modified relation to fit the well-known equality proof. My target was to show the idea of using higher-degree polynomials in challenge of Verifier (more than linear), that might happen to cover tricky relations as-is. Graph isomorphism, colorability, Hamiltonican cycle with "large" non-binary challenges would give some examples. Apr 14 at 16:40

Yes, this is an exercise in a great textbook, so maybe giving just intuition could be appropriate. First, one would open both commitments (for $x$ and $1/x$) with standard responses that are linear in challenge. Next, one would multiply that responses to show that power-two (square) coefficient (challenge of verifier is the variable here) is exactly one. This kind of technique was suggested to prove a non-zero secret by existence of it's inverse at (shameless) the paper at MFCS 2012 on graph colorability.

The natural way to prove this relation is to prove knowledge of committed values $(m,m')$ whose product is $1$. Intuitively, you want to do this by showing that the discrete logarithm of $g$ in base $B$ is also the discrete logarithm of $A$ in base $g$ (this is not correct as such but it gives an intuition).

I would proceed as follows: (I've not looked at the soundness proof so it could contain a mistake, but should suffice to clarify the intuition on how to proceed)

• The prover sends $A' = g^{r_x}h^{r_y}$ and $B' = g^{r_x/x}h^r$ for random exponents $(r_x,r_y,r)$
• The verifier sends a challenge $e$
• The prover answers with $d_x = x\cdot e + r_x \bmod n, d_y = y\cdot e + r_y \bmod n$, and $d = r - zd_x \bmod n$
• The verifier checks that $A^eA' = g^{d_x}h^{d_y}$ and $g^eB' = B^{d_x}h^{d}$

The two verification equations convince him that the prover can open $A$ to some value $x$ so that $B^x$ commits to $1$.

• One more question: In you construction, $x$ exists in $B'$, which is the first time i see a witness existing in prover's first round message. Besides, I can verify the construction, but I just cannot get the underlying intuition. intuitively, the same $r_x$ in $A'$ and $B'$ make some sense, besides that, I cannot figure out how it comes. maybe something important i missed. or this construction is the result of inspiration that has no fixed model to follow?
– D.V.
May 12 '17 at 11:21