属性加密入门

简介

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

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

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

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

Fuzzy-Identity Based Encryption

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

双线性对

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

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

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

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

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

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

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

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

Fuzzy IBE方案

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

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

  • 从$\mathbb{Z}_p$中随机取$t_1, ..., t_{|\mathcal{U}|}, y$作为主密钥保密存储

  • 将$T_1 = g^{t_1}, ..., T_{|\mathcal{U}|} = g^{t_{|\mathcal{U}|}}, Y = e(g, g)^y$作为公开参数公开

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

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

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

  • 计算$E = (\omega', E' = MY^s, \{E_i = T_i^s\}_{i \in \omega'})$作为密文

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

  $$\Delta_{i, S}(x) = \prod_{j \in S, j \ne i} \frac{x - x_j}{x_i - x_j}$$

  （上式中$x_i = i, x_j = j$） 将密文中的$E'$展开有：

  $$E' = MY^s = Me(g, g)^{ys}$$

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

  $$y = q(0) = \sum_{i \in S}q(i)\Delta_{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' / \prod_{i \in S}e(D_i, E_i)^{\Delta_{i, S}(0)}$

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

更大的属性空间

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

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

该方案的组成部分如下：

• KGC密钥生成：

  • 选择$g_1 = g^y, g_2 \in \mathbb{G}_1$。

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

    $$T(x) = g_2^{x^n}\prod_{i = 1}^{n + 1}t_i^{\Delta_{i, N}(x)}$$

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

  • 将$y$作为主密钥，$g_1, g_2, t_1, ..., t_{n + 1}$作为公开参数

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

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

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

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

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

  • 计算密文$E = (\omega', E' = Me(g_1, g_2)^s, E'' = g^s, \{E_i = T(i)^s\}_{i \in \omega})$

• 解密：由于

  $$\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' / \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: 这是怎么构造出来的？

参考资料

• https://crypto.stackexchange.com/questions/17893/what-is-attribute-based-encryption/17894#17894

• Sahai2005 - Fuzzy Identity-Based Encryption