重新审视链式时间锁谜题及改进框架

《Information and Computation》：Revisiting chained time lock puzzle and a framework for improvement

　　

## 摘要

时间锁谜题（TLP）是一种密码学原语，旨在确保即使攻击者拥有大量计算资源，秘密在预定时间之前仍然无法被访问。这些谜题在各种应用中发挥着至关重要的作用，从增强去中心化系统的安全性到实现区块链技术中的公平协议。链式时间锁谜题（C-TLP）是TLP的扩展，将多个时间锁谜题按顺序链接，在最终秘密被解锁之前强制实施一系列时间延迟。2025年，Kumar和Padhye提出了一种基于整数分解问题（IFP）的C-TLP。他们采用了Abadi和Kiayias的设计，并提出了谜题大小更小的C-TLP。在本文中，我们证明Kumar和Padhye的方案在语义上不安全，并提出了一种改进方案，该方案具有语义安全性，且与Abadi和Kiayias的C-TLP相比，密钥和谜题大小更小。

## 引言

时间锁谜题是一种加密工具，即使采用并行计算，其解密也需要可预测的时间。它们在电子投票、公平合同签署和密封投标拍卖中有用[1][2]。这一概念最早由T.C. May于1993年提出[3]。在这种特殊的加密方式中，原始消息被锁定一段时间（比如说u小时），当解密过程开始时，计算机需要运行解密算法u小时才能成功取回原始消息。如果CPU时间与真实时间一致，消息将在确切的时间被解密。

May[3]早期的工作介绍了一种依赖可信第三方的TLP。1996年，Rivest等人[2]提出了基于顺序模幂运算（SMS）的无可信代理TLP，其安全性取决于IFP的计算困难性。Boneh[4]和Garay[5]的后续研究探索了时间承诺方案，引入了零知识证明来让求解者在开始计算前确认谜题的正确性。然而，这些证明的开销使其效率低于Rivest基于SMS的方法[2]。Chvojka等人[6]随后设计了一种使用公钥加密而非对称密钥方案的TLP。Brakerski[7]和Malavolta[8]通过同态TLP进一步扩展了这一领域，能够在未解决的谜题上进行任意计算。他们的设计将SMS与全同态加密相结合，但代价是显著的计算开销。

以上讨论的所有时间锁谜题都是单实例谜题。然而，在各种场景中需要将多个实例用于在不同时间段锁定消息。这些情况可能出现在敏感文档的批量定时发布、多个密钥的顺序揭示、计划私密支付等。在这些情况下直接使用单实例TLP需要非常高的计算开销和大量并行计算资源。为克服这些问题，Abadi等人[9]和Chvojka等人[10]于2021年提出了链式时间锁谜题（C-TLP）。方案[10]的效率低于方案[9]。此外，2025年，Kumar和Padhye[11]采用了Abadi等人[9]的设计，并提出了另一种谜题大小小于[9]的C-TLP。在方案[9]中，使用私钥和随机数序列为一组r个消息生成谜题。在谜题生成中使用了两种随机序列。第一个序列用于在每次迭代中生成对称加密密钥的掩码，第二个序列用于提交消息序列。这些随机序列是私钥的一部分，因此方案[9]的私钥大小相当大。此外，方案[9]的谜题大小也很大，因为谜题的每次迭代都通过对称加密加密与随机数连接的消息。因此，密文大小也以同样的方式增大。为克服方案[9]的谜题大小问题，作者[11]消除了生成对称加密密钥掩码的一个随机序列，并使用消息序列本身来计算掩码。消除一个随机序列减少了方案[11]的谜题大小。

在本文中，我们证明方案[11]由于其确定性特征在语义上不安全。C-TLP的这种特征使得如果攻击者预测了链中的某个消息（由于低熵或标准格式），他可以提前解密密文链。在减少Abadi等人[9]的C-TLP大小时，作者[11]忽略了[9]中使用的随机值，这导致了方案中语义安全性的破坏。最后，我们提出了一种解决方案，在保持C-TLP语义安全性的同时减少了谜题大小。

## 部分片段

### 预备知识

在本节中，我们讨论审视方案[11]安全性和提出安全高效解决方案所需的所有基本定义。

**定义1：整数分解问题（IFP）**

IFP[12]是数论和现代密码学中的基础性挑战，定义为将正合数分解为其唯一质因子的任务。虽然两个质数的乘法计算上很简单，但对于足够大的合数找到这些因子的逆运算被认为是计算上困难的。

### Kumar和Padhye的C-TLP

设 $\bar{m} = (m_1, m_2, \ldots, m_r)$ 为长度为r的消息序列，将在时间序列 $(T_1, T_2, \ldots, T_r)$ 时被公开。谜题在初始时间 $T_0$ 发布，为简化计算，我们使用 $T = T_i - T_{i-1}, \forall i = 1, 2, \ldots, r$。设置 $t = S \cdot T$，其中S已定义为每秒可计算的最大模N平方次数。基于这些假设，Kumar和Padhye[11]的C-TLP可以如下讨论。

1. **CSetup(1λ, △, r)。**
(i) 首先执行算法 Setup(1λ, △)。

### Kumar和Padhye C-TLP的缺陷

在方案[11]中，作者声称其C-TLP的谜题大小小于Abadi和Kiayias[9]的C-TLP。为便于理解，我们展示方案[9]的CGenPuz算法如下。我们可以注意到，在谜题向量 $\bar{y} = (y_1, y_2, \ldots, y_r)$ 中，每个 $y_i$ 是一个有序对 $(c1_i, c2_i)$。组件 $c1_i$ 是方案[11]中消息 $m_i$ 的加密，而同一组件 $c1_i$（除 $c1_r$ 外）在方案[9]中是 $(m_i \| d_i \| l_{i+1})$ 的加密。其中，$d_i$ 是……

### 提出的解决方案

在本节中，我们提供了一种使方案[11]语义安全且抗解密失败的解决方案，同时保持最小的密钥和谜题大小。修改后的C-TLP（MC-TLP）可以如下讨论。

1. **MCSetup(1λ, △, r)。**
(i) 首先执行算法 Setup(1λ, △)，获得初始密钥对 $pk' = (N, t, x)$ 和 $sk' = (k_1, p, q, z)$。
(ii) 运行KeyGen算法 $r-1$ 次以构建 $r-1$ 个对称加密密钥 $k_2, k_3, \ldots, k_r$。
(iii) 最后，公钥设置为 $pk = (N, t, x)$，私钥……

### 安全性分析

我们在第4节中讨论了方案[11]的三个缺陷：$c2_i$ 的确定性特征、C-TLP的语义安全性和解密失败。所提出的修改如下解决了所有这些问题。

1. 可以看到，$v_1$ 是使用随机值 $x$ 计算的，因此 $v_1$ 是随机分布的。$v_2$ 的值取决于 $v_1$，因此 $v_2$ 也是随机分布的。类似地，所有的 $v_i$ 都是随机分布的。因此，所有的 $c2_i$ 都是随机分布的，所以提前预测……

### 比较分析

除安全设计外，所提出的修改方案与现有方案[9]相比还具有更小的密钥和谜题大小。由于注意到方案[11]中的缺陷，我们将我们的方案与方案[9]进行了比较，针对100条消息的链（每条128位长度）见表1。在计算中，我们取了以下大小的参数：N、x、p、q、z的大小为1024位，每个 $k_i$ 的大小为128位（AES[14]密钥大小）。

我们可以看到私钥的大小和 $c1_i$ 的大小……

### 结论

我们对Kumar和Padhye的C-TLP进行了密码分析，并证明他们的方案在语义上不安全。更具体地说，如果攻击者预测了消息序列中的任何特定消息，它可以被提前解密。然后，我们提出了C-TLP的修改设计，该设计在语义上安全，且与现有的C-TLP相比，密钥和谜题大小显著减小。

### 道德标准合规性

所有作者声明他们没有利益冲突。

**道德批准：** 本文不包含任何作者进行的人类参与者或动物的研究。

**利益冲突声明**

作者声明他们没有已知的竞争性经济利益或个人关系可能会影响本文报告的工作。

Satyam Omar