Home
Login
updated:

属性加密入门

简介

属性加密（Attribute Based Encryption, ABE）可以认为是一种泛化的基于身份加密。相较于需要接收者的公钥对消息进行加密的传统公私钥加密方案，基于身份的加密允许用户使用消息接收者的ID加密消息，基于属性的加密进一步允许用户基于消息接收者拥有的属性加密消息。使得只有某个属性约束（Policy）被满足时用户才能解密该消息。

这里“属性”是一个集合。例如，对于属性集合{A,B,C,D}\{A, B, C, D\}，发送者可以基于属性A∧BA \land B对消息进行加密，使拥有属性{A,C}\{A, C\}或者{A}\{A\}等的用户无法解密信息，而只有拥有属性QQ使{A,B}∈Q\{A, B\} \in Q的用户可以解密信息。

上面我们描述了一种将属性约束嵌入到密文中的加密方案，这种方案被称为Ciphertext-Policy ABE (CP-ABE)。

另一种加密方案是Key-Policy ABE (KP-ABE)，在这种方案下，发送者基于一个属性集合对消息进行加密，属性约束被嵌入到用户的私钥中。例如，发送者基于集合{A,B}\{A, B\}加密消息后，用户A∨CA \lor C可以解密消息，但用户A∧CA \land C不能解密消息。

Fuzzy-Identity Based Encryption

Fuzzy IBE是最早提出属性加密的方案。在Fuzzy IBE方案中，用户的身份是一个属性的集合ω∈U\omega \in \mathcal{U}，其中U\mathcal{U}是所有可能属性的集合。消息发送者可以使用任意的属性集合ω′∈U\omega' \in \mathcal{U}加密消息。对于给定的阈值dd，当且仅当∣ω∩ω′∣≥d|\omega \cap \omega'| \ge d时，用户才能解密消息，即用户必须持有dd个吻合的属性才能解密消息。

双线性对

对于素数阶的群G1,G2\mathbb{G}_1, \mathbb{G}_2，双线性对ee定义了一种映射G1×G1→G2\mathbb{G}_1 \times \mathbb{G}_1 \rightarrow \mathbb{G}_2，并且该映射具有如下性质：

  • 双线性：对于所有的a,ba, b，有e(ga,gb)=e(g,g)abe(g^a, g^b) = e(g, g)^{ab}

  • 非退化性：e(g,g)≠1e(g, g) \ne 1

其中gg为G1\mathbb{G}_1的生成元。当G1\mathbb{G}_1为加法群，G2\mathbb{G}_2为乘法群时，双线性对还可以表示为e(ag,bg)=e(g,g)abe(ag, bg) = e(g, g)^{ab}。

由于G1,G2\mathbb{G}_1, \mathbb{G}_2的阶为素数，它们是循环群。对于任意的s,t∈G1s, t \in \mathbb{G}_1，存在k1,k2k_1, k_2使s=gk1,t=gk2s = g^{k_1}, t = g^{k_2}。因此

e(a,st)=e(a,gk1+k2)=e(a,g)k1+k2=e(a,g)k1e(a,g)k2=e(a,gk1)e(a,gk2)=e(a,s)e(a,t)\begin{align} e(a, st) &= e(a, g^{k_1 + k_2}) \\ &= e(a, g)^{k_1 + k_2} \\ &= e(a, g)^{k_1}e(a, g)^{k_2} \\ &= e(a, g^{k_1})e(a, g^{k_2}) \\ &= e(a, s)e(a, t) \end{align}

我们可以看到，该结论与之前提到的双线性性质在循环群中是等价的。类似的，我们还有

  • e(st,a)=e(s,a)e(t,a)e(st, a) = e(s, a)e(t, a) （换成除法同样适用）

  • e(a,b)=e(b,a)e(a, b) = e(b, a)

Fuzzy IBE方案

Fuzzy IBE与传统IBE类似，都需要KGC的参与。该方案的组成部分如下：

  • KGC密钥生成：假设所有属性的集合为U\mathcal{U}，为了简单起见，取U\mathcal{U}为Zp∗\mathbb{Z}_p^*中的前∣U∣|\mathcal{U}|个元素，即1,2,...,∣U∣1, 2, ..., |\mathcal{U}|。e:G1×G1→G2e: \mathbb{G}_1 \times \mathbb{G}_1 \rightarrow \mathbb{G}_2是一个定义在阶为素数pp的群上的双线性对。

    • 从Zp\mathbb{Z}_p中随机取t1,...,t∣U∣,yt_1, ..., t_{|\mathcal{U}|}, y作为主密钥保密存储

    • 将T1=gt1,...,T∣U∣=gt∣U∣,Y=e(g,g)yT_1 = g^{t_1}, ..., T_{|\mathcal{U}|} = g^{t_{|\mathcal{U}|}}, Y = e(g, g)^y作为公开参数公开

  • 用户密钥生成：对于持有属性集合ω∈U\omega \in \mathcal{U}的用户（假设∣ω∣≥d|\omega| \ge d），KGC随机选取一个系数在Zp\mathbb{Z}_p中的d−1d - 1阶多项式qq使得q(0)=yq(0) = y。用户的私钥即为(Di)i∈ω,Di=gq(i)ti(D_i)_{i \in \omega}, D_i = g^{\frac{q(i)}{t_i}}。（注意我们这里能直接使用q(i),i∈ωq(i), i \in \omega是因为密钥生成阶段作出的假设U⊂Zp∗\mathcal{U} \subset \mathbb{Z}_p^*）

  • 加密：假设加密使用的属性集合为ω′\omega'，待加密消息M∈G2M \in \mathbb{G}_2。

    • 随机选取s∈Zps \in \mathbb{Z}_p

    • 计算E=(ω′,E′=MYs,{Ei=Tis}i∈ω′)E = (\omega', E' = MY^s, \{E_i = T_i^s\}_{i \in \omega'})作为密文

  • 解密： 当且仅当∣ω′∩ω∣≥d|\omega' \cap \omega| \ge d时，我们可以解密消息。 取S=ω′∩ω,∣S∣=dS = \omega' \cap \omega, |S| = d，记Δi,S\Delta_{i, S}为拉格朗日插值中点(i,q(i))(i, q(i))对应的系数，即

    Δi,S(x)=∏j∈S,j≠ix−xjxi−xj\Delta_{i, S}(x) = \prod_{j \in S, j \ne i} \frac{x - x_j}{x_i - x_j}

    （上式中xi=i,xj=jx_i = i, x_j = j） 将密文中的E′E'展开有：

    E′=MYs=Me(g,g)ysE' = MY^s = Me(g, g)^{ys}

    根据拉格朗日插值公式，我们有

    y=q(0)=∑i∈Sq(i)Δi,S(0)y = q(0) = \sum_{i \in S}q(i)\Delta_{i, S}(0)

    因此

    e(g,g)ys=e(g,g)∑i∈Sq(i)Δi,S(0)s=∏i∈Se(g,g)q(i)Δi,S(0)s=∏i∈Se(g,g)q(i)tistiΔi,S(0)=∏i∈Se(gq(i)ti,gsti)Δi,S(0)=∏i∈Se(Di,Ei)Δi,S(0)\begin{align} e(g, g)^{ys} &= e(g, g)^{\sum_{i \in S}q(i)\Delta_{i, S}(0)s} \\ &= \prod_{i \in S}e(g, g)^{q(i)\Delta_{i, S}(0)s} \\ &= \prod_{i \in S}e(g, g)^{\frac{q(i)}{t_i}st_i\Delta_{i, S}(0)} \\ &= \prod_{i \in S}e(g^{\frac{q(i)}{t_i}}, g^{st_i})^{\Delta_{i, S}(0)} \\ &= \prod_{i \in S}e(D_i, E_i)^{\Delta_{i, S}(0)} \\ \end{align}

因此消息M=E′/∏i∈Se(Di,Ei)Δi,S(0)M = E' / \prod_{i \in S}e(D_i, E_i)^{\Delta_{i, S}(0)}

我们可以看到，在上述方案中，KGC的主密钥和公共参数的大小随着属性取值空间∣U∣|\mathcal{U}|的增大而线性增大。这无疑限制了其应用场景。因此下面我们将介绍一个改进的Fuzzy IBE方案。

更大的属性空间

论文作者提供了另一种方案，该方案允许将Zp∗\mathbb{Z}_p^*作为其属性空间，但是加密使用的身份中的最大属性数量被限制为一个固定的值nn。

在这个更大的属性空间下，用户可以使用任意的字符串作为其属性，然后通过一个可靠的哈希函数H:{0,1}∗→Zp∗H: \{0, 1\}^* \rightarrow \mathbb{Z}_p^*将其映射到上述属性空间中。

该方案的组成部分如下：

  • KGC密钥生成：

    • 选择g1=gy,g2∈G1g_1 = g^y, g_2 \in \mathbb{G}_1。

    • 从G1\mathbb{G}_1中随机选取t1,...,tn+1t_1, ..., t_{n + 1}，定义N={1,...,n+1}N = \{1, ..., n + 1\}以及函数TT：

      T(x)=g2xn∏i=1n+1tiΔi,N(x)T(x) = g_2^{x^n}\prod_{i = 1}^{n + 1}t_i^{\Delta_{i, N}(x)}

      这里TT可以被看作某个nn阶多项式g2xngh(x)g_2^{x^n}g^{h(x)}的函数，其中h(i)=ki,gki=tih(i) = k_i, g^{k_i} = t_i。

    • 将yy作为主密钥，g1,g2,t1,...,tn+1g_1, g_2, t_1, ..., t_{n + 1}作为公开参数

  • 密钥生成：对于拥有身份ω\omega的用户

    • KGC随机选择一个d−1d -1阶多项式qq使得q(0)=yq(0) = y

    • 用户私钥分为两部分，分别为{Di}i∈ω,Di=g2q(i)T(i)ri\{D_i\}^{i \in \omega}, D_i = g_2^{q(i)}T(i)^{r_i}以及{di}i∈ω,di=gri\{d_i\}_{i \in \omega}, d_i = g^{r_i}。其中rir_i是从Zp\mathbb{Z}_p中随机选取的。

  • 加密：使用身份ω′\omega'加密消息M∈G2M \in \mathbb{G}_2的过程如下：

    • 随机选取s∈Zps \in \mathbb{Z}_p

    • 计算密文E=(ω′,E′=Me(g1,g2)s,E′′=gs,{Ei=T(i)s}i∈ω)E = (\omega', E' = Me(g_1, g_2)^s, E'' = g^s, \{E_i = T(i)^s\}_{i \in \omega})

  • 解密：由于

    e(g1,g2)s=e(gy,g2)s=e(gs,g2)y=e(E′′,g2)∑i∈Sq(i)Δi,S(0)=∏i∈Se(E′′,g2q(i))Δi,S(0)=∏i∈S(e(E′′,Di)e(E′′,T(i)ri))Δi,S(0)=∏i∈S(e(E′′,Di)e(gri,T(i)s))Δi,S(0)=∏i∈S(e(E′′,Di)e(di,Ei))Δi,S(0)\begin{align} e(g_1, g_2)^s &= e(g^y, g_2)^s \\ &= e(g^s, g_2)^y \\ &= e(E'', g_2)^{\sum_{i\in S}q(i)\Delta_{i, S}(0)} \\ &= \prod_{i \in S}e(E'', g_2^{q(i)})^{\Delta_{i, S}(0)} \\ &= \prod_{i \in S}(\frac{e(E'', D_i)}{e(E'', T(i)^{r_i})})^{\Delta_{i, S}(0)} \\ &= \prod_{i \in S}(\frac{e(E'', D_i)}{e(g^{r_i}, T(i)^{s})})^{\Delta_{i, S}(0)} \\ &= \prod_{i \in S}(\frac{e(E'', D_i)}{e(d_i, E_i)})^{\Delta_{i, S}(0)} \end{align}

    我们可以得到M=E′/∏i∈S(e(E′′,Di)e(di,Ei))Δi,S(0)=E′∏i∈S(e(di,Ei)e(E′′,Di))Δi,S(0)M = E' / \prod_{i \in S}(\frac{e(E'', D_i)}{e(d_i, E_i)})^{\Delta_{i, S}(0)} = E'\prod_{i \in S}(\frac{e(d_i, E_i)}{e(E'', D_i)})^{\Delta_{i, S}(0)}

TODO: 这是怎么构造出来的？

参考资料