# 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

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