CCA安全属性隐藏内积加密：原理、构造与应用

### CCA安全属性隐藏内积加密：原理、构造与应用 在当今的信息安全领域，加密技术的发展日新月异。属性隐藏内积加密（Attribute-Hiding Inner Product Encryption，AHNIPE）作为一种重要的加密手段，在保护数据隐私和安全方面发挥着关键作用。本文将深入探讨CCA安全的AHNIPE，包括其基本概念、构造方法以及具体应用。 #### 1. 基础概念与预备知识 在介绍AHNIPE之前，我们需要了解一些基础概念和预备知识。 ##### 1.1 查询限制 在密钥生成预言机 $OKG(·)$ 的所有秘密密钥查询 $\{y\}$ 中，需要满足特定条件。当 $M_0 \neq M_1$ 时，$\langle x_0, y\rangle = \langle x_1, y\rangle = 0$；当 $M_0 = M_1$ 时，$\langle x_0 - x_1, y\rangle = 0$。而在解密预言机 $ODec(·, ·, ·)$ 的所有解密查询 $\{(τ, CT, y)\}$ 中，需要满足 $τ \neq τ^*$。 ##### 1.2 准自适应非交互零知识证明（QANIZK） 准自适应非交互零知识证明（Quasi-adaptive Non-interactive Zero-Knowledge Proof，QANIZK）是一种特殊的非交互零知识证明（NIZK），其中公共参考字符串（crs）可以依赖于为生成证明而定义的语言的特定参数。 对于公共参数 $par$，设 $D_{par}$ 是一个关于由 $ρ$ 参数化的关系集合 $R = \{R_ρ\}$ 的概率分布，其关联语言为 $L_ρ = \{x : \exists w \text{ s.t. } R_ρ(x, w) = 1\}$。 QANIZK 由五个概率多项式时间（PPT）算法组成，分别为 $QANIZK = (Genpar, Gencrs, Prv, Sim, Vrfy)$，具体工作方式如下： - $par \leftarrow Genpar(λ)$：返回公共参数 $par$。 - $(crs, trap) \leftarrow Gencrs(par, ρ)$：输入 $par$ 和字符串 $ρ$，输出 $crs$ 和陷门 $trap$。假设 $crs$ 隐式包含 $par$ 和 $ρ$，并定义了一个标签空间 $T$。 - $π \leftarrow Prv(crs, τ, x, w)$：输入 $crs$、标签 $τ \in T$、陈述 $x \in L_ρ$ 和见证 $w$，输出证明 $π$。 - $1 \text{ 或 } 0 \leftarrow Vrfy(crs, τ, x, π)$：一个确定性算法，输入 $crs$、标签 $τ$、陈述 $x$ 和证明 $π$，如果 $π$ 是关于标签 $τ$ 的 $x \in L_ρ$ 的有效证明，则输出 $1$；否则返回 $0$。 - $π \leftarrow Sim(crs, trap, τ, x)$：一个确定性算法，返回模拟证明 $π$（不一定在 $L_ρ$ 中）。 这些算法需要满足以下性质： - **完美完整性**：对于所有的 $λ$、$Genpar(λ)$ 输出的所有 $par$、$D_{par}$ 输出的所有 $ρ$、所有满足 $R_ρ(x, w) = 1$ 的 $(x, w)$ 以及所有 $τ \in T$，有： \[ Pr\left[ \begin{array}{l} Vrfy(crs, τ, x, π) = 1 \\ (crs, trap) \leftarrow Gencrs(par, ρ) \\ π \leftarrow Prv(crs, τ, x, w) \end{array} \right] = 1 \] - **完美零知识**：对于所有的 $λ$、$Genpar(λ)$ 输出的所有 $par$、$D_{par}$ 输出的所有 $ρ$、$Gencrs(par, ρ)$ 输出的所有 $(crs, trap)$、所有满足 $R_ρ(x, w) = 1$ 的 $(x, w)$ 以及所有 $τ \in T$，分布 $Prv(crs, τ, x, w)$ 和 $Sim(crs, trap, τ, x)$ 相同（其中硬币抛掷是在 $Prv$ 和 $Sim$ 上进行的）。 - **模拟可靠性**：对于所有的 PPT 敌手 $A$ 和任何 QANIZK，以下优势是可忽略的： \[ Adv_{A}^{SS}(λ) = Pr\left[ \begin{array}{l} Vrfy(crs, τ^*, x^*, π^*) = 1 \\ \land x^* \notin L_ρ \land τ^* \notin T_{sim} \\ par \leftarrow Genpar(λ); ρ \leftarrow D_{par}; \\ (crs, trap) \leftarrow Gencrs(par, ρ); \\ (τ^*, x^*, π^*) \leftarrow A^{O_{sim}(·,·)}(crs) \end{array} \right] \] 其中 $O_{sim}(τ, x)$ 返回 $π \leftarrow Sim(crs, trap, τ, x)$，$T_{sim}$ 是敌手 $A$ 查询的所有标签的集合。如果敌手 $A$ 只允许对 $O_{sim}(·, ·)$ 进行一次查询，则称 QANIZK 满足一次性模拟可靠性（One-Time Simulation Soundness，OTSS），相应的优势记为 $Adv_{A}^{OTSS}(λ)$。 #### 2. 通用构造方法：从 IPFE 和 QANIZK 构建 AHNIPE 我们可以通过一种通用的转换方法，利用内积功能加密（Inner Product Functional Encryption，IPFE）的不可区分性安全来实现非交互式内积加密（Non-interactive Inner Product Encryption，NIPE）的属性隐藏安全。 考虑一个 IPFE $ = (Setup, KeyGen, Enc, Dec)$，其具有谓词空间 $P'$、属性空间 $Q'$ 和内积空间 $I'$。我们构建一个 NIPE $ = (Setup, KeyGen, Enc, Dec)$，具有相同的谓词空间 $P = P'$、属性空间 $Q$、内积空间 $I = I'$ 和消息空间 $M$，使得 $P, Q, Q' \subseteq I^l$，$M \subset I$，并且对于任何 $x = (x_1, \ldots, x_l) \in Q$ 和 $M \in M$，有 $M \cdot x \in Q'$，其中 $M \cdot x = (Mx_1, \ldots, Mx_l)$。同时，要求在 $I$ 中可以高效执行除法运算，即对于任何乘积值 $α \cdot β \in I$，如果已知 $α$，则可以轻松计算出 $β$。 我们还考虑一个针对语言 $L_{mpk}$ 的 QANIZK $ = (Genpar, Gencrs, Prv, Sim, Vrfy)$： \[ L_{mpk} = \left\{ \begin{array}{l} (\{ct_{1,i}, ct_{2,i}\}_{i = 1}^2) : \\ \exists (x, M, r_1, s_1, r_2, s_2) \text{ s.t. } \\ \land_{i = 1,2}(ct_{1,i} \leftarrow IPFE.Enc(mpk_i, x; r_i) \land \\ ct_{2,i} \leftarrow IPFE.Enc(mpk_i, M \cdot x; s_i)) \end{array} \right\} \] 其中 $par$ 是 IPFE 系统参数的一部分。 我们的 CCA 安全属性隐藏 NIPE 的构造如图 1 所示。QANIZK 用于证明 NIPE 密文的主要部分，即两个 IPFE 密文 $ct_{1,i}$ 和 $ct_{2,i}$，对应于每个 $i = 1, 2$ 的相同属性 $x$。如果密文 $CT = (\{ct_{1,i}, ct_{2,i}\}_{i = 1}^2, π)$ 通过验证，根据 IPFE 的正确性，有 $μ = \langle x, y\rangle$ 和 $μ' = M\langle x, y\rangle$。因此，如果 $μ$ 非零，则可以恢复出消息 $M$。 以下定理表明，在底层 IPFE 在选择明文攻击下具有不可区分性安全，且 QANIZK 具有一次性模拟可靠性的假设下，图 1 中描述的 AHNIPE 在选择密文攻击下具有自适应属性隐藏安全： **定理 1**：对于任何 PPT 敌手 $A$，存在 PPT 敌手 $B_1$ 和 $B_2$，使得： \[ Adv_{A,CCA}^{AHNIPE}(λ) \leq 4 \cdot Adv_{B_1,CPA}^{IND-IPFE}(λ) + 3Q_{Dec} \cdot Adv_{B_2}^{OTSS}(λ) \] 其中 $Q_{Dec}$ 表示敌手进行的解密查询的总数。 #### 3. 从 DDH 和 KerMDH 假设构建 CCA 安全的 AHNIPE 在这部分，我们将介绍一种基于简单的决策 Diffie-Hellman（DDH）假设的更高效的 AHNIPE 构造方法。 首先，我们回顾基于 DDH 的 IPFE 构造。我们的构造受到第 3 节通用方法和基于 DDH 的 IPFE 的启发。与传统的两次独立加密不同，我们使用相同的随机数对向量 $x$ 和 $M \cdot x$ 进行加密，这有助于减少密文的大小。 具体来说，我们考虑基于核矩阵 Diffie-Hellman（Kernel Matrix Diffie-Hellman，KerMDH）假设（$k = 1$）的 Kiltz 和 Wee 的 QANIZK，用于语言 $L_{[a]} = \{[c] : \exists r \in Z_p \text{ s.t. } c = ar\}$。注意，对于第 3 节中给定语言的 QANIZK 证明至少包含八个群元素，而属于 $L_{[a]}$ 的陈述的证明仅由两个群元素组成。 我们描述了一个针对 $P = Q = Z_p^{\ell}$、$I = T = Z_p$ 和 $M \subset I$ 的 AHNIPE，如图 2 所示，其中 $PG = \{G_1, G_2, G_T, p, g_1, g_2, e\} \leftarrow GGen(1^{\lambda})$。我们假设 $M$ 是多项式有界的，以便可以通过离散对数恢复消息。 **正确性证明**：对于所有的 $x, y \in Z_p^{\ell}$、$τ \in Z_p$ 和 $M \in M$，我们有： \[ e(π, [α]_2) = e([(ϑ_1 + τϑ_2)r]_1, [α]_2) = e([(K_1 + τK_2)c]_1, [α]_2) \text{ (当 } c = ar \text{ 时)} = e([c]_1, [(K_1 + τK_2)α]_2) = e([c]_1, [β_1 + τβ_2]) \] 这验证了密文组件 $c = ar$。接下来，我们注意到： \[ \langle υ_1, ς_1\rangle = \left[ \begin{array}{c} c \\ x + U_1c \end{array} \right]^T \left[