# Can we prove $(a,b,c,d)$ is of form $(g,g^x,g^y,g^{xy})$ without knowing $\phi (N)$?

assume $N=pq$ where $p$ and $q$ are two large prime numbers and all computations are modulo $N$.

given $\phi(N)$, one can prove that the tuple $(a,b,c,d)$ is of the form $(g, g^x,g^y, g^{xy})$, i.e. it is a Diffe-Helman tuple.

Question: Can we prove that the $(a,b,c,d)$ is a Diffe-Helman tuple without knowing $\phi(N)$?

Edit- Application:

Assume someone is given $(g,g^{2^3},g^{2^5}) \bmod N$. He wants to compute $g^{2^{8}}$ and prove that he has done the job correctly, but he does not know $\phi(N)$.

• A Diffie-Hellman tuple is $(g,g^x,g^y,g^{xy})$. – fkraiem Dec 12 '17 at 12:08
• @fkraiem see page 5, here: link.springer.com/content/pdf/10.1007%2F3-540-44598-6_15.pdf – Ay. Dec 12 '17 at 12:55
• Note that the actual tuple used in the paper is $(g, g^x, g^x, g^{x^2})$, which is a regular Diffie-Hellman tuple with $x = y$. The paper explains how this can be verified without revealing $\phi(N)$. With which part of the explanation are you having trouble? – knbk Dec 12 '17 at 13:11
• @knbk Yes thanks for the comment! I assume by "the paper" you mean the paper I cited. What I need is a bit different: I want the party who does not know $\phi(N)$ to prove to the other party (who may or may not know $\phi(N)$) that the above tuple has constructed well. Thanks again. – Ay. Dec 12 '17 at 14:36

## 1 Answer

From the paper you linked in the comment:

Each of these $$k$$ proofs take four rounds and they can all be done in parallel. These proofs are based on a classic zero-knowledge proof that a tuple $$( g, A, B, C)$$ is a Diffie-Hellman tuple. [13]

That classic proof works as like this (ommitting the moduli, all calculations within the group structure):

• The tuple $$(g,A,B,C)$$ is given
• The prover additionally knows $$x$$, s.t. $$B = g^x$$ and $$C = A^x$$. This is the same as a DH tuple, where the prover just knows one of the exponents. If we define $$y$$ as solution to $$B = g^y$$, then the tuple has the standard form $$(g,g^x,g^y,g^{xy})$$.
• In the ZK proof, the prover first chooses $$r$$ randomly, and then sends $$(m_1,m_2) = (g^r,A^r)$$ to the verifier.
• The verifier chooses a bit $$b$$
• The prover sends $$r' = r + bx$$
• The verifier checks if $$g^{r'} = m_1 B^b$$ and $$A^{r'} = m_2C^b$$

Can we prove that the $$(a,b,c,d)$$ is a Diffe-Helman tuple without knowing $$ϕ(N)$$?

As you can see above, the zero knowledge proof does not require knowing $$\phi(N)$$, it doesn't require anything else than the normal group operation. So yes, that's possible.

Edit- Application:

Assume someone is given $$(g,g^{2^3},g^{2^5})\mod N$$. He wants to compute $$g^{2^8}$$ and prove that he has done the job correctly, but he does not know $$ϕ(N)$$.

Well, that does not work. Computing $$g^{2^8}$$ from the given values is an instance of the computational Diffie-Hellman problem. However, if it's possible to calculate that, then the DDH problem can't be hard either. And that means, it doesn't really make sense to create a ZK proof in the first place. If you want to prove that, I think this would contradict the strong RSA assumption.

Ah, as a final note: Knowing $$\Phi(N)$$ is equivalent to knowing the fatorization of $$N$$. However, that does not necessarily imply, that this knowledge allows the calculation of DLOGs (unless the modulus is constructed in a special way, e.g. $$\phi(N)$$ just has small factors). But what is gained is the ability to calculate discrete roots - in RSA the exponentiation by $$d$$ is just the calculation of the $$e$$th root.

• thank you very much for the nice answer. However, I have a few questions/comments: yes, the paper says that it's based on classical ZK proof, but it provides a variant of it in which there is a value $q$ which is an order of element $g$ and I think it should be kept secret from the verifier. I understand that computing $g^{2^{8}}$ will be time-consuming but it is feasible and that's why the "forced opening" phase of the paper works. – Ay. Dec 12 '17 at 17:15
• @AdrianAd Basically the knowledge of $\phi(N)$ in that protocol allows the committer to generate the commitment with $O(k)$ modular exponentiations - while force open would take $2^k$ squarings, and $k$ being in the range of $30$ to $50$. With knowledge of $g$ and $k$, everyone can calculate $g^{2^{2^k}}$ - by squaring $2^k$ times. But by knowing $\phi(N)$, the committer can do that step in one exponentiation with the exponent $2^{2^k} \mod \phi(N)$ (which requires at most $2n$ squarings and multiplications). – tylo Dec 13 '17 at 13:04