基于CPA的功能重加密安全性分析

### 基于CPA的功能重加密安全性分析 在加密系统的安全性研究中，功能重加密的安全性是一个重要的研究方向。本文将详细分析功能重加密系统的安全性，特别是1 - FuncCPA + 安全性，并给出相关的证明。 #### 1. 预备知识与基本假设 - **功能重加密相关概念**：考虑一个1 - FuncCPA + 攻击者A，其提交给功能重加密预言机的密文称为输入密文，预言机返回的密文称为输出密文。 - **简化假设**： 1. **避免重复查询**：攻击者A不会提交与之前输出密文相等的输入密文。因为若之前的查询(ct, f)返回ct′，新查询(ct′, f ′)可替换为(ct, f ′ ◦ f)，二者答案相同。 2. **签名验证**：攻击者A不会对签名验证失败（Ver(vk, ⃗ct, σ) = 0）的输入密文进行查询。若遇到此类查询，可将其替换为对0k的新鲜加密查询。 3. **验证密钥分离**：输入密文中的验证密钥集合与输出密文中的验证密钥集合是不相交的。若要使用相同验证密钥，攻击者需伪造签名，而这发生的概率可忽略不计。 满足上述三个假设的攻击者称为合规攻击者。合规攻击者在区分真实游戏和“理想”游戏时与一般攻击者具有相同的优势（因签名伪造产生的差异可忽略不计）。 #### 2. 重要概念定义 - **有效密文**：复合密文ct′ = ⟨⃗ct, vk, σ⟩相对于所有组件公私钥对{(eki,j,b, dki,j,b) : b ∈ {0, 1}, i ∈ [κ], j ∈ [n]}是有效的，需满足存在唯一码字¯c ∈ C，使得对于所有i ∈ [κ]，使用第i行解密得到的字与¯c的汉明距离至多为d。即设γi,j := Dec(dki,j,vi, vk, cti,j)，记ci = (γi,1, ..., γi,n)，所有ci与¯c的汉明距离至多为d。否则，密文无效。 - **不良事件**：设S∗和所有组件公私钥对已知。不良事件Bad指攻击者A使用无效密文ct′ = ⟨⃗ct, vk, σ⟩进行功能重加密查询，但解密过程的步骤(4)未触发。具体而言，存在码字¯c = (¯γ1, ..., ¯γn) ∈ C，满足： - 存在索引i1, i2 ∈ [κ]，使得D′(ci1) = ¯c，但ci2与¯c的汉明距离大于d。 - 所有ci在列j ∈ S∗上的符号与¯c一致，即∀i ∈ [κ], ∀j ∈ S∗: γi,j = ¯γj。 设q是攻击者A进行功能重加密查询次数的多项式上界。对于u ∈ [q]，Badu表示第u次功能重加密查询导致上述不良事件发生的事件。对于v ∈ [q]，1stBadv表示首次导致不良事件发生的查询是第v次查询的事件，即1stBadv = Bad1 & ... & Badv−1 & Badv。 #### 3. 混合实验 考虑一组q + 1个混合实验H0, H1, ..., Hq，其中在混合实验Hu中，前u次功能重加密查询通过加密全零明文进行回复，从u + 1次及以后的查询按照真实的1 - FuncCPA + 游戏进行回复。真实的1 - FuncCPA + 游戏是H0，理想游戏是Hq。要证明复合方案E′是1 - FuncCPA + 安全的，即证明： \[ \left|\Pr_{Hq}[A \to 1] - \Pr_{H0}[A \to 1]\right| \leq negl(\lambda) \] 其中A → 1表示攻击者A输出1后停止的事件，negl(·)是一个可忽略函数。 为了证明上述不等式，我们先得到： \[ \left|\Pr_{Hq}[A \to 1] - \Pr_{H0}[A \to 1]\right| \leq \left|\Pr_{Hq}[A \to 1 | Bad] - \Pr_{H0}[A \to 1 | Bad]\right| + \Pr_{H0}[Bad] + \Pr_{Hq}[Bad] \] 核心证明依赖于以下三个引理： - **引理3.3**：对于所有u, v ∈ [q]，存在可忽略函数negl(·)，使得 \[ \left|\Pr_{Hu - 1}[1stBadv] - \Pr_{Hu}[1stBadv]\right| < negl(\lambda) \] - **引理3.4**：对于所有v ∈ [q]，存在可忽略函数negl(·)，使得 \[ \Pr_{Hq}[Badv] < negl(\lambda) \] - **引理3.5**：对于所有u ∈ [q]，存在可忽略函数negl(·)，使得 \[ \left|\Pr_{Hu}[A \to 1 \& Bad] - \Pr_{Hu - 1}[A \to 1 \& Bad]\right| \leq negl(\lambda) \] #### 4. 证明过程中的关键事实 - **事实3.6**：对于任何u ≥ v，混合实验Hu中第v次预言机查询的回复方式不依赖于秘密密钥中的索引i∗或集合S∗。因为根据Hu的定义，第v次输出密文只是全零明文的加密，与其他因素无关。 - **事实3.7**：对于任何u, v ∈ [q]，如果在混合实验Hu中事件Badv未发生，那么第