Time-lock puzzle

Recently, there have been fewer things to do at work, so I have been browsing interesting things while slacking off. When I was looking for VDF-related information, I came across a question: how to design a puzzle that can only be solved after a specified time $T$ ? I thought about it for a while but couldn't figure out how to quantify the abstract concept of time in a puzzle. 🤔

Then I came across this referenced paper Time-lock puzzles and timed-release Crypto.

After reading the article, I realized that this problem can actually be equivalent to designing an algorithm that can only produce the correct result after $P$ calculations, and the calculation process of this algorithm cannot be accelerated by parallel computing. This means that only one machine can be used for decryption. Assuming its maximum computing power per second is $S$ , it will take $T = P / S$ seconds to obtain the correct result, achieving the goal of time-lock.

The article introduces two implementations of time-lock puzzles.

Design of the first type of time-lock puzzle#

Assuming Alice has a message $M$ to be transmitted to Bob, but it needs to be encrypted (locked) for $T$ seconds. (Here, one prerequisite is that Alice needs to know Bob's computing power in advance)

Encryption#

Step 1: Randomly select two large prime numbers $p$ and $q$ , and multiply them to get $n = p*q$ . At the same time, calculate $\phi(n) = (p-1)*(q-1)$ .

Step 2: Calculate $t = T*S$ , where $S$ is the number of times Bob's single machine can perform modular exponentiation of $n$ per second (also known as computing power).

Step 3: Randomly generate a sufficiently secure key $K$ for encryption, and an encryption algorithm such as RC5.

Step 4: Use the key and encryption algorithm to encrypt the original message to obtain $C_m = RC5(K, M)$ .

Step 5: Choose a random number $a\ (1 < a < n)$ and encrypt $K$ to obtain $C_k = a^{2^{t}}\ (mod\ n)$ .

This step can be accelerated through the following steps: first calculate $e = 2^{t}\ (mod\ \phi(n) )$ , and 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$ . However, during encryption, it has been ensured that $K$ itself is sufficiently secure. Bob can only calculate $K = C_k - a^{2^{t}}\ (mod\ n)$ using $C_k$ .

At this point, only $t$ remains as an unknown variable. For Bob, there is no better way to find the correct $K$ other than brute-forcing all possible values of $t$ .

Thus, it is necessary to perform calculations for a sequence of $a^{2}, a^{4}, a^{8},a^{16},...a^{x} (t = 1,2,3,...)$ . It can be observed that in this sequence, each calculation depends on the previous calculation result $a^{4} = (a^{2})^{2}, a^{8} = (a^{4})^{2}, ...$ . This means that the values of the later terms cannot be calculated in advance, and the calculation cannot be accelerated in parallel. The result can only be obtained through $t$ calculations. According to the previously set $t = T*S$ , the required calculation time is $T = t/S$ , which achieves Alice's goal of locking the message for $T$ time.

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

Design of the second type of time-lock puzzle#

I didn't read the second part carefully. I directly uploaded the paper to Claude2 and asked AI to summarize it for me (highly recommended to use Claude2 when GPT-4 is not available).

ME: Please introduce the second method.

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

Set multiple trusted proxies, each proxy regularly publishes a key.

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

The user divides this random key into multiple parts using a key sharing scheme and gives each part to a different proxy.

Each proxy encrypts the part of the key they hold using the key published at time t in the future.

At time t, a sufficient number of proxies have published their keys at that time.

The user can decrypt the parts of the key using these keys and reconstruct the original random key.

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

The security of this method depends on the trusted proxies not leaking future keys in advance. At the same time, setting multiple proxies can achieve a certain degree of fault tolerance through key sharing and threshold verification. Even if individual proxies are compromised or fail, as long as there are enough proxies still functioning properly, the information can still be decrypted at the predetermined time.