Time-lock puzzle

Recently, there have been fewer tasks at work, and while I was slacking off, I came across many interesting things. When looking for VDF-related materials, I encountered a question: how to design a puzzle that can only be solved after a specified time $T$ has passed. I thought about it for a moment but couldn't figure out how to quantify the abstract concept of time within a puzzle. 🤔

Then I stumbled upon this referenced paper Time-lock puzzles and timed-release Crypto.

After reading the article, I realized that this problem can actually be equated to: designing an algorithm that can only produce the correct result after $P$ computations, and the computation process of this algorithm cannot be accelerated by parallel computing. This means that only one machine can decrypt it, and assuming its maximum computing power is $S$ per second, it must take $T = P / S$ seconds to obtain the correct result, achieving the purpose of a time-lock.

The article introduces two implementations of time-lock puzzles.

First Design of Time-lock Puzzle#

Assume Alice has a message $M$ to send to Bob, but it needs to be encrypted (locked) for $T$ seconds. (There is a premise that Alice needs to know Bob's computing power in advance.)

Encryption#

First, randomly select two large prime numbers $p$ and $q$ and multiply them to get $n = p*q$ while calculating $\phi(n) = (p-1)*(q-1)$ .

Second, calculate $t = T*S$ where $S$ is the number of times Bob can perform modular exponentiation of $n$ per second (which is the so-called computing power).

Third, randomly generate a sufficiently secure key $K$ for encryption and an encryption algorithm like RC5.

Fourth, use the key and encryption algorithm on the original message to get $C_m = RC5(K, M)$ .

Fifth, choose a random number $a\ (1 < a < n)$ and then encrypt $K$ to get $C_k = a^{2^{t}}\ (mod\ n)$ .

This step can be accelerated by the following steps: first calculate $e = 2^{t}\ (mod\ \phi(n) )$ then calculate $b = a^{e}\ (mod\ n)$ .

Finally, Alice publishes $(n, a, t, C_k, C_m)$ to Bob.

Decryption#

For Bob to obtain $M$ , he needs to decrypt $C_m$ using the key $K$ , but it has already been ensured that $K$ itself is sufficiently secure. Bob can only calculate $K = C_k - a^{2^{t}}\ (mod\ n)$ from $C_k$ .

At this point, only $t$ remains an unknown. For Bob, there is no better way than to brute-force through all $t$ values.

This requires computing a sequence of $a^{2}, a^{4}, a^{8}, a^{16},...a^{x} (t = 1,2,3,...)$ . It can be observed that each term in this sequence depends on the result of the previous term $a^{4} = (a^{2})^{2}, a^{8} = (a^{4})^{2}, ...$ which means that later values cannot be computed in advance, nor can the computation be accelerated in parallel. The result can only be obtained through $t$ computations, and according to the previously set $t = T*S$ , the time required for computation is $T = t/S$ , thus achieving Alice's goal of locking the message for $T$ seconds.

(As for how Bob determines that he has found the correct $K$ , that is not a problem within this algorithm. One way is for the encryptor to provide $sha256(K)$ for Bob to verify himself.)

Second Design of Time-lock Puzzle#

I didn't look closely at the second part; I directly uploaded the paper to Claude2 and asked the AI to summarize it (I highly recommend using Claude2 when GPT-4 is not available).

ME: Introduce how the second method is implemented.

The second method proposed in the article using trusted agents is roughly as follows:

Set up multiple trusted agents, each of whom periodically publishes a key.

The user encrypts the message with a random key to obtain the ciphertext.

The user splits the random key into multiple shares using a key-sharing scheme and gives them to different agents.

Each agent encrypts their share of the sub-key using the key that will be published at a future time t.

At time t, enough agents publish their keys from that moment.

The user can use these keys to decrypt the sub-key shares and then reconstruct the original random key.

Finally, use this random key to decrypt the original message.

The security of this method relies on trusted agents not leaking future keys in advance. By setting up multiple agents, it can achieve a certain level of fault tolerance through key sharing and threshold verification. Even if individual agents are compromised or fail, as long as enough agents are still functioning normally, the information can still be decrypted at the scheduled time.