CP-ABE：基于密文策略的属性加密

J. Bethencourt, A. Sahai and B. Waters, “Ciphertext-Policy Attribute-Based Encryption,” 2007 IEEE Symposium on Security and Privacy (SP '07), 2007, pp. 321-334, doi: 10.1109/SP.2007.11.

python的charm-crypto库，abenc_bsw07源码阅读

CP-ABE方案首次由 J. Bethencourt，A. Sahai 和 B. Waters在 IEEE Symposium on Security and Privacy (SP '07)上发布，该方案也常被成为BSW（三人名字首字母）。该方案改善了Sahai等人在2005年发表的基于身份的模糊加密方案(FIBE)，该方案将用户身份分解成一系列描述用户身份的属性，加密者加密数据时指定一个属性集合和阈值d，解密者必须拥有至少d个给定的属性才能正确解密密文。FIBE方案是BSW方案的雏形。因为BSW方案是对FIBE方案的改进，在算法设计中也使用了FIBE方案的思想和运算原理，在其基础上添加了访问控制树，以及递归求解访问控制树。

1.方案定义

该方案由5个基本算法组成：Setup、Encrypt、KeyGen、Decrypt和 Delegate。

1. $\mathrm{Setup}$：该算法以隐含安全参数λ作为输入，输出系统公钥PK和主私钥MK。
2. $\mathrm{Encrypt}(PK, M, A) → CT$：该算法输入系统公钥PK、明文M和基于属性的访问结构A，输出对明文M加密后密文CT，且只有用户拥有的属性集合满足访问结构A才能正确解密密文CT。
3. $\mathrm{KeyGen}(MK, PK, S)→ SK$ ：该算法以系统主私钥MK和属性集合S作为输入，输出用户私钥SK。
4. $\mathrm{Decrypt}(PK, CT, SK) → M$：该算法输入系统公钥PK、密文CT和用户私钥SK作为输入，若S满足A，则能够正确解密密文并输出明文M。
5. $\mathrm{Delegate}(SK,\tilde{S})\to \tilde{SK}$ ：该算法输入属性集合$S$的私钥$SK$和一个属性集合$\tilde{S}$且$\tilde{S}\subseteq S$ ，输出一个基于属性集合$\tilde{S}$的私钥$\tilde{SK}$。

2.算法详细设计

该方案用到以下基本条件：

• 令$G_0$为一个阶为素数$p$的双线性群，$g$为$G_0$的生成元。
• 令$e:G_0\times G_0\to G_1$表示双线性映射。
• 群的大小由安全参数$\lambda$决定
• 对于$i\in Z_{p}$和$Z_p$中元素组成的集合$S$，定义拉格朗日系数$\Delta_{i,S}(x)=\prod_{j\in S,j\neq i}\frac{x-j}{i-j}$。
• 应用一个哈希函数$H:\{0,1\}^*\to G_0$，该函数能将任意字符串描述的属性映射为一个随机的群元素

2.1 Setup

该算法以隐含安全参数$\lambda$作为输入，输出系统公钥PK和主私钥MK。

该算法选择一个阶为$p$的双线性群$G_0$，该群的生成元为$g$。然后随机选择加密指数$\alpha,\beta \in Z_P$。输出系统公钥$PK=(G_0,g,h=g^\beta,f=g^{\frac1\beta},e(g,g)^\alpha)$；系统主密钥$MK=(\beta,g^\alpha)$。

2.2 KeyGen

$\mathrm{KeyGen}(MK, PK, S)→ SK$ ：该算法以系统主私钥$MK$和属性集合$S$作为输入，输出用户私钥$SK$。

首先随机选择一个随机数$r\in Z_{p}$，然后对于每个属性$j\in S$，随机选择$r_j\in Z_p$。这个过程是属性集合$S$中有几个属性，那就再$Z_p$里面随机找几个数$r_j$，然后再按照如下过程计算用户私钥：

$$SK=(D=g^{\frac{\alpha+r}\beta},\forall j\in S:D_j=g^r\cdot H(j)^{r_j},D_j^{^{\prime}}=g^{r_j})$$

利用$PK$和$MK$里的相关参数和属性集$S$来计算私钥。

$\forall j\in S:D_j=g^r\cdot H(j)^{r_j},D_j^{'}=g^{r_j}$，则表示属性集$S$里含有几个属性，我们就从$Z_p$里选出几个随机数来计算相应的$D_j$和$D_j^{^{\prime}}$。

2.3 Encrypt

$\mathrm{Encrypt}(PK, M, A) → CT$：该算法输入系统公钥$PK$、明文$M$和基于属性的访问结构$A$，输出对明文$M$加密后密文$CT$，且只有用户拥有的属性集合满足访问结构$A$才能正确解密密文$CT$。

首先对访问结构$A$中的访问控制树$T$中的每个节点$x$（包括叶子节点）选择一个多项式$q_x$，这些多项式自上而下从根节点$R$进行选择。对于树中的每一个节点$x$，设多项式$q_x$的阶$d_x$为节点$x$的阈值$k_x$减去1，即$d_x=k_x-1$。

从根节点$R$开始随机选择$s\in Z_{p}$并设置$q_R(0)=s$。然后随机选择多项式$q_R$的其他$d_R$个点来定义该多项式。对于任何其他节点$x$，令$q_x(0)=q_{parent(x)}(index(x))$且随机选择多项式$q_x$的其他$d_x$个点来定义该多项式。

有点费解，那就举个例子吧！

由图可知，属性值都在叶子节点上，而非叶子节点都是满足条件个数的门限。除了叶子节点，所有非叶子节点都是$a/b$的形式，表示改节点有$b$个子节点，要满足其中$a$个子节点才可以。而非叶子节点才会有随机生成的多项式$q_x$，多项式$q_x$的阶就是该多项式的最高次幂，至于这个阈值$k_x$就是$a/b$这个形式的$a$。

接下来，对这一层的非叶子节点再按照根节点的多项式生成规则，为其随机生成多项式。

令$Y$为访问控制树$T$的所有叶子节点的集合，那么通过控制结构构造的密文为

$$CT=(T,\tilde{C}=Me(g,g)^{\alpha s},C=h^s,\forall y\in Y:C_y=g^{q_y(0)},C_y^{\prime}=H(att(y))^{q_y(0)})$$

$T$表示访问控制树。

$\tilde{C}=Me(g,g)^{\alpha s}$。$M$表示明文，$s$就是根节点上要隐藏的秘密值（上面例子中的5），这个值是在$Z_p$中随机选取的。

$C=h^s$，直观理解即可。

$\forall y\in Y:C_y=g^{q_y(0)},C_y^{\prime}=H(att(y))^{q_y(0)}$，这是对叶子节点的操作，每个叶子节点经过这样计算，都会有一个值，比如上面例子中“网信院”对应值就是19。

2.4 Decrypt

$\mathrm{Decrypt}(PK, CT, SK) → M$：该算法输入系统公钥PK、密文CT和用户私钥SK作为输入，若S满足A，则能够正确解密密文并输出明文M。

解密过程是一个递归算法$\mathrm{DecryptNode}(CT,SK,x)$。该算法输入为一个密文，$CT=(T,\tilde{C},C,\forall y\in Y:C_y,C_y^{^{\prime}})$，一个属性集$S$的私钥$SK$和树$T$中的一个节点$x$。

假如$x$是一个叶子节点，令$i=att(x)$，假如$i\in S$，定义：

$$\mathrm{DecryptNode}(CT,SK,x)=\frac{e(D_i,C_x)}{e(D_i^{'},C_x^{'})}=\frac{e(g^r\cdot H(i)^{r_i},h^{q_x(0)})}{e(g^{r_i},H(i)^{q_x(0)})}=e(g,g)^{r\cdot q_x(0)}$$

这个过程需要用到双线性映射的性质。

如果$i\notin S$的话，那么这个算法就输出⊥，表示控制结构中的属性不在个人私钥对应的属性集合中，则访问控制结构不满足私钥属性集合，则不能解密。

现在考虑非叶子节点时的递归情况，当$x$是非叶子节点时，算法的计算情况如下：对于节点$x$的所有孩子节点$z$，调用函数$\mathrm{DecryptNode}(CT,SK,z)$并存储其结果为$F_z$。令$S_x$为一个任意的大小为$k_x$的孩子节点$z$的集合，并且满足$F_{z}\neq\bot $。如果不存在这样的集合，函数就返回⊥。否则，我们就计算：

$$\begin{aligned}F_x&=\prod_{z\in S_x}F_z^{A_{i,S_x}(0)}=\prod_{z\in S_x}\left(e(g,g)^{r\cdot q_{parent(z)}(index(z))}\right)^{A_{i,S_x^{\prime}}(0)}\\&=\prod_{z\in S_x}e(g,g)^{r\cdot q_x(i)\cdot A_{i,S_x^{\prime}}(0)}=e(g,g)^{r\cdot q_x(0)}\end{aligned}$$

其中，$i=index(z)$，$S_x^{^{\prime}}=\{index(z):z\in S_x\}$

结合上面的例子，我们现在有"计算机学院"(1,19)、“硕士”(2,44)和"研一"(3,83)，所以，根据拉格朗日插值法，我们可以算出这三个节点的父节点的多项式是$q_x(x)=8+4x+7x^2$，这么我们就知道了这个父节点的隐藏秘密值是8。假设现在，我们也知道"教师"(2,11)，结合刚解开的那个秘密值是(1,8)，两者结合，再拉格朗日插值法一下，就得到了根节点的多项式是$q_R(x)=5+3x$。这样，我们就得到根节点的秘密值是5。这里，容易会有一个疑问——我在3/3那个节点解出了它的秘密值是8，进行拉格朗日插值计算的时候，我怎么知道它在根节点的index是1，别忘了，密文里面是有完整的访问控制树的结构的，我们可以根据这个结构很容易就能看出来它的index=1 。所以，在参与拉格朗日插值计算时候，就可以自动加入相应的index值计算。