同态加密可实现的CCA2松弛

### 同态加密可实现的 CCA2 松弛 在当今的数字时代，数据安全和隐私保护至关重要。同态加密作为一种强大的加密技术，允许在加密数据上进行计算，而无需先解密，为隐私保护提供了新的可能。本文将深入探讨同态加密中的 funcCPA 安全性，它是对 CCA2 安全性的一种有效松弛，能在保护隐私的同时，实现更高效的计算。 #### 1. 预备知识 - **术语和符号**：对于 \(n \in N\)，用 \([n]\) 表示集合 \(\{1, \ldots, n\}\)。使用标准定义，如关于安全参数 \(\lambda\) 的可忽略函数 \(neg(\lambda)\) 和多项式函数 \(poly(\lambda)\)、概率多项式时间算法（ppt）、随机变量、概率集合、计算不可区分性、统计距离 \(\Delta(\cdot, \cdot)\) 以及（强）单向函数。 - **CPA 安全的公钥加密**：公钥加密（PKE）方案 \(E = (Gen, Enc, Dec)\) 具有正确性、CPA 不可区分性实验 \(EXP_{A,E}^{cpa}(\lambda)\) 以及单消息和多消息的 CPA 安全性。如果对密文空间中的任何密文应用解密算法都能返回消息空间中的元素，且密文空间可有效识别，则该方案是完全可解密的。 - **同态加密**：同态公钥加密方案（HE）是在公钥加密方案的基础上，增加了一个支持对密文进行“同态评估”的 ppt 算法 \(Eval\)。其正确性要求扩展到对密文执行的任何同态评估序列。完全同态加密方案还需满足紧凑性，即密文的大小不会随同态操作序列的复杂度增长。 | 方案类型 | 定义 | | ---- | ---- | | 同态加密（HE） | \(E = (Gen, Enc, Dec, Eval)\)，其中 \((Gen, Enc, Dec)\) 是正确的 PKE，\(Eval\) 对输入的公钥 \(pk\)、电路 \(C : M^{\ell} \to M\) 和密文 \(c_1, \ldots, c_{\ell}\) 输出密文 \(\tilde{c} \leftarrow Eval_{pk}(C, c_1, \ldots, c_{\ell})\) | | 安全的 HE | 是 CPA 安全的 PKE | | 紧凑的 HE | 其解密电路的大小是安全参数的多项式 | | \(C\) - 同态的 HE | 对于所有 \(C \in C\) 和所有输入 \(x_1, \ldots, x_{\ell}\)，有 \(Pr[Dec_{sk}(Eval_{pk}(C, c_1, \ldots, c_{\ell})) \neq C(x_1, \ldots, x_{\ell})] \leq neg(\lambda)\) | | 完全同态加密 | 紧凑且对所有电路类 \(C\) 都是 \(C\) - 同态的 | - **分层同态加密（Leveled HE）**：对于每个 \(L \in Z^+\) 作为额外参数传递给 \(Gen\)，记为 \((pk, sk) \leftarrow Gen(1^{\lambda}, 1^L)\)，该方案能紧凑地评估深度至多为 \(L\) 的所有电路。其算法复杂度在 \(\lambda\) 的基础上与 \(L\) 成多项式关系。分层 HE 的 CPA 安全性定义与标准 CPA 定义类似，但允许对手选择挑战密文加密的级别。 ```mermaid graph TD; A[Chal 运行 Gen(1^λ, 1^L) 获得密钥] --> B[Chal 提供 (pk_ℓ) 给 A]; B --> C[A 发送 x0, x1 和 ℓ 给 Chal]; C --> D[Chal 选择 b 并计算 c ← Enc_{pk_ℓ}(x_b) 发送给 A]; D --> E[A 输出 b′]; E --> F[根据 b′ = b 定义实验输出]; ``` - **密文净化**：密文净化算法用于同态加密，可对密文进行重新随机化，使其在统计上接近解密为相同明文的其他（净化后）密文。大多数当代 HE 方案都存在净化算法。净化算法 \(Sanitize\) 满足消息保持性和净化性： - 消息保持性：\(\forall c\) 在密文空间中，\(Dec_{sk}(Sanitize_{pk}(c)) = Dec_{sk}(c)\)。 - 净化性：\(\forall c, c'\) 在密文空间中，若 \(Dec_{sk}(c) = Dec_{sk}(c')\)，则 \(\Delta ((Sanitize_{pk}(c), (pk, sk)), (Sanitize