给未来写信——时间胶囊技术（二）

一、问题的提出

时间胶囊最初由May[1]提出，在上文《给未来写信——时间胶囊技术（一）》中，我们介绍了基于hash迭代的时间胶囊。然而，基于hash迭代的时间胶囊，如果发送方希望接收方花多长时间解密，则自己也必须花多长时间来加密，这在实际应用中显然不合适。

二、基于时间锁谜题的时间胶囊

Rivest等人[2]提出了使用“时间锁谜题”来实现时间胶囊的方法。

假设消息发送方有待发送的明文消息m，其可以进行如下操作：

（1）类似于RSA密钥生成方法，选择大素数p和q，计算n=p*q；

（2）计算:

（公式1）

（公式2）

将（公式2）迭代计算T次（这里假设计算T次所需时间就是预设时间，T的大 小可根据需要调整）即得：

（公式3）

（3）计算消息密文为明文与上述结果的异或：

（公式4）

（4）消息发送方将(n,T，c)发送给接收方，并销毁p,q和。接收方收到(n,T，c)以后，按照公式1-3计算出，然后就可以计算密文c与的异或即得明文：

(公式5）

按此方法，接收方计算的时间与T成正比，且只能是串行计算。到这里，我们发现，消息发送方和接收方的计算量几乎是一样的，这与前面的hash迭代运算又有什么区别呢？事实上，由于发送方有关于p和q的信息，其不用照（公式2）那样计算T次，其有更为快速的方法计算出。设

(公式6）

我们知道，由欧拉定理，有：

（公式7）

其中，a为任何不等于p和q且小于n的正整数。 于是，消息发送方仅需通过如下2步计算，就可快速得到：(2)* 计算：

（公式8）

（公式9）

注：（公式8）和（公式9）的关系成立，是因为由（公式8）可知存在某个x使得下式成立：

（公式10）

于是

（公式11）

由上述分析可知，发送方掌握了p和q的信息，其可以很容易的走“捷径”计算出密文，形象地表示如图1所示。而接收方，必须依照（公式2）按部就班地进行T次平方取模运算，形象地表示如图2所示，T的大小决定了接收方解密所需时间的长短。

图1 发送方加密走“捷径”，所需计算量小

图2 接收方无捷径可走，所需计算量大

因此，基于时间锁谜题的时间胶囊可以实现：1. 加密所需时间很短；2.解密所需时间（对应的计算量）由加密时设定。其较好的满足了时间胶囊的基本要求。

三、时间胶囊应用

3.1遗嘱

例如，某人可能会提前立下遗嘱，而不愿意过早地暴露其遗嘱内容，担心会引起纠纷。

图3 遗嘱托管 （图片来自网络）

3.2投标

通常情况下，投标要求，一是必须在指定时间前提交投标，二是必须在指定时间后才公布投标内容。这中间会有一个时间差。现场投标可以通过物理检查的方法实现上述要求。但是电子投标的情况下，如果没有合适的安全措施，也许你的投标，会被人提前打开而泄露给你的竞争对手。通过时间胶囊，可以实现除加密者自己外没有人能够提前打开投标信息（如报价）。

3.3 电子投票/选举

与投标类似，通常要求在特定的时间之前投出选票，但是不希望任何人在唱票之前获悉投票的内容。

图4 投票 （图片来自网络）

其他应用还有抵押延迟支付、密钥托管等等。

除上述应用外，时间胶囊的思想还可以用于其他的一些密码学领域，如结合不经意传输（oblivious transfer）协议提高不经意传输的灵活性[3]。时间锁谜题也可以用于构造可验证延迟函数VDF，这是一种在区块链、博彩等领域具有广泛应用的延迟函数[4]。

四、时间胶囊的进一步发展

4.1存在的问题

上述时间锁定方案简单易懂易实现，适合非专业人士理解，却也还存在实用性差等一些问题，例如：

（1）不能匿名（如无记名投票需要匿名性）；

（2）解密需要大量的计算；

（3）接收方需要及时启动计算，否则不能在预定时间完成解密；

（4）设计时难以较为准确地估计敌手的计算能力，尤其是未来的计算能力。

关于延迟时间的设计，对于较为短期的，可以较为精确，对于时间较长的设计，由于对技术发展的预测可能与实际的发生之间存在偏差，则实际解密的时间可能与设计存在差异。例如，1999年，Rivest [5-6]给出了一个公开的时间锁加密挑战，其最初设计的目标是使得该挑战要经过35年才能被解密。而在挑战公开刚好20年后即2019被破解，其中一个破解者（个人）从2016年初开始，采用基于软件的方法，花了3年零三个月的时间，另一组破解者（团队）则通过FPGA的方法，花了2个月的时间破解。Rivest承认，在设计之初，未考虑到FPGA发展如此之快。2019年，Rivest又给出了一个新的挑战[7],感兴趣的可以尝试破解。

针对上述缺点，学术界提出了一些新的更先进更实用的方法，如采用基于时间服务器的方法[8]、基于身份的方法[9]等。感兴趣的读者可以进一步阅读相关文献。

4.2 结合存证更具应用潜力

前面讲到的投标和遗嘱等问题，都需要有相应的时间证明，比如，要求在某个时间点之前提交标书。而对于遗嘱，由于立遗嘱的人可能会修改遗嘱，当出现两份不一致的遗嘱时，需要以最新的遗嘱为准。这些都需要提供时间证明。因此，时间胶囊与存在性证明相结合是必然的。区块链天生就是个良好的无中心/无需可信第三方的存证平台，结合区块链的时间胶囊必定更具应用潜力，学界也提出了一些算法，例如[10-13]，建议进一步阅读。

参考文献

[1],May, T.C.: Timed-release crypto (1993),http://cypherpunks.venona.com/date/

1993/02/msg00129.html.

[2] Rivest, R.L., Shamir, A.,Wagner, D.A.:Time-lock puzzles and timed-release crypto. Massachusetts Institute ofTechnology (1996).

[3] Ma Xu, Xu Lingling, Zhang Fangguo.Oblivious transfer with timed-release receiver's privacy. Joumal of Systems andSoftware， 2011, 84(3): 460-464.

[4] Krzysztof Pietrzak, Simple VerifiableDelay Functions, https://eprint.iacr.org/2018/627.pdf.

[5] https://people.csail.mit.edu/rivest/lcs35-puzzle-description.txt,访问时间：2021.08

[6] Lcs35 https://github.com/supranational/lcs35，访问时间：2021.08

[7] Rivest, R.L., Description of theCSAIL2019 Time Capsule Crypto-Puzzle， https://people.csail.mit.edu/rivest/pubs/Riv19f.new-puzzle.pdf， 访问时间：2021.08

[8] Ian F. Blake and Aldar C-F. Chan，Scalable, Server-Passive, User-Anonymous Timed Release PublicKey Encryption from Bilinear Pairing， https://eprint.iacr.org/2004/211，访问时间：2021.08

内容编辑：创新中心 李德全 责任编辑：王星凯

本公众号原创文章仅代表作者观点，不代表绿盟科技立场。所有原创内容版权均属绿盟科技研究通讯。未经授权，严禁任何媒体以及微信公众号复制、转载、摘编或以其他方式使用，转载须注明来自绿盟科技研究通讯并附上本文链接。

关于我们

绿盟科技研究通讯由绿盟科技创新中心负责运营，绿盟科技创新中心是绿盟科技的前沿技术研究部门。包括云安全实验室、安全大数据分析实验室和物联网安全实验室。团队成员由来自清华、北大、哈工大、中科院、北邮等多所重点院校的博士和硕士组成。

绿盟科技创新中心作为“中关村科技园区海淀园博士后工作站分站”的重要培养单位之一，与清华大学进行博士后联合培养，科研成果已涵盖各类国家课题项目、国家专利、国家标准、高水平学术论文、出版专业书籍等。

我们持续探索信息安全领域的前沿学术方向，从实践出发，结合公司资源和先进技术，实现概念级的原型系统，进而交付产品线孵化产品并创造巨大的经济价值。