Time-Lock Puzzles (Send a Message to the Future)

1. Time-Lock Puzzles 简介（给未来发送消息）
2. Time-Lock Puzzles 算法
- 2.1. 两种方法的简单演示
- 2.2. 两种方法的时间对比
3. 生成未知阶的群（整数模 n 乘法群 $(Z / n Z)^{*}$ ）
4. LCS35 Cryptographic Challenge
5. Time-Lock Puzzles 和 VDF 的不同
6. 附录
- 6.1. 时间对比测试程序
- 6.2. Time-Lock Puzzles 实现

1. Time-Lock Puzzles 简介（给未来发送消息）

1996 年，R. L. Rivest, A. Shamir, and D. A. Wagner 在论文 Time-lock puzzles and timed-release crypto 中提出的 Time-lock puzzles，它解决的问题是： 如何加密一个消息，让这个消息不能马上被解密，甚至是消息的发送者也不能马上解密，必须经过一定时间后才能被解密？这相当于给未来发送消息。

2. Time-Lock Puzzles 算法

Alice 有消息 $M$ 想发给 Bob， Alice 使用 Time-lock puzzle 对它加密，让其在 $T$ 秒内谁也不能解密。Rivest 等在论文中给出的方案为：

Alice 随机选择两个素数 $p$ 和 $q$ ，计算： $\begin{aligned} n & = p q \\ ϕ (n) & = (p - 1) (q - 1) \end{aligned}$ 这个 $ϕ (n)$ 就是 Euler's totient function 。
Alice 计算 $t = T S$ ，其中 $S$ 是每秒钟 Bob 可以计算平方再求模的次数。
Alice 随机选择 $K$ 做为 RC5 加密算法（论文中是使用的 RC5，但它已经过时，换为 AES 即可）中的密钥。
Alice 使用密钥 $K$ 对消息 $M$ 进行加密，密文： $C_{M} = RC 5 (K, M)$
Alice 随机选择 $a$ 满足 $1 < a < n$ ，使用下面办法加密 $K$ ： $C_{K} = K + a^{2^{t}} (\mod n)$ 需要说明的是， $a^{2^{t}} (\mod n)$ 就是对 $a$ 进行连续 $t$ 次的平方再求模运算，由第 2 步可知，计算它需要 $T$ 秒钟。这太慢了，Alice 显然不能采用这样的方法来计算 $a^{2^{t}} (\mod n)$ ，Alice 采用下面技巧来快速计算 $\begin{aligned} e & = 2^{t} (\mod ϕ (n)) \\ b & = a^{e} (\mod n) \end{aligned}$ 这样得到的 $b$ 就是 $a^{2^{t}} (\mod n)$ ，但比直接算 $a^{2^{t}} (\mod n)$ 快很多。
Alice 把 $(n, a, t, C_{K}, C_{M})$ 发送给 Bob，Alice 删除所有其它变量，如 $p, q, ϕ (n)$ 等都会被 Alice 删除。

Bob 要解密密文 $C_{M}$ 的关键是求出加密密钥 $K$ ： $K = C_{K} - a^{2^{t}} (\mod n)$ 计算 $a^{2^{t}} (\mod n)$ 会消耗 $T$ 秒时间，由于 Bob 不知道 $ϕ (n)$ ，而且 Bob 也无法把 $n$ 分解为 $p, q$ 相乘（大整数分解是一个数学难题），所以 Bob 不能使用 Alice 使用的技巧来加快 $a^{2^{t}} (\mod n)$ 的计算。

2.1. 两种方法的简单演示

假设 $a = 5, t = 10, p = 7, q = 13$ 从而 $n = 7 \cdot 13 = 91, ϕ (n) = (7 - 1) \cdot (13 - 1) = 72$ ，Alice 计算 $a^{2^{t}} (\mod n)$ 的方法是：
$\begin{aligned} e & = 2^{t} (\mod ϕ (n)) = 16 \\ b & = a^{e} (\mod n) = 5^{16} (\mod 91) = 79 \end{aligned}$

Bob 计算 $a^{2^{t}} (\mod n)$ 的方法是对 $a$ 连续平方后求模，即：
$\begin{aligned} a^{2} (\mod n) & = 25, t = 1 \\ 25^{2} (\mod n) & = 79, t = 2 \\ 79^{2} (\mod n) & = 53, t = 3 \\ 53^{2} (\mod n) & = 79, t = 4 \\ 79^{2} (\mod n) & = 53, t = 5 \\ 53^{2} (\mod n) & = 79, t = 6 \\ 79^{2} (\mod n) & = 53, t = 7 \\ 53^{2} (\mod n) & = 79, t = 8 \\ 79^{2} (\mod n) & = 53, t = 9 \\ 53^{2} (\mod n) & = 79, t = 10 \end{aligned}$

这两种方法计算出来的 $a^{2^{t}} (\mod n)$ 都是 $79$ ，不过，这个例子的参数太小，这两种方法没有什么差别，下一节介绍的内容可以明显看到 Alice 方法的优点。

2.2. 两种方法的时间对比

节 2 中提到对某个数 $a$ 重复进行 $t$ 次平方后再求模有两种方法。

第一种是直接计算 $t$ 次平方求模（比较慢）： $a \to a^{2} \to a^{2^{2}} \to \dots \to a^{2^{t}} (\mod n)$ 第二种是利用 $ϕ (n)$ 加快计算： $\begin{aligned} e & = 2^{t} (\mod ϕ (n)) \\ b & = a^{e} (\mod n) \end{aligned}$

表 1 给出了计算 $a^{2^{t}} (\mod n)$ 的两种方法的时间对比， $p, q$ 采用的是 512 比特位的素数，完整测试程序在节 6.1 中有给出。从表中可行，Alice 的方法消耗的时间基本固定，而 Bob 的方法消耗的时间随着 $t$ 的增大而变长。

Table 1: 计算 $a^{2^{t}} (\mod n)$ 的两种方法的时间对比
t（计算平方求模的次数）	Bob 方法（直接计算）	Alice 方法（利用 $ϕ (n)$ 加快计算）
1000000	4.2795s	0.0051s
2000000	8.2409s	0.0050s
3000000	12.5669s	0.0052s
4000000	16.8149s	0.0051s
5000000	20.3919s	0.0049s
6000000	24.8932s	0.0055s
7000000	28.1989s	0.0049s
8000000	31.8169s	0.0052s

3. 生成未知阶的群（整数模 n 乘法群 $(Z / n Z)^{*}$ ）

不管 $a$ 和 $t$ 取什么值， $a \to a^{2} \to a^{2^{2}} \to \dots \to a^{2^{t}} (\mod n)$ 得到的结果是整数模 $n$ 乘法群 $(Z / n Z)^{*}$ 的元素。 $(Z / n Z)^{*}$ 由所有小于 $n$ 且和 $n$ 互素的数组成，它的阶（即群中元素个数）等于欧拉函数 $ϕ (n)$ 的值。如果我们不知道 $n$ 的两个素数因子 $p, q$ ，我们无法有效计算出群的阶 $ϕ (n) = (p - 1) (q - 1)$ 。

论文 Trustless unknown-order groups 中提到未知阶的群有一些应用：

VDF
Accumulator
Zero-knowledge proof

基于前面的知识，我们得到了一种生成未知阶的群的方法： 随机选择大素数 $p, q$ ，令 $n = p q$ ，则整数模 $n$ 乘法群 $(Z / n Z)^{*}$ 就是一个未知阶的群。 不过，这种方法有个 Trusted Setup 过程，也就是说生成 $(Z / n Z)^{*}$ 的人如果不主动丢弃 $p, q$ ，那么他就容易计算出群 $(Z / n Z)^{*}$ 的阶 $ϕ (n) = (p - 1) (q - 1)$ 。

有没有不需要 Trusted Setup 过程的生成未知阶的群的方法呢？有，使用虚二次域的类群（The class group of an imaginary quagratic number field），这里不介绍它。

4. LCS35 Cryptographic Challenge

论文 Time-lock puzzles and timed-release crypto 的作者 R.L. Rivest 在 1999 年为了庆祝 MIT Laboratory for Computer Science 35 周年，提出了一个密码学挑战，被称为 LCS35 挑战，内容是计算 $w = 2^{2^{t}} (\mod n)$ 其中 $t = 79685186856218$ ，而 $n$ 是一个 2048 位的合数（它是两个素数的乘积，但这两个素因子是保密的，没有给出），算出 $w$ 后，可以用它来解密密文 $z$ 。从节 2.2 中的例子可知，计算 $w$ 是一项非常耗时的工作，而如果知道 $n$ 的两个素因子，则 $w$ 可用其它方式来快速求得。

在 20 年后，也就是 2019 年，这个密码学挑战被程序员 Bernard Fabrot 解决了，密文对应的明文为 !!! Happy Birthday LCS !!! 。由于 LCS35 已经被解决，Rivest 提出了一个类似的新挑战，在新挑战中 $t$ 更大了 $t = 72057594037927936$ ，而 $n$ 也从 2048 位合数变为了 3072 位合数，这个挑战估计需要 35 年来解决（即在 2034 年前解决）。

参考：
http://people.csail.mit.edu/rivest/lcs35-puzzle-description.txt
http://people.csail.mit.edu/rivest/pubs/Riv19f.new-puzzle.txt

5. Time-Lock Puzzles 和 VDF 的不同

Time-Lock Puzzles 和 Verifiable Delay Functions (VDF) 很像，VDF 的作者在论文 Verifiable Delay Functions 中总结了这两者的不同：

However, time-lock puzzles are not required to be universally verifiable and in all known constructions the verifier uses its secret state to prepare each puzzle and verify the results. VDFs, by contrast, may require an initial trusted setup but then must be usable on any randomly chosen input.

也就是说，Time-Lock Puzzles 并不是公开可验证的，只有知道秘密 $ϕ (n)$ 的人可以快速验证。

6. 附录

6.1. 时间对比测试程序

下面是一个测试程序，用于对比 $a^{2^{t}} (\mod n)$ 的两种计算方法的消耗时间：

#!/usr/bin/env python3
import time

# p, q are 512-bit primes
p = 8209077225464744046058125532749278512291234171215833952402836353080077624707567078652583737734960250522321797259257834136264573912281335421318629812420243
q = 10210866123026220402608723719512990963703414195418793555009957005900602373762304023225762792476205121987889212846523815929308691506724521213557799758686351
n = p*q
phi = (p-1)*(q-1)
a = 26709222073426371386944893319563814873828437081287914883853479639285555080105905753122291117627967664722212372127789775600885451856023491770260498070851477043567765086507488412082645344266097153356496584378260820598850038246370721277496827950170445707849823419867264814314535998513443626070856504384463494482

t_tests = [1000000, 2000000, 3000000, 4000000, 5000000, 6000000, 7000000, 8000000]  # t 分别取这些值进行测试
for t in t_tests:
    t1 = time.time()
    result1 = a
    times = t
    while times != 0:
        result1 = result1 * result1 % n   # 第一种方法，直接计算。这里有 t 次平方后再求模的运算。整个 while 循环可写为 result1 = pow(a, 2**t, n)，计算时间差不多
        times = times - 1
    t2 = time.time()
    print("method 1, t = {}, time = {}".format(t, t2 - t1))

    t1 = time.time()
    e = pow(2, t, phi)                    # 第二种方法，利用 Euler's totient function 加快计算
    result2 = pow(a, e, n)
    t2 = time.time()
    print("method 2, t = {}, time = {}".format(t, t2 - t1))

    assert result1 == result2

下面是在 2.2 GHz Intel Core i7 Processor 下的一个运行结果：

method 1, t = 1000000, time = 4.279543161392212
method 2, t = 1000000, time = 0.005108833312988281
method 1, t = 2000000, time = 8.240965127944946
method 2, t = 2000000, time = 0.005007743835449219
method 1, t = 3000000, time = 12.566895961761475
method 2, t = 3000000, time = 0.005189180374145508
method 1, t = 4000000, time = 16.81494688987732
method 2, t = 4000000, time = 0.0051081180572509766
method 1, t = 5000000, time = 20.39188504219055
method 2, t = 5000000, time = 0.004948139190673828
method 1, t = 6000000, time = 24.893248796463013
method 2, t = 6000000, time = 0.00545501708984375
method 1, t = 7000000, time = 28.19888401031494
method 2, t = 7000000, time = 0.004888057708740234
method 1, t = 8000000, time = 31.816866159439087
method 2, t = 8000000, time = 0.005177736282348633

6.2. Time-Lock Puzzles 实现

下面是 Time-Lock Puzzles 的一个实现：

#!/usr/bin/python

# This code was taken from:
# http://de.scribd.com/doc/32307363/Anti-Emulation-through-TimeLock-puzzles / Appendix A (at the very end)
# All rights to their respective owners
# Requires Python Cryptography Toolkit
# http://www.amk.ca/python/code/crypto.html
import time

from Crypto.Util import number


def make_puzzle(t):
    # Generate 512-bit primes
    p = number.getPrime(512)
    q = number.getPrime(512)

    n = p * q
    phi = (p - 1) * (q - 1)

    # AES key --- this is what we will encode into the puzzle solution
    key = number.getRandomInteger(128)

    # Need a random starting value for the puzzle, between 1 and n
    a = number.getRandomInteger(4096)
    a = a % n

    # *** puzzle shortcut ***
    # fast way to compute (a^2)^t (if you know phi)
    e = pow(2, t, phi)
    b = pow(a, e, n)
    # print("phi = {}, e = {}, p = {}, q = {}".format(phi, e, p, q))

    # So b = (a^2)^t, and we encode the key into this solution
    ck = (key + b) % n

    return key, n, a, t, ck


def solve_puzzle(n, a, t, ck):
    print("Working")
    while t != 0:  # This while loop is equivalent to: a = pow(a, 2**t, n)
        a = a * a % n
        t = t - 1
    return (ck - a) % n


def main():
    # Generate a new puzzle requiting 3000000 modular squarings to solve
    t = 3000000
    (key, n, a, t, ck) = make_puzzle(t)

    # Use this key to encrypt a payload
    print("key = " + str(key))

    print("puzzle (n = {}, a = {}, t = {}, ck = {})".format(n, a, t, ck))

    # Recover the key
    t1 = time.time()
    solution = solve_puzzle(n, a, t, ck)
    t2 = time.time()
    print("solve_puzzle time =", t2 - t1)
    print("solution = " + str(solution))


if __name__ == "__main__":
    main()

代码改编于：Anti-Emulation Through TimeLock Puzzles, by Tim Ebringer