组合同态加密与抗碰撞哈希函数构建

### 组合同态加密与抗碰撞哈希函数构建 #### 1. 引言 在密码学领域，组合同态加密和抗碰撞哈希函数是两个重要的概念。组合同态加密允许在加密数据上进行特定的计算，而抗碰撞哈希函数则能确保不同的输入产生不同的哈希值，这在数据完整性验证等方面有着重要应用。 #### 2. 相关定义 - **高效编码**：设 \(X = (X_{\lambda})_{\lambda \in \mathbb{N}}\) 是有限集的集合。若存在一个可有效计算（多项式时间）的单射函数 \(Encode : \{0, 1\}^{\ell} \to X_{\lambda}\)，则称 \(X\) 支持输入长度为 \(\ell = \ell(\lambda)\) 的高效编码。 - **通用哈希函数族**：从集合 \(X\) 到 \(\{0, 1\}\) 的函数集合 \(H\) 是通用哈希函数族，当且仅当对于每对不同的 \(x_1, x_2 \in X\)，哈希函数族 \(H\) 满足 \(\Pr[h(x_1) = h(x_2) : h \leftarrow H] \leq \frac{1}{2}\)。 #### 3. CC - 同态加密与抗碰撞哈希函数的关系 - **定理**：假设存在关于函数 \(f\)、输入分布 \((X, Y)\) 和参数 \(c\) 的 CC - 同态加密方案，且满足以下条件： - 函数集合 \(\{f(\cdot, y) : y \in Y_{\lambda}\}_{\lambda \in \mathbb{N}}\) 是通用哈希函数族。 - 对于 \(ExtE(f)\) 的多项式时间协议在 \(ExtE(X, Y)\) 的任何输入上的正确率为 \(\frac{1}{2} + \frac{1}{p(\lambda)}\)，其中 \(p\) 是某个多项式。 - 集合 \(X\) 支持输入长度 \(\ell(\lambda) \geq c(\lambda)\) 的高效编码，对于足够大的 \(\lambda\)。 那么，存在抗碰撞哈希函数。 #### 4. 抗碰撞哈希函数的构造 考虑以下方案 \((Gen^*, Eval^*)\)： - **密钥生成**：给定安全参数 \(1^{\lambda}\)，概率多项式时间算法 \(Gen^*\) 采样 \(y \leftarrow Y\)，\(k \leftarrow Gen(1^{\lambda})\) 和 \(s \leftarrow Enc_k(y)\) 并输出 \(s\)。 - **评估**：给定索引 \(s\) 和输入 \(m \in \{0, 1\}^{\ell(\lambda)}\)，多项式时间算法 \(Eval^*\) 输出 \(Alice(Encode(m), s)\)。 可以证明该方案确实具有压缩性，即对于任何 \(\lambda \in \mathbb{N}\)，\(s \leftarrow Gen^*(1^{\lambda})\) 和 \(m \in \{0, 1\}^{\ell(\lambda)}\)，\(\vert h_s(m) \vert = \vert Alice(Encode(m), s) \vert \leq \ell'(\lambda) < \ell(\lambda)\)。 假设该方案不是抗碰撞的，那么存在一个概率多项式规模的对手 \(A\) 和一个多项式 \(q\)，使得对于无限多个 \(\lambda \in \mathbb{N}\)，\(\Pr[m \neq m' \land h_s(m) = h_s(m') : s \leftarrow Gen^*(1^{\lambda}), (m, m') \leftarrow A(s)] = \frac{1}{q(\lambda)}\)。 通过构造一个区分器 \(D\) 来证明这与加密方案 \(E\) 的 \(Y\) - 熵安全性相矛盾。 #### 5. 低噪声 LPN 构建 CC - 同态加密方案 - **学习奇偶性带噪声假设**：对于噪声率 \(\mu = \mu(\lambda) \in (0, \frac{1}{2})\)，\(LPN_{\mu}\) 假设是对于任何 \(m(\lambda) = \lambda^{O(1)}\)，\((A, As + e)_{\lambda \in \mathbb{N}} \approx_c (A, u)_{\lambda \in \mathbb{N}}\)，其中 \(A \leftarrow \mathbb{F}_2^{m \times \lambda}\)，\(s \leftarrow \mathbb{F}_2^{\lambda}\)，\(e \leftarrow Ber_m^{\mu}\) 和 \(u \leftarrow \mathbb{F}_2^{m}\)。 - **定理**：假设 \(LPN_{\frac{\log^2 \lambda}{\lambda}}\) 成立，则存在平衡状态下的 CC - 同态加密方案。 #### 6. 基于低噪声 LPN 的私钥加密方案 - **密钥生成**：给定安全参数 \(1^{\lambda}\)，概率算法 \(Ge