部分可等价公钥加密的新改进构造

### 部分可等价公钥加密的新改进构造 非承诺加密（NCE）是一种高级的公钥加密形式，能确保多方计算（MPC）协议在自适应对手存在的情况下的安全性。最近，Brakerski 等人提出了一种中间概念——具有部分可等价性的打包加密（PEPE），它蕴含 NCE 并能保持密文率（至多一个常数因子）。本文将介绍基于标准假设的三种新的速率为 1 的 PEPE 构造，包括从具有多项式模数的 LWE 假设和子群决策假设得到的首个常密文率 NCE 构造，以及一种基于 DDH 假设且运行时间有保证的替代构造。 #### 1. 背景知识 - **非承诺加密（NCE）**：由 Canetti 等人引入，是一种公钥加密形式，允许生成“虚拟”密文，这些密文稍后可以被打开为任意消息。通过在 MPC 协议中使用 NCE 作为加密工具，可以欺骗对手，将新被破坏方的内部状态打开为任意消息，同时证明该任意内部状态与协议的公共记录一致。 - **密文率**：NCE 方案效率的一个重要属性，即密文长度与消息长度的比率。 #### 2. 相关工作回顾 | 构造者 | 密文率 | 假设 | 设定 | | ---- | ---- | ---- | ---- | | Canetti 等人 | \(O(λ^2)\) | RSA、CDH | - | | Choi 等人 | \(O(λ)\) | 分解 Blum 整数 | - | | Hemenway 等人 | \(O(log ℓ)\) | Φ - 隐藏 | RSA 模数的不经意采样 | | Hemenway 等人 | \(poly(log λ)\) | LWE、Ring - LWE（超多项式 LWE 模数噪声比） | - | | Canetti 等人 | \(1 + o(1)\) | 不可区分混淆（iO） | CRS | | Yoshida 等人 | \(O(log λ)\) | DDH | - | | Brakerski 等人 | \(O(1)\) | LWE、DDH（超多项式 LWE 模数噪声比） | - | | Yoshida 等人 | \(O(1)\) | LWE、DDH（超多项式 LWE 模数噪声比） | - | #### 3. 本文贡献 - **LWE 构造**：提出首个依赖于具有多项式模数噪声比的 LWE 困难性的常密文率 NCE 方案，改进了 Brakerski 等人和 Yoshida 等人的近期工作。避免使用噪声泛洪来等价密文随机性，而是使用离散高斯卷积来正确模拟模拟密文的噪声。 - **DDH 构造**：提出一种简单的基于 DDH 假设的速率为 1 的 PEPE 构造，与 Brakerski 等人的构造不同。应用通用哈希函数对加密随机性进行处理，然后使用哈希输出作为一次性密码本加密消息，避免了密文压缩算法的缺点，加密算法运行时间严格为多项式。 - **SD 构造**：提出首个基于子群决策（SD）假设的常密文率 NCE（通过 PEPE）构造，使用了公共参考字符串（CRS），这在依赖因子分解困难性时似乎是必要的。 #### 4. PEPE 概述 PEPE 方案是一个高效（PPT）算法元组 \((KeyGen, Enc, Dec, EquivPK, EquivCT)\)： - **KeyGen(b, I, rG)**：输入一个比特 \(b\)、子集 \(I ⊂ [ℓ]\)（\(ℓ\) 是可加密消息的长度）和随机数 \(rG\)，输出公钥 \(pk\) 和私钥 \(sk\)。该算法有两种模式：真实模式（\(b = 0\)）和理想模式（\(b = 1\)）。在真实模式下，该方案应满足常规公钥加密方案在子集 \(I\) 上的正确性。 - **EquivPK(sk, b, (I, rG), I′)**：输入私钥 \(sk\)、比特 \(b\)、\((I, rG)\) 和 \(I′ ⊂ I\)，输出新的随机数 \(r′_G\)，使得 \(r′_G\) 与在 \(KeyGen(0, I′, r′_G)\) 中使用的诚实（真实模式）随机数 \(r′_G\) 不可区分。 - **EquivCT(sk, (M, rE), {M′_i}i∉I)**：输入加密随机数 \(rE\)、消息 \(M\) 和 \(M′\)（其中 \(M_i = M′_i\) 对于 \(i ∈ I\)），输出新的加密随机数 \(r′_E\)。没有高效的对手能够区分 \((pk, M′, r′_E)\) 是通过在理想模式下对不同消息 \(M\) 的加密进行等价处理得到的，还是通过在真实模式下诚实加密得到的。 #### 5. LWE 构造细节 - **真实模式公钥**：由随机整数矩阵