短时间锁谜题及其对自适应选择解与谜题攻击的安全性

《Information and Computation》：Short time-lock puzzles with security against adaptive chosen-solution-and-puzzle attacks

　　

**摘要**

时间锁谜题（TLPs）通过要求在消息可访问之前经过特定时长，实现了将消息"发送至未来"的功能。其应用领域广泛，例如电子投票、密封出价拍卖和公平多方计算等。然而，现有的时间锁谜题方案存在一些缺陷，如高通信开销、过多的计算资源消耗或安全性较弱等。为克服这些缺点，我们在一个强安全模型下提出了一种高效的时间锁谜题方案，其中每个谜题仅包含RSA群中的单个元素。我们的方案能够抵抗同时拥有谜题生成预言机和谜题求解预言机的对手，实现了语义安全性和隐式认证。此外，我们引入了时间锁谜题的一种新变体，称为"密钥可恢复时间锁谜题"（KR-TLPs），并给出了具体构造，该变体具有"解一个，免费得多个"的特性，即任何知道谜题生成密钥的人都能在时间T之后批量求解谜题。此外，我们为两种方案提供了可验证性协议，确保运行可靠性，同时消除谜题求解过程中的冗余计算开销。

**引言**

时间锁谜题（TLPs）是定时发布密码学中的基本原语，旨在"为未来加密"，最早由Rivest、Shamir和Wagner[1]提出。在时间锁谜题方案中，消息被封装在谜题中，谜题可以快速生成，且无需密钥即可被缓慢求解。时间锁谜题的核心构建模块是一个连续的、不可并行的任务，其原始且最广泛使用的例子是在RSA群中进行顺序平方运算，该例子在[1]中提出。具体而言，要计算$x^{2^T} \mod N$，其中$N=pq$是RSA模数，$x \in \mathbb{Z}_N^*$，$T$是正整数，那些不知道$N$的分解的人只能按以下顺序逐步计算：$x \to x^2 \to x^{2^2} \to \cdots \to x^{2^T}$。另一方面，那些知道$N$的分解的人可以先计算$e := 2^T \mod \phi(N)$，然后计算$y := x^e \mod N$，时间复杂度为$\mathcal{O}(\log T)$。

时间锁谜题在要求公平性保证的场景中有着最具说服力的应用。一个突出的例子是将其用作电子投票[2]、[3]中的投票隐藏机制。通过将困难参数$T$设置为远长于投票阶段的时长，可以确保投票在该阶段结束前保持机密性。使用时间锁谜题不仅可以防止投票提前泄露，还消除了投票者在计票阶段未能揭示其投票的风险——这是承诺方案固有的缺陷。类似地，时间锁谜题在各种应用领域也具有巨大潜力，如不可迁移承诺[4]、公平合同签署[5]、数据复制和可检索性[6]、零知识论证[7]以及公开可验证的秘密安全[8]、[9]。

尽管近年来提出了一些不基于顺序平方的定时发布密码学方案[10]、[11]、[12]、[13]、[14]、[15]，但在RSA群（或其子群）中的顺序平方运算仍然是构建定时发布密码学方案中最常见且最可靠的方法[2]、[16]、[17]、[18]、[19]、[20]。最重要的原因是，该假设在社区中已获得充分信任：已证明在强AGM模型下，任何对顺序平方运算的加速都与分解$N$的困难程度相当[21]。

然而，当前基于RSA群中顺序平方运算的时间锁谜题实现通常需要在谜题结构中包含额外元素以保证可求解性，导致通信开销增加。另一方面，当考虑更强大的对手时，例如那些能够自适应选择某些谜题实例以获取其解的对手，我们需要考虑一个更强的模型，在该模型中对手可以访问谜题求解预言机。然而，现有的时间锁谜题方案要么无法达到如此高的安全级别，要么需要显著的额外开销才能实现[21]、[22]、[23]。因此，一个有意义的问题油然而生：**基于RSA群中顺序平方运算的时间锁谜题方案能否同时实现紧凑的谜题表示和强安全保证？**

在本文中，我们进一步研究了基于RSA群中顺序平方运算的时间锁谜题。我们的贡献总结如下：

- **短谜题。** 我们提出了一种新方法，将TLP方案中的单个谜题缩减为$\mathbb{Z}_N^*$中的仅一个元素，并利用该方法构造了一种名为$\textbf{STLP}$（短时间锁谜题）的时间锁谜题方案。该方案在大多数实际场景中相比现有方案实现了更紧凑的谜题表示。

- **强安全模型。** 我们为时间锁谜题引入了新的安全模型，即IND-CSPA（针对自适应选择和求解攻击的不可区分性）安全性和SU-CSPA（针对自适应选择和求解攻击的强不可伪造性）安全性。两者都考虑了同时可以访问谜题生成预言机和谜题求解预言机的对手。IND-CSPA安全性提供语义安全，SU-CSPA安全性提供隐式认证，后文将对此进行澄清。我们的方案$\textbf{STLP}$能够同时实现IND-CSPA安全性和SU-CSPA安全性。

- **解一个，免费得多个。** 我们引入了一种称为"密钥可恢复时间锁谜题"（KR-TLPs）的时间锁谜题变体。在KR-TLP方案中，存在一个算法，可以在至少$T$（困难参数）的时间内从谜题生成密钥推导出一个"快速谜题求解密钥"，拥有该密钥的人可以立即求解谜题。这样一来，任何拥有谜题生成密钥的人就具备了"解一个，免费得多个"的能力，即只需求解单个谜题即可获取任意数量时间锁谜题的解。我们通过扩展方案$\textbf{STLP}$提出了一种KR-TLP方案，称为$\textbf{KR-STLP}$。该方案同样能够抵抗选择求解和谜题攻击。

我们的第一个观察是，大多数现有的TLP方案中每个谜题至少包含两个群元素。就Rivest等人的原始TLP方案[1]而言，每个谜题包含$\mathbb{Z}_N^*$中的两个元素。为了探究原因，在该方案中，选择一个随机$x \in \mathbb{Z}_N^*$，并使用$x^{2^T} \mod N$作为一次性填充。关键在于，$x$必须提供给谜题求解者以使其能够通过反复平方运算计算$x^{2^T} \mod N$。

我们观察到RSA加密方案中的密文仅包含单个元素。这引出了一个疑问：时间锁谜题能否在不损害安全性的情况下实现类似的结构效率？注意，如果按照RSA的密钥生成方式，将$2^T \mod \phi(N)$设为谜题求解密钥，那么谜题生成密钥$e$应满足$e \cdot 2^T \equiv 1 \pmod{\phi(N)}$。然而，这样的$e$无法存在，因为$2^T$和$\phi(N)$不互素，由于对于奇素数$p$和$q$，$\phi(N) = (p-1)(q-1)$是偶数。为了解决这个问题，我们考虑在乘性群$\mathcal{QR}_N$上的运算，其阶为$\phi(N)/4$。此外，如果$N = pq$是强RSA整数，即$(p-1)/2$和$(q-1)/2$也是素数，那么$\phi(N)/4$是奇数，因此必然存在$e$使得$e \cdot 2^T \equiv 1 \pmod{\phi(N)/4}$。

为了利用上述结果构造时间锁谜题方案，我们的最初想法是将解$s$限制在群$\mathcal{QR}_N$中，并使得对谜题$Z$进行$T$步反复平方的结果直接等于$s$，即$s = Z^{2^T} \mod N$。那么谜题$Z$可以由知道满足$e \cdot 2^T \equiv 1 \pmod{\phi(N)/4}$的$e$的人通过$Z := s^e \mod N$生成，从而使得拥有$e$的人可以在不需要知道$N$的分解的情况下生成谜题。

然而，这一基本方案在实际部署和理论安全方面都存在关键局限性。为了改进这一缺陷，我们不直接对解$s$计算$Z := s^e \mod N$，而是首先采用一种编码方案将原始解$s$映射到编码后的解$\hat{s} \in \mathcal{QR}_N$。我们发现PSS-R填充方案[24]是适合的，因为它不仅允许解为任意固定长度的比特串，还提供了强安全性。我们采用了该方案，构造了一种实用且安全的方案，称为$\textbf{STLP}$，其具体安全性将在后文讨论。

在本文中时间锁谜题的定义中，谜题生成算法需要一个由初始化算法生成的谜题生成密钥，该密钥需要保密。因此，不持有密钥的参与者无法自行生成谜题。为了在我们的安全框架中对此进行建模，我们向对手提供了对谜题生成预言机的访问权限，该预言机接收解作为输入并输出相应的谜题。此外，为了实现更高的安全性，我们还向对手提供了对谜题求解预言机的访问权限，该预言机接收谜题作为输入，通过求解输出解（如果有效）。

我们为时间锁谜题的语义安全定义了一个新的安全模型：IND-CSPA（针对自适应选择和求解攻击的不可区分性），该模型确保即使在对手同时拥有谜题生成预言机和谜题求解预言机的情况下，谜题$Z$对应的解$s$在时间$T$之前仍然是完全隐藏的。

我们证明了我们的方案$\textbf{STLP}$在判定性$T$-RSW假设下（该假设在[21]中引入）满足IND-CSPA安全性。

由于使用了PSS-R，方案$\textbf{STLP}$还满足另一个有趣的特性：隐式认证。这对应于一个新的安全模型SU-CSPA（针对自适应选择和求解攻击的强不可伪造性）。

时间锁谜题方案的SU-CSPA安全性类似于签名方案的SU-CMA安全性。在该安全模型中，任何概率多项式时间（PPT）对手$\mathcal{A}$——仅拥有公开参数$\mathbf{pp}$但不拥有谜题生成密钥$\mathbf{gk}$——即使可以访问谜题生成和谜题求解预言机，也无法输出任何之前未生成的有效谜题。强不可伪造性意味着隐式认证，即有效谜题必须由谜题生成密钥持有者生成。

我们证明了我们的方案$\textbf{STLP}$在分解假设下满足SU-CSPA安全性。

我们观察到，当方案$\textbf{STLP}$中的谜题生成密钥$\mathbf{gk}$被公开时，会产生一个有趣的特性。我们证明了存在一个算法$\textbf{GetFac}$，给定满足$e \cdot 2^T \equiv 1 \pmod{\phi(N)/4}$的$N$、$T$和$e$，可以在$T + \mathcal{O}(|N|)$的时间内输出$N$的分解。虽然该算法对求解单个谜题的谜题求解者不提供计算优势，但它允许在时间$T$之后推导出快速谜题求解密钥。一旦获得该密钥，即可立即求解在相同参数下生成的所有谜题。基于这一思想，我们为这一特性引入了一个新的TLP变体，称为"密钥可恢复时间锁谜题（KR-TLP）"。对于KR-TLP方案，知道$\mathbf{gk}$的参与者可以在时间$T$之后通过密钥恢复算法获得快速谜题求解密钥，然后使用它快速求解所有谜题。这等价于求解一个谜题（需要$T$次顺序平方运算）后免费获得所有实际谜题的解，类似于[17]中的"解一个，免费得多个"特性。

此外，我们通过扩展方案$\textbf{STLP}$构造了一种密钥可恢复时间锁谜题方案$\textbf{KR-STLP}$，该方案在合理假设下也能实现选择和求解安全。

我们为两种时间锁谜题方案提供了协议，用于验证以下两个性质：

1. **公开参数的可验证性：** 初始化算法的执行者能够说服他人参数的正确性，使谜题生成者可以使用它们生成有效谜题，从而使谜题求解者能够从中提取解。这确保了方案的可用性。
2. **解的可验证性：** 谜题求解者可以说服他人其获得的解（或不存在的解）的正确性。该协议有助于避免谜题求解过程中的冗余成本，并允许各方将任务外包给单一实体。

这些协议的核心思想是调用基于RSA群上反复平方运算的可验证延迟函数（VDF）协议[25]作为构建模块。在该VDF方案中，给定一个四元组$(N, T, x, y)$，评估者可以为陈述$y = x^{2^T} \mod N$生成一个证明。关键在于，这允许任何拥有平方结果的参与方（即使不知道模数$N$的分解）协助他人快速验证。

公开参数的可验证性协议涉及两个步骤：证明$N$是强RSA整数，以及证明满足$e \cdot 2^T \equiv 1 \pmod{\phi(N)/4}$的$N$、$T$和$e$，且不泄露$\phi(N)$。

前者可以通过现有协议[26]实现，后者可以转换为计算某个特定 $x$ 的 $x_e \cdot 2^T \bmod N$，然后应用VDF协议。方案$\mathsf{STLP}$和$\mathsf{QR-STLP}$的解验证协议有所不同：对于方案$\mathsf{STLP}$，谜题求解者可以借助VDF协议来帮助验证者加速谜题求解过程以验证解；对于方案$\mathsf{QR-STLP}$，谜题求解者只需提供重复平方的结果，然后验证者可以使用谜题生成密钥对其进行检查。

我们分别为各方案提供了一个应用。

1. **吹哨人保护**：正如[27]中所述，吹哨人可能面临人身威胁。时间锁谜题提供了一种延迟发布敏感信息的方式，这确保了吹哨人在封装原始材料后有足够的时间销毁这些材料，从而降低了此类威胁发生的可能性。此外，还需要确保谜题中封装的文档确实是由吹哨人提供的（而非有人冒名顶替）。我们的方案$\mathsf{STLP}$实现了隐式认证，从而确保了这一点。

2. **密封投标拍卖**：在密封投标拍卖中，可以通过使用时间锁谜题方案来避免某些投标者在投标阶段后离线从而无法揭示其投标的问题。然而，如果离线投标者数量庞大，传统时间锁谜题方案的计算成本较高。得益于我们的方案$\mathsf{QR-STLP}$的"解一个，免费获得多个"的能力，可以减少资源消耗，类似于[2]和[17]中的做法。此外，只有持有谜题生成密钥$\mathbf{gk}$的参与者才具备这一能力，而其他参与者（例如仅需获知胜者投标的市场监管者）则不具备。这保护了非胜者投标者的隐私。

## 相关工作

在具有强安全性的定时密码学方面已有相关工作。Katz等人[21]通过适当地适配Naor-Yung范式[28]、[29]引入了一种具有CCA安全性的定时释放公钥加密方案，该方案需要同一消息的两个密文和NIZK证明。Thyagarajan等人[23]以及Chvojka和Jager[30]分别提出了高效的CCA定时承诺方案，它们也遵循Naor-Yung范式。Freitag等人[22]提出了一种通用方法，在随机预言模型中将任意时间锁谜题方案转换为不可篡改的时间锁谜题方案，这在概念上与Fujisaki Okamoto（FO）变换[31]相似。与先前工作不同，我们采用PSS-R填充方案[24]、[32]作为实现IND-CSPA安全性的通道，这不是一种通用方法，但适合我们的方案。

我们的短时锁谜题方案不仅提供了机密性，还提供了认证，这与签名加密[33]有相似之处。事实上，PSS-R填充方案已被证明适合构建签名加密方案[34]，我们借鉴了这一思路。然而，我们的TLP方案与签名加密之间存在两个主要区别：首先，签名加密不提供像TLP那样的延迟属性；其次，在签名加密方案中，持有签名私钥且知道另一参与者加密公钥的参与者可以生成有效的密文。但在我们的方案中，只有一个密钥——谜题生成密钥，持有该密钥的参与者可以生成有效的谜题。在[27]中，Loe提出了一种具有隐式认证的定时释放加密方案，他们将RSA私钥封装在时间锁谜题中，并使用RSA-OAEP方案加密消息，而我们时间锁谜题方案$\mathsf{STLP}$中的谜题直接封装消息，这是与他们最大的不同之处。

我们的密钥可恢复时间锁谜题支持"解一个，免费获得多个"的性质，相关方面已有研究。Malavolta等人[2]引入了同态时间锁谜题的概念，允许在不需要求解谜题的情况下对谜题进行函数计算。Chvojka等人[17]实现了新的"解一个，免费获得多个"的性质，使得在仅求解单个谜题后即可同时检索任意数量的独立时间锁定消息。此外，他们区分了时间锁谜题与定时释放加密，即时间锁谜题用于封装定时释放加密方案的密钥。他们的时间锁谜题方案仅产生PKE方案密钥生成算法中使用的随机数，以生成密钥对。然后他们将相应的公钥$\mathbf{pk}$作为TRE的参数，求解谜题$Z$即可揭示随机数，从而可以检索私钥$\mathbf{sk}$，进而可用于解密所有关于$\mathbf{pk}$计算的密文。我们KR-TLP的核心也是在一定时间后恢复私钥，但使用的是公钥而非谜题。因此，我们KR-TLP方案的优势在于，我们不需要为"解一个，免费获得多个"的性质额外部署任何东西或增加开销。

## 预备知识

我们用$\lambda$表示安全参数。我们用$\text{negl}(\lambda)$表示某个函数是可忽略的。我们用$\coloneqq$表示赋值。我们用$\equiv$表示同余。我们将$A$的二进制串与$B$的二进制串连接记为$A \| B$。我们将二进制串$A$的长度记为$\|A\|$。

我们用$\mathbb{Z}_n$表示模$n$的剩余类环，$\mathbb{Z}_n^* := \{x \in \mathbb{Z}_n : \gcd(x, n) = 1\}$。我们记$\mathcal{J}_n(x)$为$x$模$n$的雅可比符号。我们记$\mathcal{J}_n^{+1}$（分别$\mathcal{J}_n^{-1}$）为$\mathbb{Z}_n^*$中雅可比符号为$+1$（分别$-1$）的元素集合。

## 短时锁谜题

在现有的时间锁谜题方案中，一个谜题至少包含2个群元素，以便使解可恢复。我们的目标是使谜题仅包含$\mathbb{Z}_N^*$中的单个元素。我们尝试使谜题生成和谜题求解在逆方向上操作。类似于RSA加密方案，加密和解密算法是互逆函数。为了使重复平方过程可逆，我们使用以下命题。

**命题5** 设$N = pq$为Blum整数，$T \in \mathbb{N}$

## 密钥可恢复时间锁谜题

在方案$\mathsf{STLP}$中，我们要求谜题求解者不能是谜题生成者，即通常不向谜题求解者提供$\mathbf{gk}$。现在我们讨论如果谜题求解者知道$\mathbf{gk}$会发生什么情况。在此，我们介绍TLP的一个新变体：密钥可恢复时间锁谜题。

**定义7 密钥可恢复时间锁谜题**

一个具有解空间$\mathcal{S}$的密钥可恢复时间锁谜题方案$\mathsf{QR-TLP}$是由五个算法$\mathsf{TPKE} = (\mathsf{Setup}, \mathsf{PGen}, \mathsf{PSolve}, \mathsf{PSolvef}, \mathsf{KeyRec})$组成的元组，具有以下语法：

- $(\mathbf{pp}, \mathbf{gk}, \mathbf{fsk}) \leftarrow \mathsf{Setup}(1^\lambda, T)$ 是一个概率算法，该算法...

## 性能分析

观察定理1和定理2的结果，由于对预言机的任何查询都是多项式的，只要$k_0$和$k_1$足够大，从$\epsilon$中减去的项就是可忽略的。因此，如果攻破方案$\mathsf{STLP}$的IND-CSPA安全性（分别SU-CSPA安全性）的优势不可忽略，则求解$T$-decision RSW问题（分别分解问题）的优势也不可忽略，这与假设相矛盾。因此，我们的归约是合理的。

通常情况下，对于模数...

## 应用

在本节中，我们分别为方案$\mathsf{STLP}$和方案$\mathsf{QR-STLP}$呈现一个应用。

## 结论

在本研究中，我们在强安全模型下提供了一个高效的时间锁谜题方案，其中每个谜题仅包含RSA群中的单个元素。我们的TLP方案能够抵御同时拥有谜题生成预言机和谜题求解预言机访问权限的对手，实现了语义安全和隐式认证。此外，我们引入了TLP的一个新变体，称为"密钥可恢复时间锁谜题"（KR-TLPs），并给出了具体构造，该构造提供了"解一个，免费获得多个"的性质。

## 作者贡献声明

- **Xuexuan Hao**：撰写–原始草稿，方法论，形式化分析，概念化。
- **Jianghong Wei**：撰写–审阅与编辑，调查。
- **Jie Chen**：撰写–审阅与编辑。
- **Zheli Liu**：撰写–审阅与编辑。
- **Xiaofeng Chen**：撰写–审阅与编辑，验证，项目管理。

## 利益冲突声明

作者声明不存在已知的可能影响本文所述工作的竞争性经济利益或个人关系。

Xuexuan Hao | Jianghong Wei | Jie Chen | Zheli Liu | Xiaofeng Chen