ParaDiSE：全恶意模型下的高效阈值认证加密

### ParaDiSE：全恶意模型下的高效阈值认证加密 #### 1. 引言 密码学在组织内部和组织之间的应用日益广泛，用于保护有价值的数据并执行授权。由于 GDPR 和 PCI 等法规的要求，以及基于芯片和加密货币的支付方式的出现，加密密钥的被盗、丢失或滥用可能会带来经济损失，因此保护加密密钥变得愈发重要。 目前，许多设备都配备了可信硬件，如苹果和谷歌的移动设备、ARM 和英特尔 SGX 的商品处理器，同时组织也越来越多地使用硬件安全模块（HSM）来生成和保护加密密钥。然而，这些可信硬件的构建和部署成本高昂，使用难度大，操作灵活性有限，并且在大规模应用时难以确保安全。因此，许多人希望减少对可信硬件的依赖。 阈值密码学提供了一种不同且互补的方法。它不依赖于单个设备的安全性，而是要求攻击者必须攻破一定数量（阈值）的设备，从而增加了攻击的难度。此外，阈值密码学可以通过软件实现，具有成本低、部署快和灵活性高的优点，还能从密码学层面执行需要多方参与决策的业务策略。 阈值密码学的优势吸引了众多从业者的关注。美国国家标准与技术研究院（NIST）已着手对阈值密码学进行标准化，越来越多的商业产品也开始采用这项技术，如 Vault 的数据保护服务、Coinbase Custody 以及 Unbound Tech 的 HSM 替代品等。在这些商业产品中，阈值对称加密被广泛用于保护存储数据、生成令牌或随机数，不同的方案在安全性、性能和部署等方面进行了不同的权衡。 #### 2. 阈值对称加密的方法 阈值对称加密有以下几种实现方法： - **秘密共享法**：一种简单的方法是对算法（如 AES - GCM）的密钥进行秘密共享，将密钥份额分发给不同的参与方。在进行加密或解密时，需要联系一定数量的参与方来重构密钥。然而，这种方法在某些时候需要重构密钥，几乎抵消了将秘密分割的优势。 - **明文共享法**：另一种方法是对明文进行秘密共享，将每个份额发送给持有不同密钥的参与方。这种方法避免了密钥重构，但如果应用于 AES - GCM 等认证加密方案，会显著增加通信和存储成本。 - **安全多方计算（MPC）**：MPC 可以在操作过程中保持密钥的分割状态，适用于需要向后兼容的应用场景。但 MPC 的性能开销较大，通常需要在不同参与方之间进行多轮高带宽通信。例如，Keller 等人的研究表明，对于 128 位的 AES 块，双方计算需要 2.9 到 8.4 MB 的通信量和至少 10 轮通信。在不需要向后兼容的场景中，使用 MiMC 和 LowMC 等 MPC 友好的密码可以适度提高性能。 - **DiSE 方案**：Agrawal 等人提出的阈值认证加密（TAE）方案 DiSE 在两轮通信内完成操作，在两方设置下每次加密需要 32 到 148 字节的通信量。该方案输出的密文具有完整性保护，通信复杂度与消息长度无关，性能比 MPC 实现的认证加密高出多个数量级，因此成为追求阈值安全应用的首选方案，也促使人们进一步研究专用的 TAE 方案。 #### 3. 重新审视阈值认证加密 Agrawal 等人（简称 AMMR）首次对 TAE 方案进行了研究，旨在实现阈值环境下的机密性和完整性，同时确保主密钥在加密和解密过程中保持分布式状态。他们将安全性定义为相对于阈值 t 的概念，t 比协议能够容忍的恶意方数量多 1。机密性通过类似 CPA 的游戏来定义，攻击者参与加密会话，目标是破解挑战密文的语义安全性；完整性定义为“多一个密文完整性”，即攻击者必须提供比“伪造预算”多一个的有效密文。 然而，AMMR 的形式化定义存在以下三个缺点： - **机密性无法防止密钥重构**：AMMR 的机密性定义不能防止参与者重构主密钥。存在一个反例方案，它满足 AMMR 定义的机密性和完整性，但攻击者可以重构主加密密钥，从而在不联系其他参与者的情况下进行加密。这是因为 AMMR 的 CPA 类机密性游戏不允许攻击者发起解密会话，所以方案可能在解密过程中泄露秘密密钥。 - **完整性概念宽松**：在 DiSE 协议中，参与者无法区分自己是在参与加密还是解密过程，攻击者可以在解密会话中生成有效密文，这在实际应用中会给日志记录和权限管理带来困难，是一种不理想的特性。此外，AMMR 的完整性定义允许“可篡改”的 TAE 方案，攻击者可以让诚实方输出无效密文，然后对其进行“修补”以获得正确的密文，从而破坏了密文的完整性。 - **安全处理抽象且不具体**：AMMR 的定义框架涵盖了广泛的协议类型，但这种通用性使得对攻击者能力的形式化变得复杂。此外，DiSE 协议的安全分析是渐近的，在实际应用中难以指导如何安全地设置参数。 #### 4. 主要贡献 针对 AMMR 定义的不足，我们致力于推动 TAE 方案在形式化、设计和分析方面的发展。除了对我们的方案进行具体的安全分析外，我们还首次对分布式伪随机函数（DPRF）及其可验证扩展 DVRF 进行了具体分析，采用了一种新的模块化技术——张量 DDH（Tensor DDH），它是矩阵 DDH 假设的一种变体，能够比 AMMR 的方法更紧密地将安全性归约到 DDH 假设。 - **新定义**：我们引入了新的 TAE 安全定义，解决了 AMMR 定义中的问题。我们只考虑在两轮通信内完成操作的 TAE 方案，提出了 IND - CCA 类型的定义，用于捕获机密性和完整性，并防止密钥重构。我们的定义要求协议使参与者能够区分加密和解密过程。受公钥文献中同名定义的启发，我们提出了 CCA 和 RCCA（“可重放”CCA）两个定义，分别保证密文完整性和明文完整性。我们认为 RCCA 对于许多应用场景已经足够，而 CCA 适用于对密文完整性要求较高的场景。需要注意的是，实现 CCA 安全的性能成本相对较高。 - **新构造**：我们提出了满足新安全定义的构造方案。为实现 RCCA 安全，我们采用了两种方法：一是使用一种全有或全无变换，结合加密和解密过程中的正向和反向块密码调用；二是结合 DPRF 和阈值签名。为实现 CCA 安全，我们使用了分布式可验证 PRF 结合阈值签名。 - **性能评估**：我们对构造方案进行了广泛的性能研究，并与 DiSE 协议进行了比较。在三方设置且阈值为 2 的情况下，我们的 RCCA 安全的随机注入构造方案每秒可实现超过 777,000 次加密，每次加密的延迟为 0.1 毫秒；CCA 安全的构造方案每秒可实现约 350 次加密，延迟为 4 毫秒。虽然这些数字约为 DiSE 协议的 0.7 倍，但我们的构造方案通过满足 RCCA 和 CCA 概念提供了更强的安全性。 #### 5. 技术概述 - 安全定义 - **全恶意安全模型**：在我们的模型中，攻击者可以获取腐败方的秘密密钥，并在加密或解密过程中代表它们行事。攻击者还可以通过这些腐败方发起协议，并接收诚实方的输出。与 AMMR 的模型不同，我们的模型保证即使攻击者能够解密诚实生成的密文，也无法解密挑战密文。此外，我们要求在攻击者偏离诚实解密协议的情况下仍能保证真实性。 - **通过解密标准捕获隐私**：我们的阈值 IND - RCCA 和 IND - CCA 定义遵循标准的左右不可区分性模型。攻击者提交消息对 (m0, m1)，以获得隐藏位 b 对应的消息 mb 的挑战加密。如果攻击者能够猜出 b，则破解了隐私。为防止攻击者通过诚实执行解密协议猜出 b，我们引入了解密标准的概念。解密标准 Eval - MSet(c, CR) 用于捕获攻击者为了解密密文 c 所需发送和响应的消息集合。 - **捕获真实性**：在标准认证加密中，真实性通过 INT - CTXT 来捕获，即攻击者能够生成的唯一有效密文是从加密预言机获得的。在我们的设置中，情况更为复杂。攻击者可以自行发起加密会话生成密文，而且外部观察者可能无法确定攻击者试图加密的消息。因此，我们根据攻击者与诚实方的交互次数为其设定伪造预算。此外，我们考虑了密文真实性的放松形式——明文真实性（类似于 INT - PTXT），并要求即使攻击者在解密过程中任意偏离协议，有效解密也必须解密为之前见过的消息（IND - RCCA）。我们还考虑了在存在恶意解密的情况下提供密文完整性（IND - CCA）。 #### 6. 技术概述 - 构造方案 我们提出了三种构造方案： - **随机注入方法**：该方法仅基于对称密钥原语，实现了 RCCA 安全。密钥以 t - out - of - n 的复制格式进行分发，具体来说，通过组合秘密共享方案，将 \(d = \binom{n}{t - 1}\) 个随机密钥分发给参与方，使得任意 t 个参与方共同拥有所有 d 个密钥，而任何少于 t 个参与方的子集至少缺少一个密钥。该构造需要两个原语：随机注入函数 \(I: X \to Y\) 及其逆函数 \(I^{-1}: Y \to X \cup \{\perp\}\)，以及带密钥的伪随机置换 \(PRP: PRP.kl \times \{0, 1\}^k \to \{0, 1\}^k\) 及其逆函数 \(PRP^{-1}\)。加密过程中，加密者计算 \(y \leftarrow I(m)\)，并将 \(y\) 拆分为 \(y_1, y_2, \ldots, y_{\ell}\)，其中 \(\ell \geq d\)。然后，加密者选择 \(t - 1\) 个其他参与方，将 \(y_i\) 发送给拥有 \(k_i\) 的参与方，该参与方返回 \(e_i = PRP_{k_i}(y_i)\)。最终密文定义为 \(c = (e_1, \ldots, e_d, y_{d + 1}, \ldots, y_{\ell})\)。解密时，解密者通过与其他 \(t - 1\) 个辅助方交互计算 \(y_1, \ldots, y_d\)，然后本地计算 \(m = I^{-1}(y_1, \ldots, y_{\ell})\)。该方案的安全性依赖于随机注入的隐藏和真实性属性，并且在加密和解密查询之间有明显的区别，增强了安全性。 - **基于 DPRF 的方法 I：通过阈值签名实现 IND - RCCA**：该构造基于 DiSE 方案。DiSE 方案使用分布式伪随机函数（DPRF），在加密消息 m 时，生成承诺 \(\alpha = Com(m; r)\)，DPRF 输出 \(\beta \leftarrow DP(j \parallel \alpha)\) 作为加密密钥，将 \((m, r)\) 加密为密文 \(c \leftarrow enc_{\beta}(m \parallel r)\)；解密时，重新计算 \(\beta\) 并解密。为了拒绝解密未合法生成的密文，我们在加密过程中为 \(j \parallel \alpha\) 添加阈值签名 \(\sigma\)，解密时各方在响应前验证签名，若验证失败则中止。我们通过一系列游戏跳跃来证明在更强大的模型下的安全性，确保即使攻击者可以任意与诚实方交互并偏离诚实协议，也无法获得挑战密文的额外信息。 以下是这些方法的对比表格： | 方法 | 安全性 | 主要原语 | 特点 | | --- | --- | --- | --- | | 随机注入方法 | RCCA | 随机注入、伪随机置换 | 仅基于对称密钥原语，加密和解密有明显区别 | | 基于 DPRF 的方法 I | IND - RCCA | DPRF、阈值签名 | 基于 DiSE 方案，通过签名增强完整性 | 下面是随机注入方法的加密流程 mermaid 图： ```mermaid graph TD; A[明文 m] --> B[计算 y = I(m)]; B --> C[拆分 y 为 y1, ..., yℓ]; C --> D[选择 t - 1 个参与方]; D --> E[发送 yi 到拥有 ki 的参与方]; E --> F[参与方返回 ei = PRPki(yi)]; F --> G[生成密文 c = (e1, ..., ed, yd + 1, ..., yℓ)]; ``` ### ParaDiSE：全恶意模型下的高效阈值认证加密 #### 7. 基于 DPRF 的方法 II：通过可验证 PRF 实现 IND - CCA 为了实现 IND - CCA 安全，我们在 DPRF 的基础上引入可验证性。在这个方案中，我们使用分布式可验证 PRF 结合阈值签名。 和之前基于 DPRF 的方法类似，在加密消息 \(m\) 时，首先生成承诺 \(\alpha = Com(m; r)\)。不同的是，这里的 DPRF 具备可验证性，我们记为 \(VDP\)。通过 \(VDP\) 计算输出 \(\beta \leftarrow VDP(j \parallel \alpha)\)，同时会生成一个可验证的证明 \(\pi\) 来证明这个输出的正确性。然后使用 \(\beta\) 作为加密密钥，将 \((m, r)\) 加密为密文 \(c \leftarrow enc_{\beta}(m \parallel r)\)。 在解密时，解密方需要重新计算 \(\beta \leftarrow VDP(j \parallel \alpha)\)，并验证证明 \(\pi\) 的有效性。只有当证明有效时，才会继续进行解密操作 \(m \leftarrow dec_{\beta}(c)\)。 这种方法的优势在于，通过可验证 PRF 和阈值签名的结合，能够提供更强的密文完整性保证。即使攻击者试图在解密过程中进行恶意操作，由于可验证性的存在，解密方可以检测到并拒绝无效的解密请求，从而确保密文的完整性。 以下是三种构造方案的详细对比表格： | 构造方案 | 安全性 | 主要原语 | 加密过程 | 解密过程 | 特点 | | --- | --- | --- | --- | --- | --- | | 随机注入方法 | RCCA | 随机注入 \(I\)、伪随机置换 \(PRP\) | 计算 \(y = I(m)\)，拆分 \(y\) 并与 \(t - 1\) 个参与方交互计算 \(e_i = PRP_{k_i}(y_i)\)，生成密文 \(c\) | 与 \(t - 1\) 个辅助方交互计算 \(y_i\)，本地计算 \(m = I^{-1}(y_1, \ldots, y_{\ell})\) | 仅基于对称密钥原语，加密和解密有明显区别 | | 基于 DPRF 的方法 I | IND - RCCA | DPRF、阈值签名 | 生成承诺 \(\alpha = Com(m; r)\)，计算 \(\beta \leftarrow DP(j \parallel \alpha)\) 并添加阈值签名 \(\sigma\)，加密 \(c \leftarrow enc_{\beta}(m \parallel r)\) | 重新计算 \(\beta\)，验证签名，解密 \(m \leftarrow dec_{\beta}(c)\) | 基于 DiSE 方案，通过签名增强完整性 | | 基于 DPRF 的方法 II | IND - CCA | 可验证 DPRF（\(VDP\)）、阈值签名 | 生成承诺 \(\alpha = Com(m; r)\)，计算 \(\beta \leftarrow VDP(j \parallel \alpha)\) 并生成证明 \(\pi\)，加密 \(c \leftarrow enc_{\beta}(m \parallel r)\) | 重新计算 \(\beta\)，验证证明 \(\pi\)，解密 \(m \leftarrow dec_{\beta}(c)\) | 提供更强的密文完整性保证 | #### 8. 性能评估 我们对提出的构造方案进行了广泛的性能研究，并与 DiSE 协议进行了对比。在一个三方设置且阈值设定为 2 的环境下进行测试，得到了以下性能数据： | 方案 | 加密速度（每秒加密次数） | 加密延迟（毫秒） | | --- | --- | --- | | RCCA 安全的随机注入构造方案 | 超过 777,000 | 0.1 | | CCA 安全的构造方案 | 约 350 | 4 | | DiSE 协议（可比方案） | 约为 RCCA 方案的 1.43 倍，CCA 方案的 1.43 倍 | 约为 RCCA 方案的 0.7 倍，CCA 方案的 0.7 倍 | 从数据中可以看出，我们的 RCCA 安全的随机注入构造方案在加密速度上表现出色，每秒能够实现超过 777,000 次加密，并且延迟极低，仅为 0.1 毫秒。而 CCA 安全的构造方案虽然加密速度相对较慢，每秒约 350 次加密，延迟为 4 毫秒，但它提供了更强的密文完整性保证。 与 DiSE 协议相比，我们的方案在性能上约为 DiSE 协议的 0.7 倍，但我们的构造方案通过满足 RCCA 和 CCA 概念提供了更强的安全性。这表明在实际应用中，用户可以根据对安全性和性能的不同需求，选择合适的方案。 #### 9. 总结与展望 通过结合实际考虑、新的理论设计和具体分析，我们提出的 TAE 方案（统称为 ParaDiSE）在性能和安全性上达到了较好的平衡，足以在实际应用中使用。这些方案不仅提供了足够的安全性保证，还呈现出有趣且新颖的设计，具有独立的研究价值。 在未来，我们可以进一步探索以下方向： - **性能优化**：虽然目前的方案已经取得了不错的性能，但仍有优化的空间。可以研究更高效的算法和协议，减少通信和计算开销，提高加密和解密的速度。 - **安全性增强**：随着攻击技术的不断发展，需要持续关注方案的安全性。可以研究如何在不牺牲太多性能的前提下，进一步增强方案的安全性，抵御更复杂的攻击。 - **应用拓展**：将这些方案应用到更多的实际场景中，如金融领域的支付安全、物联网设备的数据保护等，探索其在不同场景下的适用性和优势。 ，从而为密码学领域的发展做出更大的贡献。 下面是整个方案的整体流程 mermaid 图： ```mermaid graph LR; A[选择构造方案] --> B{RCCA 或 CCA}; B -->|RCCA| C[随机注入方法或基于 DPRF 的方法 I]; B -->|CCA| D[基于 DPRF 的方法 II]; C --> E[加密过程]; C --> F[解密过程]; D --> G[加密过程]; D --> H[解密过程]; E --> I[性能评估]; F --> I; G --> I; H --> I; I --> J[根据需求选择方案应用]; ```