0
$\begingroup$

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)$.

$\endgroup$
  • $\begingroup$ A Diffie-Hellman tuple is $(g,g^x,g^y,g^{xy})$. $\endgroup$ – fkraiem Dec 12 '17 at 12:08
  • $\begingroup$ @fkraiem see page 5, here: link.springer.com/content/pdf/10.1007%2F3-540-44598-6_15.pdf $\endgroup$ – Ay. Dec 12 '17 at 12:55
  • $\begingroup$ 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? $\endgroup$ – knbk Dec 12 '17 at 13:11
  • $\begingroup$ @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. $\endgroup$ – Ay. Dec 12 '17 at 14:36
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Ay. Dec 12 '17 at 17:15
  • $\begingroup$ @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). $\endgroup$ – tylo Dec 13 '17 at 13:04

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.