Sequential squaring ⇒ TLP (RSW puzzle)
Statement
RSW96 give the first candidate time-lock puzzle. To lock a message for squarings, the generator picks an RSA modulus and a random modulo , encrypts under a random key of a symmetric cipher, and publishes , the ciphertext and . Knowing , the generator computes in time ; a solver without the factorization recovers by sequential squarings. RSW96 conjecture that the squarings cannot be parallelized, which is the sequential squaring assumption, and give no reduction from it.
Notes
- The puzzle relies on the hardness of factoring as well as on the sequentiality of squaring, and is therefore vulnerable to advances in factoring and to quantum attacks — MMV11; see Sequential squaring ⇒ FAC.
- Time-lock puzzles with gap against polynomial-size adversaries of depth below are defined by BGJ+16, who construct them from succinct randomized encodings and a non-parallelizing language rather than from squaring.