Technology / Software / 

12 Nov 2017

Time Lock Encryption and Other Developments

The last few months have been particularly busy for me, and as a result I haven’t been keeping tabs on basically anything outside of my day job. It was therefore interesting to read Gwern Branwen’s recently-updated article on “time lock” encryption, which has always been a topic of interest to me due to its wide range of applications.

Reliable time-lock encryption has been a goal since the early days of widespread strong cryptography, and is often discussed in the context of key escrow schemes like Shamir’s Secret Sharing Scheme (SSSS).

But in many ways, time-lock encryption has more practical applications to the average user than an escrow system like SSSS. (Although in part this is because SSSS has never, to my knowledge anyway, been implemented in an easy-to-use fashion. It has remained the province of very high-end applications, like signing the DNSSEC root zone key.) There are lots of applications where people don’t use cryptography because of the risk of data loss – making your data as vulnerable to complete and catastrophic loss as the key (which is sort of inherent in any good cryptographic scheme) is often not desirable. Similarly, there are probably places in which people are using data encryption and taking on the risk of data loss unknowingly, whether personally or on behalf of others. E.g. the person who encrypts their personal computer and memorizes the key, and then gets run over by a bus. Hopefully their family didn’t need or want anything on that computer’s drive!

A reliable system for time-lock cryptography would provide a good backstop to traditional key management techniques. To continue the hypothetical, a user could configure their hard drive’s encryption to be openable using their memorized password, or in ten (or twenty, or a hundred) year’s time. Suddenly, the necessity of writing down the password and filing it away somewhere (a huge vulnerability) is reduced, and the data is not irretrievably lost to civilization (or at least that subset of civilization that’s interested, perhaps their family) should the person with the key meet a premature end.

Most approaches to time-lock cryptography rely on proof-of-work systems that are fundamentally similar to public key schemes, only with a work factor that is intentionally chosen to be low enough to be broken via brute force in some predictable amount of time. The earliest approaches that I’m familiar with, batted around on Usenet and Slashdot back in the 90s, were literally just PK crypto with short key lengths, based on certain assumptions of the recipient’s computing budget. These weren’t great, because some (e.g. RSA and DSA) could be parallelized. Finding out that your 10-year time-lock was actually a 10-day time-lock to someone with 365 computers to throw at the problem is less than ideal.

More recent proposals have used algorithms which are designed to be resistant to parallelization. Something like scrypt, which is designed to require significant amounts of memory to compute, can be used to enforce bounds on an attacker/recipient in order to keep them at least approximately close to the sender’s assumptions. (Although there’s always the risk that the algorithm might be flawed and someone in the future might dramatically decrease the cost-to-compute.) And most proposed implementations generally involve regular randomization of the time-lock key, e.g. changing it with each successful normal login, to ensure that newly-added data is protected for some minimum amount of time. (Backups, of course, are vulnerable sooner.)

But all of these approaches have a flaw, which is they aren’t locked to absolute time, but rather to relative effort. What matters is basically how badly someone wants to get at the data, not how much time has actually passed. If nobody knows what’s inside, and thus isn’t willing to throw some significant processing power at the time-lock over a long time, the contents will never be revealed – conversely, if too many people are interested, it increases the risk that the contents will be released prematurely due to time/resources tradeoffs inherent in brute-force problems.

This always struck me as something of an unsolvable problem: you want to encrypt the message with a key that’s known only in the future, preferably widely known (sparing the recipient the requirement to do any work), but you are stuck in the present; how can you possibly know what will be common knowledge in the future? Most true time-lock proposals therefore punt from the technological domain into the social, and rely on trusted third parties or the legal system to provide key escrow.

However, blockchain-based cryptocurrencies present an intriguing path that did not exist back in the 90s when much of the original work on this class of problem was being done. Public blockchains provide, purely as a side-effect of their intended purpose as distributed proof of work for their underlying cryptocurrencies, a sort of verifiable “clock”, as a result of the number of blocks in the chain increasing over time.

To be perfectly honest, if this works well, it will be one of the more intriguing applications of ‘blockchain’ that I’ve seen recently.