Time-lock puzzle

最近工作上事情比较少，摸鱼的时候看了很多有意思的东西，找 VDF 相关资料的时候讲到一个问题：如何设计一个只能在指定的时间 $T$ 后才能解出来的 puzzle 我先想了一下但是没想明白，怎么把时间这种抽象的概念在一个 puzzle 里面给量化出来。🤔

然后就翻到了这篇引用的论文 Time-lock puzzles and timed-release Crypto

看了文章才发现实际上这个问题可以等效于：设计一个算法，只有在经过 $P$ 次计算后才能够得到正确的结果，且这个算法的计算过程不能被并行计算加速。这样只能使用一台机器解密，假设其每秒最高算力为 $S$ 则一定要经过 $T = P / S$ 秒后才能解出正确的结果，达到了 time-lock 的目的。

文章里介绍了两种 time-lock puzzle 的实现方式。

第一种 time-lock puzzle 设计#

假设 Alice 有一个信息 $M$ 要传递给 Bob 但是需要加密 (锁定) $T$ 秒钟的时间。(这里有一个前提是 Alice 需要事先知道 Bob 的算力情况)

加密#

第一步，随机选择两个大质数 $p$ 和 $q$ 将他们相乘得到 $n = p*q$ 同时计算 $\phi(n) = (p-1)*(q-1)$

第二步，计算 $t = T*S$ 其中 $S$ 是 Bob 单机每秒能够进行的对 $n$ 平方取模的次数 (也就是所谓算力)

第三步，随机生成一个足够安全的，用于加密的密钥 $K$ 和一个加密算法比如 RC5

第四步，使用密钥和加密算法加原始信息得到 $C_m = RC5(K, M)$

第五步，选择一个随机数 $a\ (1 < a < n)$ 然后加密 $K$ 得到 $C_k = a^{2^{t}}\ (mod\ n)$

这一步可以通过以下步骤进行加速：首先计算 $e = 2^{t}\ (mod\ \phi(n) )$ 然后计算 $b = a^{e}\ (mod\ n)$

最后 Alice 将 $(n, a, t, C_k, C_m)$ 公布给 Bob

解密#

对于 Bob 来说获取 $M$ 需要用密钥 $K$ 解密 $C_m$ 但是加密时已经保证 $K$ 本身是足够安全的 Bob 只能通过 $C_k$ 计算得到 $K = C_k - a^{2^{t}}\ (mod\ n)$

这里只剩下 $t$ 一个未知数，对于 Bob 来说除了暴力遍历所有 $t$ 没有其他更好的办法。

这样则需要经过 $a^{2}, a^{4}, a^{8},a^{16},...a^{x} (t = 1,2,3,...)$ 这样一个序列的计算，可以观察到在这个序列里，每一项的计算都依赖前一项的计算结果 $a^{4} = (a^{2})^{2}, a^{8} = (a^{4})^{2}, ...$ 即无法提前计算后面的值，也不能并行加速计算。只能通过 $t$ 次计算得到结果，而根据之前设定的 $t = T*S$ 所需要计算的时间就是 $T = t/S$ 也即达了 Alice 将消息锁定 $T$ 时间的目的。

（至于 Bob 如何判断自己找到了正确的 $K$ 就不属于这个算法里面的问题了。一种方式是加密者可以给出 $sha256(K)$ 让 Bob 自己校验。）

第二种 time-lock puzzle 设计#

第二部分没仔细看，直接在 Claude2 上面上传论文让后让 AI 帮忙总结的 (没有 GPT-4 可以用的情况下非常推荐用 Claude2)

ME: 介绍下第二种方法如何实现

文章提出的第二种使用受信任代理的方法大致如下:

设置多个受信任的代理，每个代理定期公布一个密钥。

用户将消息用一个随机密钥加密，得到密文。

用户将该随机密钥通过密钥分享方案分成多个份，分别给不同的代理。

每个代理使用在未来时间 t 公布的密钥，加密自己持有的那一份子密钥。

在时间 t, 足够多的代理公布了他们在 t 时刻的密钥。

用户可以用这些密钥解密出子密钥份，然后重构出原始的随机密钥。

最后用这个随机密钥解密出原始消息。

这种方法的安全性依赖于受信任代理不提前泄露未来的密钥。同时设置多个代理，可以通过密钥分享和阈值检验来实现一定的容错性。即使个别代理被攻破或失效，只要有足够的代理仍正常工作，信息仍能在预定时间解密出来。