For unknown group order such as RSA groups $ G %$, it takes $T$ sequential steps to compute the below function (time-lock puzzle).

$$ y = g^{2^T} mod N$$

This paper states that if $ /Phi(N) $ (Group order) is known, it takes only two exponentiation to compute $y$.

$$ e = 2^T mod |G| $$ $$ y = g^e $$

I am not sure I understand how these two results are equivalent.

  • 1
    $\begingroup$ $e = 2^T mod |N|$ should be $e = 2^T \bmod \varphi (N)$. Knowing the $\varphi$ helps to reduce the power. The two exponentiation are the last two exponentiation. The operations re not counted. $\endgroup$
    – kelalaka
    Jun 14, 2021 at 21:36
  • $\begingroup$ I know it is reduced. However, I give values to check the results but it fails $\endgroup$ Jun 14, 2021 at 22:38
  • $\begingroup$ Did you compute $y = g^e \bmod N$? This is also needed. $\endgroup$ Jun 15, 2021 at 9:46


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.