4
$\begingroup$

Most successive squaring time lock puzzles I've seen appear to be broken by Shor's algorithm. Is there another practical and efficient time lock protocol that is not broken by Shor's algorithm? If not, what will I need to make one?

time lock requirements

What I mean as a time lock puzzle is something that balances being cheap to crack, but requires a lot of time to crack. This is achievable by requiring that a solver computes a long, non-parallelizable function. However, it has to be very cheap (less than a minute of modern CPU time) to make. In order to encrypt something with the puzzle, the creator probably needs to know the outcome of the puzzle when creating it. If there is a way to encrypt something with out knowing the solution (via asymmetric encryption) that will also be acceptable.

known research

I have read that as of 2014 there were no (at least practical) alternatives to successive squaring. A lot has happened since then. One more recent creation, verifiable delay functions(VDF), are very similar to time lock puzzles but has a different purpose. It may be worth looking in to to see if VDFs can be converted to time locks.

Improve this question
$\endgroup$
4
  • $\begingroup$ What about just iterating a quantum-resistant hash function, i.e. you take $H(H(H(....H(x))))$, for a quantum-resistant hash function $H$. $\endgroup$
    – István András Seres
    Commented May 25, 2020 at 11:58
  • 3
    $\begingroup$ @IstvánAndrásSeres: the issue with a $H^n(x)$ based timelock is 'how do you use it to unlock a predetermined value?' That is, how do you put something in the safe in the first place? $\endgroup$
    – poncho
    Commented May 25, 2020 at 13:09
  • $\begingroup$ @IstvánAndrásSeres The problem with that is that I need to know the outcome of H(H(H(...H(x)))) without doing the calculations myself. That is what's necessary to "put something in the safe" as poncho was talking about. $\endgroup$
    – Nic
    Commented May 25, 2020 at 13:30
  • $\begingroup$ It seems like this calls for a one-way permutation, or a trapdoor permutation. Some weak candidates would be MiMC, or MiMC with a different permutation polynomial (there are some candidate PPs which may be harder to invert). Some other candidates are mentioned in crypto.stackexchange.com/a/11583/56529, but nothing highly promising. $\endgroup$
    – Daniel Lubarov
    Commented Aug 10, 2020 at 4:25

3 Answers 3

Reset to default
3
$\begingroup$

A similar construct to a time-lock puzzle is a verifiable delay function. They have a similar notion of "inherent sequentially". They have an unrelated "public verifiability" property which you do not care about.

Boneh et al. build verifiable delay function from a construct called ``Incrementally Verifiable Computation'', which they can instantiate from certain SNARKs/SNARGs. There exist lattice based SNARGS, which I imagine are post-quantum.

I have not checked if all of these notions line up to directly give someone post-quantum VDFs (and therefore post-quantum Time-Lock Puzzles), but this seems like an excellent candidate for what you're looking for.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Also worth pointing out is time-lock puzzles from succinct randomised encodings (here and here), which potentially are quantum-safe, but far from practical. $\endgroup$
    – ckamath
    Commented May 25, 2020 at 21:32
  • $\begingroup$ SNARG based VDFs can not be repurposed for time locks. In order to derive x from y (if possible at all), while parallelizable, require computations linearly proportional to the computations required to solve the puzzle. SNARGs, by definition, require you to do the computations ahead of time. $\endgroup$
    – Nic
    Commented May 26, 2020 at 21:49
  • $\begingroup$ Other types of VDFs might be able to be repurposed. VDFs based on polynomial GCF likely can be converted to a time lock puzzle, but polynomial GCF's quantum-safety is unknown and will likely be broken in the near future. They also have a polynomial gap but an exponential gap is what we need. $\endgroup$
    – Nic
    Commented May 26, 2020 at 21:59
2
$\begingroup$

There is an interesting time lock technique known as 'delay encryption'. This is based on isogenies of supersingular curves and pairings. As we know, Supersingular Isogeny curves are one of the reference post quantum ( quantum safe / resistant ) cryptography technique. This technique is related to Time-lock Puzzles and Verifiable Delay Functions. This technique is similar to the Isogeny VDF of De Feo, Masson, Petit and Sanso.

It is summarised as an identity based encryption (IBE) with slow derived private key issuance. This is postulated for applications in Vickery Auctions and Electronic Voting. Please find the research paper on this cryptographic primitive here.

Delay Encryption by Jeffrey Burdges and Luca De Feo

Improve this answer
$\endgroup$
1
  • $\begingroup$ Unfortunately it isn't truely quantum safe, but there is some hope. As explained here: "Finally, while the use of isogenies does not magically make our functions post-quantum (in fact they can be broken with a discrete logarithm computation), one of our two constructions still offers some partial resistance to quantum attacks; we call this property quantum annoyance." $\endgroup$
    – Nic
    Commented Jun 21, 2020 at 17:17
1
$\begingroup$

No, not yet.

Let: "time" mean the total amount of computations, and

"parallel time" mean the minimum amount of sequential computations

In order to meet the practical requirements for a puzzle that will last until Shor's algorithm can be implemented, the asymptotic complexity needs to meet the following requirements:

  1. The solving time and parallel time need be within quasi-linear of each other.
  2. There is an exponential gap between creation time and solving parallel time.

We don't currently know how to meet those requirements, but we can make time lock puzzles that don't quite reach there. These are practical only with a high budget for creation and solving.

A group of trusted and wealthy parties can build a time lock puzzle together and encrypt a quantum safe private key. People can then encrypt their own private keys with the previously made public key. If many people do this, it will likely convince historians to cough up the money to solve the puzzle.

There are also other ways to make a time capsule with out this kind of puzzle.

Improve this answer
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.