用于云数据共享的含细粒度策略的条件代理广播重加密

摘要

条件代理广播重加密（CPBRE）是一种半信任代理，可以将满足一定条件的Alice密文转换为一组用户密文。但是，代理不能了解有关底层明文的任何信息。传统的CPBRE方案不支持对条件的灵活控制。本文提出了一种新的基于细粒度策略的条件代理广播重加密算法（CPBRE-FG）。在CPBRE-FG方案中，用访问树生成重加密密钥，并在一组描述条件下构造密文。当且仅当这些条件满足访问树时，代理才能对密文进行转换。我们将CPBRE-FG的概念形式化，并提出一个有效的CPBRE-FG方案。最后，我们在随机预言模型中证明了它对选择密文攻击（CCA）的安全性。

关键词：条件代理重加密；代理广播重加密；访问政策；随机预言模型。

引言

代理重加密(PRE)是Blaze、Bleumer和Strauss在Eurocrypt98 (Blaze et al.， 1998)中提出的，它使半信任代理能够将爱丽丝的密文转换为鲍勃的密文。但是，代理不能了解关于Alice的私钥和底层明文的任何信息。Alice可能不需要对所有密文进行转换，而只需要代理对满足一定条件的密文进行转换。为了捕捉这种情况，Weng等人(2009)引入了条件代理重加密(C-PRE)的概念。在他们的工作之后，Chu等人(2009)将C-PRE的概念扩展到CPBRE，其中代理可以将Alice的密文转换为一组用户的密文，例如她的整个员工。

然而，以前的C-PRE和CPBRE方案不支持任何条件上的布尔组合。例如，在一个教育行政管理系统中，教学秘书的密文被加密在一组关键词“日期:7月”、“地点:罗马201”、“主题:信息安全报告”和“参与者:教授”下。秘书收到密文后，如果密文满足以下条件，就可能会转发给整个系的老师： $T = ('July'\wedge 'Report'\wedge('lecturer' \wedge 'professor') \wedge 'Computer science')$

本文引入了细粒度策略的条件代理广播重加密的概念。在CPBRE-FG方案中，密文用一组关键字W加密，用访问树T生成重加密密钥，当且仅当W满足T时，代理可以将Alice的密文转换为一组用户的密文。

我们的贡献

本文首次引入了细粒度策略的条件代理广播重加密的概念。在本文中，我们首先定义了一个访问树，并提出了一个CPBRE方案。最后，在决策n-BDHE假设下，证明了该方案对自适应访问树和自适应身份攻击是安全的。

路线图

我们将在第2节中提供定义和复杂性假设。随后，我们提出了我们的CPBRE-FG方案，并在第三节中证明了它的CCA安全性。最后，在第4部分，我们总结了我们的论文。

预备知识

双线性映射

设G和G_T是两个具有相同素数阶p的可乘循环群，g是G的生成子，双线性配对是一个双线性映射 $e:G\times G\rightarrow G_T$ ，具有以下性质（Boneh和Boyen, 2004；Boneh和Franklin, 2001）：

对于所有的 $a,b\leftarrow Z_{p}^{*}$ 和 $g,h\in G$ ，都有 $e(g^a,h^b)=e(g,h)^{ab}$ ；
$e(g,g) \ne 1$ ；
对于所有的 $g,h\in G$ ，有一个高效地计算 $e(g,h)$ 的算法。

n-BDHE假设

我们系统的安全性是基于一个称为决策双线性Diffie-Hellman指数(BDHE)的复杂性假设(Boneh et al.， 2005)。

$(h, g, g^{\alpha}, g^{\alpha^{2}}, ... , g^{\alpha^{n}}, g^{\alpha^{n+2}}, ... ,g^{\alpha^{2n}})\in G^{2n+1}$ 。

和元素T 2 GT时，对手的任务是确定标记是否为g_i，并定义对手A的优势为：

$Adv^{n-BDHE}_{G,A}=|Pr[A(h,g,g_{1},...,g_{n},g_{n+2},...,g_{2n},e(g_{n+1},h))=1]-Pr[A(h,g,g_{1},...,g_{n},g_{n+2},...,g_{2n},T)=1]|$ 。

其中 $g,h\in G$ ， $α\in Z^{*}_{p}$ ， $T\in G_{T}$ 是随机选择的。如果 $Adv^{n-BDHE}_{G,A}$ 对于所有的概率多项式时间（PPT）对手A是可忽略的，我们说相对于(G,G_T)的n-BDHE假设成立。

细粒度策略的条件代理广播重加密

在本节中，我们将给出细粒度策略的条件代理广播重加密的定义及其安全模型。我们借用了基于密钥策略属性的加密的概念。我们使用访问树来描述访问策略，其中每个内部节点是一个阈值门，叶子与关键字相关联。使用这种方法，我们可以分别使用n-out- n和1-out- n阈值门来表示具有“与”和“或”门的树。当且仅当密文对树的节点分配了满足树的条件时，用户将能够使用提供的重新加密密钥重新加密密文。

定义1 [访问树(Goyal等人,2006)]。访问树T：我们在Goyal等人（2006）中加入了访问树的定义。设T是表示一个访问结构的树。树的每个非叶节点表示一个阈值门，由其子节点描述一个阈值。设num_x为节点x的子节点数，k_x为其阈值，则有0 <k_x≤num_x。当k_x = num_x时，它是一个与门，当k_x = 1时，阈值是一个或门。树的每个叶节点x由一个条件关键字和一个阈值k_x = 1描述。我们将访问树的根设为深度0。设 $\bar{LN_{T}}$ 为所有非叶节点的集合，LNT为所有叶节点的集合。我们表示树p(x)中节点x的父结点。函数关键字(x)仅在 $x\in LN_{T}$ 时定义，它表示与树中的叶节点x关联的条件关键字。访问树T还定义了每个节点的子节点之间的排序，即节点的子节点编号从1到num。函数inex(z)返回一个与节点z相关联的索引，其中索引值是唯一分配给访问树中的节点的。

满足访问树：设T是根为r的访问树，T_r是根在节点x的子树，因此T与T_r相同。T_x(W)=1表示一组条件W满足访问树T_x。如果 $x\in LN_T$ ，那么T_x(W)=1当且仅当 $keyword(x)\in W$ ，如果 $x\in LN_T$ ，计算节点x的所有子z的T_z(W)， T_x(W)返回1当且仅当至少k_x孩子返回1。

定义2 (CPBRE-FG)：一种（一次性）细粒度策略的代理广播重加密方案，由以下算法组成:：

Setup(λ,n)：在输入安全参数λ和最大用户数n时，输出公钥PK和主密钥msk。

Extract(PK, msk, i)：输入公钥PK，主密钥msk和一个用户 $i\in \{1,2,…,n\}$ ，输出用户i的秘密密钥sk_i。
Encrypt(PK, S, m, W)：对输入的公钥PK，一个用户集 $S\subseteq \{1,2,…,n\}$ ，消息m和一个描述性关键字集W，输出用户集S的条件集W的密文C。
RKGen(PK, sk_i, S', T):输入公钥PK，用户i的秘密密钥sk_i，一个用户集 $S'\subseteq \{1,2,…,n\}$ 和一个访问树T，输出重加密密钥 $rk_{i,T,S'}$ 。
$ReEnc(PK,rk_{i,T,S'},i,S,S',C)$ ：输入公钥PK，重加密密钥 $rk_{i,T,S'}$ ，用户i，两个用户集S，S'和一个原始密文C，如果T(W)=1，输出重加密的密文C_R，否则输出错误符号 $\bot$ 。
$Decrypt2(PK, sk_i, I, S, C)$ ：Decrypt2表示原密文解密算法。在输入公钥PK、用户i的私钥sk_i、用户i、用户集S和用户集S的密文C时，输出明文m或错误符号 $\bot$ 。
$Decrypt1(PK, sk_j, i, j, S, S', C_R)$ ：Decrypt1表示重新加密的密文解密算法。输入公钥PK，用户j的私钥sk_j，两个用户i， j，两个用户集S，S'和一个重新加密的密文C_R。输出明文m，或一个错误符号 $\bot$ 。

正确性：CPBRE-FG方案的正确性意味着，对于任意用户集S, S'，条件集W, W'，C=Encrypt(PK,S,m,W)， $rk_{i,T,S'}=RKGen(PK,sk_i,S',T)$ 和 $C_R=ReEnc(PK, rk_{i,T,S'}, i, S, S', C)$ 。

如果 $i \in S$ ，则有 $P_{r}[Deccypt2(PK,sk_{i},i,S,C)=m]=1$ ；

如果 $j \in S'$ 和 $T(W)=1$ ，则有 $P_{r}[Deccypt1(PK,sk_{j},i,j,S,S',C_{R})=m]=1$ 。

下面我们将提供CPBRE-FG方案的基于博弈的安全模型。我们在选择集模型中考虑了CCA的安全性。在选择集模型中，对手应该在挑战用户集S^*和条件集W^*之前提交。

定义3 （IND-sSet-CCA博弈）：接下来我们考虑以下两个在对手A和挑战者C之间的安全博弈。

博弈1：IND-O-CCA博弈，考虑原始密文的不可区分性。

1. Init：对手A选择一个目标用户集 $S^{*} \subseteq \{ 1,2,…,n \}$ 和条件集W^*。

2. Setup：挑战者C运行Setup(n)获取公钥PK和主密钥msk，并将PK交给A。

3. 查询阶段1：对手A进行以下查询：

Extract(i)：挑战者运行 $sk_i=KeyGen(PK, msk, i)$ ，将sk_i返回给a，否则返回 $\bot$ 。
$RKGen(i, S', T)$ ：挑战者运行 $rk_{i, T,S'}= RKGen(PK, sk_i, S',T)$ ，其中 $sk_i=KeyGen(PK,msk,i)$ ，返回 $rk_{i,T,S'}$ 到A。
$ReEnc(I, S, S', C)$ ：挑战者运行 $ReEnc(PK, rk_{i,T,S'}, i, S, S', C)$ ，其中 $rk_{i,T,S'}=RKGen(PK, sk_i, S', T)$ 和 $sk_i=KeyGen(PK, msk, I)$ ，将结果返回给A。
Decrypt2(i, S, C)：挑战者运行Decrypt2(PK, ski, i, S, C)，其中ski = KeyGen(PK, msk, i)，将结果返回给A。
Decrypt1(i, j, S, S', C_R)：挑战者运行Decrypt1(PK, skj, i, j, S, S', C_R)，其中sk_j=KeyGen(PK, msk, j)，将结果返回给A。

在查询阶段1，A有以下限制：

对于任意 $i\in S^*$ ， A都不能满足Extract(i)，
如果 $i\in S^{*}, j\in S',T(W)=1$ ，A不能使RKGen(i, T, S')和Extract(j)成立。

4. 挑战：一旦A决定查询阶段1结束，它输出两个相等长度的消息(m₀;m₁)。挑战者C选择位 $b\in \{0,1\}$ ，挑战密文为 $C^{*}=Encrypt(PK, m_b, S^{*}, W^{*})$ 。最后，将C^*返回给对手A。

5. 查询阶段2：A继续执行查询阶段1中的查询，具有以下限制：

对于任意i∈S*， A不能取Extract(i)；
如果I∈S*， j∈S'，T (W*)∈1，A不能使RKGen(I, S', T)和Extract(j)；
如果i∈S*， j∈S'， A不能使ReEnc(i, S*， S'， C*)和Extract(j)；
对于任意i∈S*，A不能生成 $Decrypt2(i, S^{*}, C^{*})$ ；
如果 $i\in S^{*},j\in S'$ ，且 $C_R=ReEnc(i, S^*,S',C^*)$ ， A不能生成 $Decrypt1(i, j, S^{*}, S', C_R)$ 。

6. 猜测：A输出猜b。如果b'=b，对手获胜。

我们将上述对手A称为IND-O-CCA对手。其优势定义为：

$Adv^{Game1}_{A,n}=|Pr[b'=b]-1/2|$

博弈2：IND-Re-CCA博弈，考虑重新加密的密文的不可区分性。
博弈2考虑重新加密的密文的安全性。安全的补充定义也捕获了他们无法区分重加密的密文。对于单一使用方案，对手可以访问所有重加密密钥，因此重加密预言将变得无用。而且Decrypt2预言也没必要了。
1. Init：对手A选择一个目标用户集 $S^{*}\in \{1, 2, …, n\}$ 和条件集W^*。

2. Setup：挑战者C运行Setup(n)获取公钥PK和主密钥msk，并将PK交给A。

3. 查询阶段1：对手A进行以下查询：

Extract(i)：挑战者运行 $sk_i=KeyGen(PK, msk, i)$ ，返回sk_i给A，否则返回 $\bot$ ，注意，A不能对任何 $i\in S^{*}$ 做Extract(i)。
RKGen(i, S', T)：挑战者运行 $rk_{i,T,S'}=RKGen(PK, sk_{i}, S', T)$ ，其中 $sk_{i}=KeyGen(PK, msk, i)$ ，返回 $rk_{i,T,S'}$ 到A。
Decrypt1(i, j, S, S', C_R)：挑战者运行Decrypt1(PK, sk_j, i, j, S, S', C_R)，其中sk_j=KeyGen(PK, msk, j)，将结果返回给A。

4. 挑战：一旦A决定查询阶段1结束，它就输出两个相等长度的消息(m₀, m₁)。挑战者C选择一个比特b∈{0,1}，设置挑战密文为 $C*=ReEnc(PK, rk_{i,T,S'}, i, S, S*, C)$ ，其中i∈S，i∉S*， C=Encrypt(PK,m_b, S, W^*)， T(W) = 1。最后，将C^*返回给对手A。

5. 查询阶段2：A继续执行查询阶段1中的查询，具有以下限制：

对于任意i∈S*， A不能取Extract(i)；
如果i∈S，j∈S*， A不能生成Decrypt1(i, j, S, S*, C*)。

6. 猜想。A输出b'。如果b' = b，对手获胜。

我们将上述对手A称为IND-Re-CCA对手。其优势定义为： $Adv_{A,n}^{Game1}=|Pr[b'=b]-1/2|$

如果一个模糊条件代理广播重加密方案对所有的PPT对手 $A,A,Adv_{A,n}^{Game1}$ 和 $A,Adv_{A,n}^{Game2}$ 都可以忽略，则该方案是IND-sSet-CCA安全的。

提出CPBRE方案

我们的构建

我们首先定义ω∈Z_p的拉格朗日系数Δ_ω,F(x)和Z_p中的元素集合F： $Δ_{ω,F}(x)=\prod_{i \in F, i\ne \omega} \frac{x-i}{\omega-i}$

我们的构造由以下算法组成：

Setup(λ,n)：设(p, g, g, G_T, e)为一个双线性映射参数。M={0,1}^k表示消息空间。随机选择α,γ∈Z_p，Z∈G和计算 $g^{i}=g^{a^{i}}$ ，i=1,2,…,n,n+2,…,2n。设 $H_1:{0,1}^{k}\times G_T\rightarrow Z^{*}_{p}$ ， $H_2:GT\rightarrow \{0,1\}^{k}$ ， $H_3:\{0,1\}^{*} \times G_T \times G \times G\times G \times \{0,1\}^{k} \rightarrow G$ ， $H_4: Z_p^* \rightarrow G$ ， $H_5:\{0,1\}^{k}\rightarrow Z_p^{*}$ 为抗合谋哈希函数。计算v=g^γ。输出公钥PK和主密钥msk如下： $PK(g,g_1,...,g_{n+2},g_{2n},v,Z,H_1,H_2,H_3,H_4)$ ，msk = y。

KeyGen(PK;msk;i)：用户i的私钥计算如下： $sk_{i}=g_{i}^{\gamma}$ 。

Encrypt(PK, S, m, W)：加密消息m∈M为用户集 $S\subseteq \{1,2,…,n\}$ ，条件集W。随机选取R∈G_T，计算t=H₁(m,R)，输出密文C=(W,C₁,C₂,C₃,C₄,C₅,C₆)。

$C_{1}=R\cdot e(g_{1},g_{n})^{t}$ ， $C_{2}=g^{t}$ ，

$C_{3}=\left( v\prod_{j \in S}g_{n+1-j} \right)^{t}$ ， $C_{4}=\left(C\omega=H_{4}(\omega)^t \right)_{\omega \in W}$ ，

$C_{5}=m \oplus H_{2}(R)$ ， $C_{6}=H_{3}(W,C_{1},C_{2},C_{3},C_{4},C_{5})^{t}$ 。

RKGen(PK, sk_i, S', T)：在输入 $sk_{i}=g_i^\gamma$ ，S'∈{1,2,…,n}和T。首先，对于树T中每个非叶节点x，随机选择σ∈{0,1}^k和一个多项式q_x。这些多项式从根节点r开始，按照如下自上自下的方式选择。它调用过程RKG(T;H5(σ))，其中过程RKG(T;H5(σ))定义如下：

对于树中的每个节点x，设置多项式q_x的度d_x比注的阈值k_x小1，即d_x=k_x-1。对于根r，取多项式q_r的q_r(0)=H₅(σ)和d_r的其他点，随机确定其完整。对于任意其他节点x，设q_x(0) = q_p(x)(index(x))，随机选择其他点d_x来完全定义q_x，一旦多项式确定，对于每个叶节点x，设ω=keyword(x)。因此，给代理重加密密钥的计算方法如下：

选择一个随机值 $r_{x}\leftarrow Z_{p}^{*}$ ，计算 $a_{x}=sk_{i}\cdot Z^{qx(0)}H_{4}(\omega)^{r_{x}}$ ， $b_{x}=g^{r_{x}}$ 。

设a ={ax: x∈LN_T}， b={bx: x∈LN_T}。

选取随机值 $s\in Z^{*}_{p}$ ， $R'\in G_2$ ，计算 $t'=H_1(σ;R')$ 和集合：

$rk_{1}=R'\cdot e(g_{1},g_{n})^{t'}$ ， $rk_{2}=g^{t'}$ ，

$rk_{3}=\left( v\cdot \prod_{j\in S'}g_{n+1-j} \right)^{t'}$ ，

$rk_{4}=\sigma \oplus H_{2}(R')$ ， $rk_{5}=H_{3}(rk_{1},rk_{2},rk_{3},rk_{4})^{t'}$ 。

输出重加密密钥 $rk_{i,T,S'}=(T, a, b, rk_1,rk_2, rk_3, rk_4, rk_5)$ 。

$ReEnc(PK,rk_{i,T,S'},i,S,S',C)$ ：输入一个重加密密钥rk_i,T,S'=(T, a, b, rk₁, rk₂, rk₃, rk₄, rk₅)和一个密文C =(W,C₁,C₂,C₃,C₄,C₅,C₆)。检查以下等式是否成立：

$e\left( C_{2},v \cdot \prod_{j \in S}g_{n+1-j} \right)=e(g,C_3)$ ，

$e(C_{2},H_{4}(\omega))_{\omega \in W} = e(g,C_{\omega})_{\omega \in W}$ ，

$e(C_{2},H_{3}(C_1,C_2,C_3,C_4,C_5))=e(g,C_6)$ 。

否则，定义递归算法NodeReEnc(C,rk_i,T,S',x)，它接受原始密文C，重加密密钥rk_i,T,S'和树中的一个注释x作为输入。

1. 对于叶节点x，设ω=keyword(x)，如果ω∈W，则 $NodeReEnc(C,rk_{i,T,S'},x)=\frac{e(C_{2},a_{x})}{e(b_{x},C_{4})}=\frac{e(g^{t},sk_i \cdot Z^{q_{x}(0)}H_{4}(\omega)^{r_{x}})}{e(g^{r_{\omega}},H_{4}(\omega)^{t})}=e(sk_{i},g^t)\cdot e(Z,g)^{tq_{x}(0)}$

否则，输出 $NodeReEnc(rk_{i,T,S'},x)=\bot$ 。

2. 如果x是一个非叶节点，考虑递归情况，对于x的所有子节点z，它调用NodeReEnc(C, rk_i,T,j, z)并将输出存储为T_z。设F_x为任意k_x大小的子注z集合，且 $T_{z}\ne \bot$ 。如果不存在该集合，则节点不满足，函数不满足 $NodeReEnc(C,rk_{i,T,S'},x)$ 则返回 $\bot$ 。否则，让 $F'_{x}=\{ index(z) : z\in S \}$ ，并且计算：

$T_{x}=\prod_{z \in F_{x},i=index(z)} T(z)^{\Delta_{i},F'_{x}(0)}=\prod_{z \in F_{x},i=index(z)}(e(sk_{i},g^{t})\cdot e(Z,g)^{tq_{x}(0)})^{\Delta_{i},F'_{x}(0)}$

$=e(sk_{i},g^{t})\cdot \prod_{z \in F_{x},i=index(z)}(e(Z,g)^{tq_{p(z)}(index(z))})^{\Delta_{i},F'_{x}(0)}$

$=e(sk_{i},g^{t})\cdot \prod_{z \in F_{x},i=index(z)}(e(Z,g)^{tq_{x}(i)})^{\Delta_{i},F'_{x}(0)}$

$=e(sk_{i},g^{t})\cdot e(Z,g)^{sq_{x}(0)}$

并返回结果。
最后，计算：
$\tilde{C_{1}}=C_{1}\frac{e\left( T_{r}\cdot \prod_{j\in S, j \ne 1}g_{n+1-j+i},C_{2} \right)}{e(g_{i},C_{3})}$

输出重加密的密文： $C_{R}=(\tilde{C_1} , C_2, C_5, rk_{1}, rk_{2}, rk_{3}, rk_{4}, rk_{5})$ 。

Decrypt2(PK,sk_i,i,S,C)：输入一个私钥sk_i和一个原始密文C=(W, C₁, C₂, C₃, C₄, C₅, C₆)，按如下步骤进行：

首先检查方程(1)-(3)是否成立。如果不是，输出 $\bot$ 并终止。否则，

计算： $R=C_{1}\cdot e\left( sk_{i}\cdot \prod_{j\in S, j\ne i}g_{n+1-j}+i, C_{2} \right) / e(g_{i},C_{3})$ ， $m=C_{5} \oplus H_{2}(R), t=H_{1}(m, R)$ ，并检查以下

$C_{2}=g^{t}$ ， $C_{3}=\left( v \cdot \prod_{j \in S} g_{n+1-j} \right)^t$ ，

$C_{6}=H_{3}(C_{1},C_{2},C_{3},C_{4},C_{5})^t$ 。

是否成立。如果是，返回m，否则返回 $\bot$ 。

$Decrypt1(PK, sk_j, i, j, S, S', C_R)$ ：输入私钥sk_j和重新加密的密文 $CR = ( \tilde{C_1} , C_2, C_5, rk_1, rk_2, rk_3, rk_4, rk_5)$ ，处理如下：

首先检查方程是否成立：

$e\left( rk_{2},v\cdot \prod_{j\in S}g_{n+1-j} \right)=e(g,rk_{3})$ ，

$e(rk_{2},H_{3}(rk_1,rk_2,rk_3,rk_4))=e(g,rk_5)$ 。

如果不是，输出 $\bot$ 。否则，计算

$R'=rk_{1}\cdot e\left( sk_{j}\cdot \prod_{l \in S', l \ne j}g_{n+1-l+j},rk_{2} \right) / e(g_{j},rk_{3})$ ，

$\sigma=rk_{5} \oplus H_{2}(R')$ ， $g^{s}=rk_{4}/H_{4}(\sigma)$ ， $t'=H_{1}(\sigma,R')$

检查是否满足

$rk_{2}=g^{t'}$ ， $rk_{3}=\left( v\cdot \prod_{l \in S'}g_{n+1-l} \right)^{t'}$ ，

$rk_{5}=H_{3}(rk_{1},rk_{2},rk_{3},rk_{4})^{t'}$ 。

如果不，返回 $\bot$ ，否则计算

$R=\tilde{C_{1}}/e(C_{2},Z^{H_{5}(\sigma)})$ ， $m=C_{5} \oplus H_{2}(R)$ ， $t=H_{1}(m,R)$ 。

检查是否满足 $C_{2}=g^{t}$ 。如果是，返回m；否则返回 $\bot$ 。

正确性：我们现在解释上述方案的正确性：

对于原始密文C=(C₁, C₂, C₃, C₄, C₅, C₆)，我们有：

$C_{1}\cdot e\left( sk_{i}\cdot \prod_{j\in S,j \ne i}g_{n+1-j-i},C_{2} \right) / e(g_{i},C_{3})$

$=R \cdot e\left( g_{1},g_{n} \right)^t \cdot \frac{e\left( g_{i}^{\gamma}\cdot\prod_{j \in S, j \ne i}g_{n+1-j+i},g^t \right)}{e\left( g_{i},g^{\gamma}\cdot\prod_{j \in S}g_{n+1-j+i} \right)^t}$

$R \cdot e(g_{1},g_{n})^{t} \cdot \frac{e\left( g^{t},\prod_{j\in S, j\ne i}g_{n+1-j+i} \right)}{e\left( g^t,\prod_{j \in S}g_{n+1-j+i} \right)^t}$

对于重新加密的密文CR=(C₁, C₂, C₅, rk₁, rk₂, rk₃, rk₄, rk₅, rk₆)，我们有

$\tilde{C_{1}}=C_{1}\cdot T_{r}\cdot\frac{e\left( \prod_{j \in S,j \ne i}g_{n+1-j+i},C_2 \right)}{e(g_{i},C_{3})}$

$=R\cdot e(g_{1},g_{n})^t \cdot e(sk_{i},g^t)\cdot e(Z,g)^{sq_{x}(0)}\cdot \frac{e\left( \prod_{j \in S,j \ne i}g_{n+1-j+i},C_2 \right)}{e\left( g_{i},\left( v \cdot \prod_{j \in S}g_{n+1-j} \right)^t \right)}$

$=R \cdot e\left( Z,g^t \right)^{H_{5}(\sigma)}$

我们PBRE方案的安全性

在本小节中，我们将证明我们的方案的IND-sSet-CCA安全性。安全博弈分析如下。

定理1：如果H₁, H₂, H₃, H₄, H₅是目标抗碰撞哈希函数，那么在决定n-BDHE假设下，上述方案在随机预言模型中是安全的IND-sSet-CCA。

引理1：如果存在一个可以破坏我们方案的IND-O-CCA对手A，那么我们可以构造一个可以解决确定性n-BDHE假设的模拟器B。

证明：给B一个决定n-BDHE实例 $(h, g, g_1,…,g_n, g_{n+2},…,g_{2n},T)$ ，并决定 $T=e(g_{n+1},h)$ 或T是G_T中的随机元素。初始为空的随机预言H₁, H₂, H₃, H₄, H₅由B控制如下：

如果A查询(m, R)到随机预言H₁，B在H₁列表中搜索一个条目(m, R, t)，如果存在，返回t给A。否则，B随机选择一个 $t\in Z^{*}_{p}$ ，返回s到A，并将(m, R, t)添加到H₁列表中。

如果A查询(R)到随机预言H2，B在H2列表中搜索一个条目(R, k)，如果这个条目存在，返回k给A。否则，B选择一个随机k∈{0,1}^k，返回k给A'，并将(R, k)添加到H₂列表中。

如果A查询 $(W, C_1, C_2, C_3, C_4, C_5)$ 到随机预言H3，B搜索H3列表的条目 $(C_1, C_2, C_3, C_4, C_5, \phi , \varphi)$ 。如果存在，则将 $\Psi$ 返回到A。否则，B随机选取一个 $\phi \in Z^{*}_{p}$ ，计算 $ψ=g^{\phi}$ 。返回ψ为A，并将 $(C_1, C_2, C_3, C_4, C_5, \phi, \varphi)$ 加到H₃列表中。

如果A查询(ω)到随机预言H₄，B在H4列表中搜索一个条目 $(\omega, t, \bar{\omega})$ ，如果存在该条目，则返回 $\bar{\omega}$ 给A，否则B选择一个随机 $\tau\in$ ， $Z^{*}_{p}$ 计算 $\bar{\omega}=g^{\tau}$ 。返回 $\bar{\omega}$ 到A，并添加 $(\omega, t, \bar{\omega})$ 到H₄列表。

如果A查询( $\phi$ )到随机预言H₅，B搜索H₅列表中的条目( $\phi$ ， $\varrho$ )。如果存在这样的条目，则返回 $\varrho$ 到A。否则，B随机选择 $\varrho \in Z^{*}_{p}$ 。返回 $\varrho$ 到A，并添加( $\phi$ ， $\varrho$ )到H₅列表。

B接下来维护以下最初为空的表。

Key^List：记录元组 $(β,i,sk_i)$ ，这是秘密密钥的信息；
ReKey^List：记录元组(β₁, i, S', T, rk_i,T,S', σ, R, flag₁)，存储查询RKGen(sk_i, S', T)的信息。注意，flag₁=1表示重新加密密钥是有效的，否则flag₁=0表示重新加密密钥是一个随机值。
ReEnc^List：记录元组(β₁, S, S', C, C_R, flag₂)，存储查询ReEnc(i, S, S', C)的信息。注意：flag₂=1表示重新加密的密文是通过有效的重加密密钥生成的，否则flag₂=0表示重加密的密文是随机重加密密钥生成的。

1. Init：对手任意选择一个挑战用户集 $S^* \subseteq \{1,2,…,n\}$ ，条件集 $W^{*}=\{ ω_{1}^{*},ω_{2}^{*},…,ω_{n}^{*} \}$ 。

2. Setup：模拟器B随机选取μ,∈Z_p，Z∈G和集合 $v=g^{u}\cdot \left( \prod_{j\in S^{*}} g_{n+1-j} \right) - 1 = g^{\gamma}$ 。B设置公钥为 $PK=(v, g, g_1, …, g_n, g_{n+2}, …, g_{2n}, Z, H_1, H_2, H_3, H_4, H_5)$ 和 $sk=γ$ 。B把PK给了A。

3. 查询阶段1：A发出一系列查询，B响应如下:

Extract(i)：如果i∈S*， B终止。否则B首先搜索Key^List，如果(β, i, sk_i)存在于Key_List，返回结果为sk_i。否则，B产生一个偏置的硬币β，使Pr[β=1]=δ为一些δ，这将在稍后确定。
如果β=0，B输出一个随机位并终止。
如果β=1，B计算 $sk_{i}=g_{i}^{u}\cdot \left( \prod_{j\in S^{*}}g_{n+1-j+i} \right)^{-1}$ 。注意，我们有： $sk_{i}=g_{i}^{u}\cdot \left( \prod_{j\in S^{*}}g_{n+1-j+i} \right)^{-1}=\left( g^{u}\cdot \left( \prod_{j\in S^{*}}g_{n+1-j} \right)^{-1} \right)^{\alpha^{i}}=v^{\alpha^{i}}=g_{i}^{\gamma}$ 。
RKGen(i, S', T)：B检查Key^List中没有元组(*, j, sk_j)，如果i∈S^*， j∈S'和T(W^*)=1，其中*是通配符。如果检查不成立，B终止。否则，B将搜索ReKey^List中是否有元组(*, i, S'，T, rk_i,T,S', σ, R, *)。如果是，B返回rk_i,S',T，作为结果。否则，B进行如下操作：

如果Key^List中存在(1,i,sk_i)，B使用sk_i生成真实方案中的重加密密钥rk_i,S',W'签证算法RKGen。返回重加密密钥给A，并添加 $(*,i,S',T, rk_{i,T,S'},σ,R,1)$ 到ReKey^List，其中σ， R在RKeyGen算法中是随机选择的。

否则，B抛一个有偏差的硬币。如果β=1，B查询Extract(i)预言机获得滑雪，然后生成rk_i,T,S'签证算法RKGen在真实的方案。返回重加密密钥rk_i,T,S'到A和(1,i,sk_i)和(*,i,S',T,rk_i,T,S',σ,R,1)到Key^List和ReKey^List。如果β=0，B设{a=(a_ω=ρ_ω)， b=(bω=ρω):ω∈keyword(ω)}为随机选择的 $ρ_{ω},ρ'_{ω}\in G$ ，则B构造 $rk_1,rk_2,rk_3,rk_4,rk_5$ 为加密随机σ， R为真实方案。B将重加密密钥转发给A，并将(*,i,S',T,rk_i,T,S',σ,R,0)添加到ReKey^List。

ReEnc(i, S, S', C)：B首先搜索ReEnc^List中是否有元组(i, S, S', C, C_R, *)。如果是，B返回结果为C_R，其中*为通配符。否则，B进行如下操作：

如果ReKey^List中存在 $(*,i,S',rk_{i,T,S'},σ,R,*)$ ， B使用rk_i,T,S'生成真实方案中的C_R签证算法ReEnc。返回C_R到A，并添加(i, S, S', C, C_R, *)到ReEnc^List。注意，C=Encrypt(PK, S, m, W)，T(W)=1。

否则，B首先发出 $RKGen(i,S',T)$ 查询，获得重加密密钥rk_i,T,S'。接下来，B生成C_R并添加(i, S, S',C, C_R, *)到ReEnc^List。

Decrypt2(i,S,C)：B首先验证方程(1)-(3)。如果方程不成立，输出 $\bot$ 并终止。否则，B收益：

如果(1,i,sk_i)存在于Key^List中，使用sk_i来恢复m。

否则，B发出Extract(i)查询来获取sk_i，并使用sk_i来恢复m。

Decrypt1(i,j,S,S',C_R)：B首先验证方程(4)-(5)。如果方程不成立，输出 $\bot$ 并终止。否则，B收益：

如果Key^List中存在(1,j,sk_j)，则使用sk_j恢复m。

否则，B发出Extract(j)查询来获取sk_j，并使用sk_j来恢复m。

4. Challenge：一旦A决定查询阶段1结束，它就输出两个相等长度的消息(m₀, m₁)。B随机选取B∈{0,1}，R^*∈G_T。设任意选取的t^*， h = g^t*。B计算：

$C_{1}^{*}=R*T$ ，

$C_{2}^{*}=h=g^{t^{*}}$ ，

$C_{3}^{*}=h^{\mu}=g^{\mu t^{*}}=\left( g^{\mu}\cdot\left( \prod_{j \in S^{*}}g_{n+1-j} \right)^{-1}\left( \prod_{j \in S^{*}}g_{n+1-j} \right) \right)^{t^{*}}$ ，

$C_{4}^{*}=\left( C_{w}=h^{T}=(g^{T})^{t^{*}}=H_{4}(w)^{t^{*}} \right)w\in W^{*}$ ，

$C_{5}^{*}=m_{b} \oplus H_{2}(R^{*})$ ，

$\varphi ^{*} =H_{3}(C_{1}^{*},C_{2}^{*},C_{3}^{*},C_{4}^{*},C_{5}^{*})^{t^{*}}$ 。

其中B查询 $(C_1^*,C_2^*,C_3^*,C_4^*,C_5^*)$ 到随机预言H₃的条目 $(C_1^*,C_2^*,C_3^*,C_4^*,C_5^*,\phi^*, \varphi ^*)$ 。B返回 $C^{*}=(C_1^*,C_2^*,C_3^*,C_4^*,C_5^*,C_6^*)$ 到a。注意，如果T=e(g_n+1, h)，我们有 $C_1^*=R^*\cdot T=R^{*}\cdot e(g,g_{n+1})^{t^*}$ 。因此C^*是一个有效的挑战密文。否则，如果T是G₂中的一个随机值，那么在对手的视图中C^*与b是独立的。

5. 查询阶段2：A使用IND-O-CCA博弈中描述的限制继续查询阶段1中的查询。

6. 猜想：A输出猜b，如果b'=b，则输出1，意思是T=e(g_n+1, h)；否则输出0，表示T是G₂中的一个随机值。

概率分析：如果B不中止，则A的视图与实际方案相同。我们将Abort定义为在模拟查询过程中B终止的事件。让q表示所有查询的总数，我们有 $Pr[¬Abort] \geq δ^{q} \cdot \left( \frac{p-1}{p} \right)^q = \xi ^{q}(1-\xi)$ ，在 $\delta_{opt}=\frac{q}{(1-q)}$ 处最大。使用δ_opt，概率 $Pr[\neg Abort]$ 至少是 $\frac{1}{e(1-q)}$ ，其中e是自然对数的基数。因此，我们有：

$\epsilon ' \geq \frac{\epsilon}{e(1+q)}-Adv^{TCR}_{H_{1},A}-Adv^{TCR}_{H_{2},A}-Adv^{TCR}_{H_{3},A}-Adv^{TCR}_{H_{4},A}-Adv^{TCR}_{H_{5},A}$ 。

这就完成了引理1的证明。

引理2：如果存在一个可以破坏我们方案的IND-Re-CCA对手A，那么我们可以构造一个可以解决确定n-BDHE假设的模拟器B。

证明：引理2的证明与引理1的证明几乎相同，只是在挑战阶段，挑战者按以下方式构造挑战重加密的密文。B随机选取 $B\in \{0,1\}$ ， $R^*\in G_T$ 。设任意选取的t^*， h=g^t*。B计算：

$\tilde{C_{1}^{*}}=R^* \cdot e(h,Z)^{H_{5}(\sigma)}$ ，

$C_{2}^{*}=h=g^{t^{*}}$ ，

$C_{5}^{*}=m_{b} \oplus H_{2}(R^{*})$ 。

然后B构建 $rk_{1}^{*},rk_{2}^{*},rk_{3}^{*},rk_{4}^{*},rk_{5}^{*}$ ，方法与博弈1相同。

结论和未决问题

在本文中，我们引入了细粒度策略的条件代理广播重加密的概念，它允许代理一次将用户的密文转换为一组用户的密文，只要密文中的关键字满足访问树。提出了一种细粒度策略的有条件代理广播重加密方案，并证明了该方案在随机oracle中抗选择密文攻击的安全性。这项工作激发了许多有趣的问题，例如标准模型中的CCA安全CPBRE-FG方案和没有随机预言的CPBRE-FG方案。