Hacker News new | past | comments | ask | show | jobs | submit login
Time-Lock Encryption (2011) (gwern.net)
61 points by vermilingua on Jan 17, 2020 | hide | past | favorite | 14 comments



I only skimmed the post, but referring to the blackbox approach with some blockchain as trustless clock:

Given the black box was created when block X was the current one and is defined to release the key some N days later, so ca. (N * 144) blocks later, if the bitcoin blockchain with a block time of 10 minutes is used.

Wouldn't an attacker be able to create an isolated network using the existing blockchain up to block X, push the difficulty in this "new" network artificially down and create the amount of required blocks much faster than the actual bitcoin network.

Once the chain is calculated up to a specific point, the blackbox program can be executed in the emulated network and will release the key before the actual deadline.

Am I missing something or is this conceptually broken?


> Wouldn't an attacker be able to create an isolated network using the existing blockchain up to block X, push the difficulty in this "new" network artificially down and create the amount of required blocks much faster than the actual bitcoin network.

You would need to invest an enormous amount of hashpower to create so many blocks that the difficulty adjustment could ratchet down (and if you don't, it's an invalid blockchain period), and this expensive attack can be blocked simply by changing the witness proof to require blocks have a certain minimum hashpower on average, which will be safe since hashpower has historically only gone up, and lets you specify the total cost of unlocking for anyone, which, like PoW, is your security factor.


> You would need to invest an enormous amount of hashpower to create so many blocks that the difficulty adjustment could ratchet down

Thanks for the clarification. I don't know much about the difficulty adjustment algorithm of bitcoin so that's the point I was missing. So I guess there are some mechanisms like "the difficulty can only be adjusted every N blocks" and "the difficulty can only rise/sink by X%"?

If that's it and the deadline for when the key should be released is far enough in the future (e.g. 50 years?), it might still be feasible for an attacker to implement such an attack?

> simply by changing the witness proof to require blocks have a certain minimum hashpower on average

This assumes, bitcoin is an ever growing network and will never loose miners below a certain point. Depending on how long the key should be secret, this assumption might not hold true and I wouldn't depend on it.


> So I guess there are some mechanisms like "the difficulty can only be adjusted every N blocks" and "the difficulty can only rise/sink by X%"?

Yes. So you can manufacture your own blockchain, but you can't simply mint 1 block, declare difficulty just dropped 99.999%, and mint a bazillion more blocks after that. I never worked it out but you'd need to invest like months of current blockchain hashpower to make a pseudo-chain which would do nothing but unlock some timelocks (you can't even try to double-spend anyone, because their clients will follow the heavier chain, which will be the public one).

> If that's it and the deadline for when the key should be released is far enough in the future (e.g. 50 years?), it might still be feasible for an attacker to implement such an attack?...Depending on how long the key should be secret, this assumption might not hold true and I wouldn't depend on it.

Yes. This is an inherent feature of all work-based timelocks: the further out you go, the more uncertain things are. Rivest's timelock contest is a good demonstration of the empirical difficulties - the squaring timelock looked like it wasn't going to be unlocked on schedule until, out of nowhere, two different groups unlocked it with different approaches.

So, you decide what your tradeoff is. Do you want to make as sure as possible that it doesn't unlock early, because too early is catastrophic? Then you require a lot of hashpower and you set a very high minimum hash per block, at the risk of hashpower slowing down and your timelock taking much longer than you expected. Are you worried about it not being unlocked on time? Then you require relatively less hashpower and have looser constraints.

It's like PoW: how many transactions do you wait before deciding a transaction is 'real'? If you're in a hurry, maybe you use 0-conf; if you're an exchange transacting $1b in a single block, perhaps you'd better wait a few hundred blocks just to be absolutely certain.


It seems that bitcoin doesn't have limits in the difficulty adjustment, but I am pretty sure Monero does. If your black box checks these limits, that sets up a hard limit on how low you can get the difficulty. Which means that (over sufficiently short times) you'd still need a significant fraction of the publicly available hashing power to create such a forged chain.

As an alternative, you could set a limit of 'at least N blocks, and at least X accumulated difficulty'. This way any forks with reduced hashing power wouldn't reach the accumulated difficulty requirement.

Edit: I was wrong, bitcoin has a maximum difficulty factor of 4. So you could decrease the difficulty by 4 every 2 weeks.


This probably assumes you can't trick the program into connecting to the wrong bootstrap nodes.


But this means that there is a trusted party involved: the bootstrap nodes. Those might not exist anymore in the future. If they don't, the key cannot be released anymore? In my opinion something like this must not depend on the online status of some nodes.

I think, for the black box to be truly trust-less, it must be a `f: Blockchain -> Maybe DecryptionKey`. And then you can provide a specifically crafted blockchain to extract the key...


Such a program would certainly not be connecting to any network itself.



This is going to be a game changer when the first password manager implements a no third party time-lock as its recovery by trusted contact mechanism. Most of them just hold onto your password store public key encrypted for that contact, if they implement a trusted contact recovery at all.


Both time and location based encryption frequently appear as plot devices in fiction, but both are not really the subject of cryptography. At the core both of these simply require measurement of a physical quantity (position, time elapsed) to release some bits of information. This is something cryptography inherently can't do. You either end up changing the problem (unlocks not before X => unlocks after spending X amount of time computing) or relying on someone/somethey to proxy the measurement in a trustworthy manner to you (the blockchain-blackbox approach).

(You can't do "location based encryption" even if you bring your own trusted computing enviroment plus GNSS receiver, because GNSS emulators exist)


> location based encryption

Well, you can if the encryption key requires information that can only be collected from that location. The simplest example would be to put the encryption key on a piece of paper and tuck it under a rock. Now somebody has to reach that location in order to decrypt your message.

Time-based encryption is fundamentally different, since the sender can't travel into the future to lay unpredictable clues in advance.


This reminded me of dead drops: https://deaddrops.com/


> This is something cryptography inherently can't do. You either end up changing the problem (unlocks not before X => unlocks after spending X amount of time computing) or relying on someone/somethey to proxy the measurement in a trustworthy manner to you (the blockchain-blackbox approach).

If we were serious about timelocks, we'd just use trusted key-management services, i.e. the CAs. It would even be possible to use several, without placing total trust in any one of them.

Each CA would publish a huge set of public keys, each one associated with a date on which the corresponding private key will be published. We generate a symmetric crypto key, then encrypt our blob using it, then publish the resulting encrypted blob (withholding the key of course).

Now we 'split' the symmetric crypto key into c-many constituents (called shares), n-many of which are required to recover our symmetric crypto key, where c equals the number of CAs, and n is some number less than c, let's say, c/2. This is possible using Shamir's secret-sharing algorithm. [0]

Then we take the various CA's public keys for the desired date (so we have c-many public keys here). We encrypt each share with a different public key, and publish all the resulting encrypted shares. All this means that someone can only get our symmetric decryption key once n-many of the CAs have published their date-specific private-key.

The various CAs would not need to cooperate in any way for this scheme to work. Indeed, it would be ideal for the CAs to be highly diverse, minimally associated with each other, and in different countries.

Assumptions:

* We assume the crypto scheme that we originally used to encrypt the blob, doesn't get broken before the chosen date

* We assume the CAs don't all go bust, or lose the date-specific private keys, or otherwise fail to publish them at the proper date. We can adjust n to cope with some proportion of them failing.

* We assume the CAs can be trusted to ensure no premature release of date-specific private keys, whether deliberate or not. For this to be an issue, n-many of them would need to leak.

I think these assumptions are reasonable. The CAs are already making money on document-signing, to prove a document is no younger than claimed. I can't see a reason why there shouldn't already be a date-specific-key service like what I've described, but I don't know of any.

[0] https://en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing

[1] https://www.globalsign.com/en/digital-signatures/




Applications are open for YC Summer 2022

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: