Time-locked Puzzles & Dead Man's Switch Intervention

Question

I have been researching time-based puzzles. Specifically, computationally expensive algorithms for the purpose of a time-lock. This has lead me to sequential squaring, firstly, as well as some memory-hard approaches and of course trusted third parties. Creating a scheme that cannot be deciphered in N time, though not entirely trivial, is at least in theory doable. My question though is as this might relate to a dead man's switch.

Suppose we have Alice who wants to encrypt her message so that should N time pass without her intervention, Bob can decrypt it. What model of system could she come up with so that if she intervenes, perhaps complexity (Or something else that prevents decryption for more N) is added to the problem?

None of the approaches I've been reading about consider this possible scenario. In addition to accounting for time, how can we also account for periodic intervention, adding to N and/or difficulty?

Answer 1

Creating a function that can’t be solved in N time

Some assumptions need to be addressed to adequately answer this question; the first is to establish that there are different protocols provided a scenario with an honest/dishonest Bob. In a scenario where Bob only acts honestly the solution, to creating a function that can’t be solved in N time, is less of a cryptographic discussion and more of a software portability issue. In addition it will be assumed that all encryption and decryption methods are public information.

The definition of a dead man’s switch

Now I’ll assume that when you refer to a dead man’s switch you’re referring to a system that executes some task when there is the absence of user interaction, and that this particular system is implemented in software. Most non-mechanical dead man’s switches are limited by the reliability of the power source and energy storage, and thus become uninteresting.

Assuming a dishonest Bob

Now in this scenario we will assume that Bob will try to cheat and find a method to decipher the message in time less than N. Being able to decipher the message in time greater than N is of no particular interest or even an issue. So then the burden falls to Alice to prove that her particular decryption method is the fastest that exists, and to ensure that in the event that a faster method is discovered, that she is able to identify the cheating party. Furthermore Alice must ensure that her decryption system is sequential in so far as it can’t easily be run in parallel on a distributed computer network.

Discovering a cheating party is matter of recording the time stamp immediately after generating the message with expected decryption time of N, and by then calculating the time differential after the receipt of the decrypted message. Now assuming Alice has discovered a cheating party she must infer the capabilities of the attacker.

1. Did Bob discover a faster decryption method?

   Possible

2. Does Bob have more computational resources?

   Possible

3. Did Bob execute a pre-computation attack?

   Not Possible :)

In addition Alice must assume at all times there is the possibility of silent failure: Where Bob could have completed two of the previously mentioned attacks, decrypted the original message before there was any system intervention, and is sitting on the cryptographic equivalent of a dirty-bomb.

Alice’s system intervention

As I understand your question you’re interested in a system where Alice could actively manipulate the expected decryption time N. In which case Bob would need to be interacting with a system where Alice has read/write access. Bob would also need a method to know when decryption was successfully completed without knowing the required decryption time N, or the original message that was encrypted. Alice also would need a method for periodic intervention WITHOUT changing the original encrypted master secret.

This is based on the assumption that the dead man switch would be used to distribute a static master secret (MS). Alice encrypts a message (M) with expected decryption time X, and issues cipher (C) to Bob. At some point before the expected decryption time X Alice needs to change the decryption time X by Y. Now this is just a bad idea because it will be more complicated to predict the computational capabilities of Bob, which is pretty much the only point of this exercise….but I digress. Then Alice computes the new cipher (C’), and issues the new value to Bob. But as Daniel pointed out Bob could just as easily continue to decrypt the original cipher (C) to recover the original message (M) independently of the new cipher (C’). So it’s likely that the secret key would be some variable time value (T’) to recover a non-secret and non-random message (M’).

This would be the indicator message to relay to Bob that decryption was completed. Bob would then use the variable time value (T’) and attempt to decrypt some master secret (MS). If decryption was unsuccessful Bob would continue to decrypt the most recently distributed cipher (C’). The issue is that Alice could just as easily distribute the master secret (MS) without having to distribute all the false variable time (T’) secrets for decrypting the master secret (MS). The triggering system would remain unchanged, and thus there would be no reason for variable time (T’) values. As such all continued interaction between Alice and the dead man switch would serve only to distribute the master secret (MS).

Third Party

A system where the master secret (MS) is delivered to a trusted third party would be possible only when implemented in a completely mechanical system. Given the fallibility of humans and the inherent possibility of system compromise. The United States Postal Service would be the best delivery method.

tl;dr

This system will provide no fail-safe for Alice. If this is wrong please edit.