Suppose there is a cyclic group $G$ of prime order $q$ of elements in $Z_p^*$ with a generator $g$ and a value $x \in Z_q$.

$h_1 = g^{x+1}$

$h_2 = g^{x}$

Is it possible to write $h_2^{((x+1)^{-1})}$ as some combination of $g$ and $h_1$?

$x+1$ is invertible in $Z_q$ only if $gcd(x+1,q)=1$, which means $ax+a = 1 \bmod q$ and $gcd(x,q)=1-a$, so $x$ is not invertable in $Z_q$. However, then it seems that $h_2^{(x+1)^{-1}}$ can't be represented as combination of $g$ and $h_1$.

P.S. I'm trying to figure out whether verifier can distinguish real and fake proofs in this questions if verifier assumes that $x_{tr} = \hat{x}_{tr} +1$, computes $e$ for $\hat{h}$ but adjusts $r_{ch}$.

  • $\begingroup$ Sorry, it indeed was not clear. I've modified the question. $\endgroup$ – pintor Jun 12 '18 at 16:08

Is it possible to write $h_2^{((x+1)^{-1})}$ as some combination of $g$ and $h_1$?

No. Computing $h_2^{((x+1)^{-1})}$ from $g, h_1$ is equivalent to the Computational Diffie Hellman (CDH) problem, which we believe is difficult for some groups.

Here is the proof in the forward direction (your problem is at least as hard); suppose that we had an Oracle that, given $g, h_1 = g^{x+1}$, was able to give us the value $h_2^{((x+1)^{-1})} = g^{x \cdot (x+1)^{-1}}$

First of all, let us set $y = x+1$, and rearrange the Oracle "given $g, g^y$, give us the value $g^{(y-1) \cdot y^{-1}} = g \cdot g^{-y^{-1}}$; with this Oracle, we can easily reconstruct the value $g^{y^{-1}}$.

It is well known that computing the value $g^{y^{-1}}$ given $g, g^y$ is equivalent to the CDH problem; given $h, h^a, h^b$ compute $h^{ab}$. This is done by turning the inverse Oracle into a squaring Oracle (given $h, h^a$, compute $h^{a^2}$). To do this, we set $g = h^a$ and $g^y = h = (h^a)^{a^{-1}}$; we give those two to our inverse Oracle, which returns us $(h^a)^a = h^{a^2}$

Once we have a Squaring Oracle, we can directly solve the CDH problem by computing $h^{a+b} = h^a \cdot h^b$, and then computing $h^{2ab} = h^{(a+b)^2} \cdot (h^{a^2})^{-1} \cdot (h^{b^2})^{-1}$, then a modular square root gives us $h^{ab}$

And there we are done. (Showing the proof in the other direction isn't hard, but I'll leave that as an exercise for the reader)

Hence, if we have a generic way of solving your problem (e.g. by doing algebraic rearrangement of $g$ and $h_1$) that works in an arbitrary group, well, we just showed that the CDH problem is never hard, and we don't currently believe that.


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.