2024-07-16 2024-07-16 6241 字 13 分钟

- 密码学

#include <iostream>
using namespace std;
int main(){
    cout << "你可以在这里编写，测试代码!" << endl;
    cout << "目前只支持c++,java和python!" << endl;
    cout << "点击右上角切换语言!" << endl;
    return 0;
}

ABE及其应用

什么是基于属性的加密

正式描述

基于属性加密（ABE）最先在 2005年由 Waters 在论文《Fuzzy Identity-Based Encryption》中提出，并在2006年的论文中用于细粒度的访问控制，被看作是最具前景的支持细粒度访问的加密原语。ABE实现了一对多的加解密。不需要像基于身份加密(IBE)一样，每次解密都必须知道接收者的身份信息，在ABE中它把身份标识被看做是一系列的属性。当用户拥有的属性超过加密者所描述的预设阈值时，用户是可以解密的。

基于属性加密主要分为两大类：密文策略的属性加密（CP-ABE）和密钥策略的属性加密（KP-ABE）。在CP-ABE中密文和加密者定义的访问策略相关联，密钥则是和属性相关联；在KP-ABE中密文则是和属性相关，而密钥与访问策略相关联。我们将在下文对他们分别进行介绍。

通俗描述

基于属性的加密实际上实现了这样一个功能，加密者可以选择一组属性并利用这组属性对一个消息进行加密，只有接收者满足这些属性的指定数目时才能解密密文。例如：Alice 选择三个属性"安徽大学"，“计算机学院”，“老师"去加密消息 m 得到密文 c ，那么ABE可以要求至少拥有这三个属性中的两个才能解密 c 。

ABE方案

形式化定义

Setup：系统初始化阶段，输入系统安全参数，产生相应的公共参数 MPK 和系统主密钥 msk；

KeyGen：密钥生成，解密用户向系统提交自己的属性，获得属性相关联的用户密钥（SK）；

Enc：加密，数据拥有者对数据进行加密得到密文（CT）并发送给用户或者发送到公共云上；

Dec：解密，解密用户获得密文，用自己的密钥SK进行解密。

ABE实例

一种直观的构造

Setup：

令属性全集为 $U=\{1,2,…,n\}$ 这里 U 中的每个元素可以映射到一个属性，例如：1 表示"国家”,2 表示"省份"，3表示"性别"等等。
生成 n 个随机数 $t_1 \in_R Z_p ,…,t_n \in_R Z_p$ , 计算 $T_1 = g^{t_1} ,…,T_n = g^{t_n}$
生成随机数 $y\in_R Z_p$ 计算 $Y=e(g,g)^y$
则，系统私钥为 $msk=(t_1,…,t_n,y)$ , 系统公钥为 $MPK=(T_1,…,T_n,Y)$.

KeyGen：

假设在这个系统中，加密方要求解密者至少需要拥有 t 个加密使用的属性才能解密密文，则他首先生成一个 t-1 阶的多项式 $q(x) = y + a_1x + … + a_{t-1}x^{t-1}$ , 然后计算第 i 个属性对应的解密密钥 $D_i=g^{q(i)/t_i}$, 其中 $ i\in U $，若某用户拥有一个属性，则将该属性对应的密钥 $D_i$ 分发给该用户。

Encryption：

假设一个用户想要使用一组属性 $ w’ = \{ i_1,…,i_n \}_{i\in U}$ 对消息 m 进行加密，那么她执行以下步骤：

生成随机数 $s\in_R Z_p$ 并计算 $C’= m \cdot Y^s$ 和 $\{ C_i = T_i^s \}_{i\in {w’}}$
令最终的密文 $C=(w’,C’,\{C_i\}_{i\in w’})$ 。

Decryption：

解密者在得到了使用属性集 $w’$ 加密的密文 c 之后，如果自己有不少于 t 条属性属于 $w’$ ，那么它可以选择任意包含 t 个属性的子集 S，然后计算下式解密 c 得到消息 m 。

$$m = C’ / \prod_{i\in S}e(D_i,C_i)^{L_i(0)}, 其中 \ \ L_i(x)=\prod_{i=1}^{t} \frac{i}{j-i}$$

正确性证明

上述解密的正确性很容易证明，具体过程如下： $$\begin{align} C’ / \prod_{i\in S}e(D_i,C_i)^{L_i(0)} &= m\cdot e(g,g)^{sy}/ \prod_{i\in S}e(g^{q_i/t_i},g^{s\cdot t_i})^{L_i(0)} \\ &= m\cdot e(g,g)^{sy}/ \prod_{i\in S}e(g,g)^{s\cdot q(i)\cdot L_i(0)} \\ &= m\cdot \frac{e(g,g)^{s\cdot y}}{e(g,g)^{s\cdot \sum_{i=1}^{t} q(i)\cdot L_i(0)}} \\ &= m \end{align}$$

Large Universe Construction

在上述方案中，属性全集 $U=\{1,2,…,n\}$, U 中每个元素 i 对应于一个属性，这导致需要额外存储一个 U 中元素与属性的对应关系表 Rel。除此之外，上述方案中的公共参数的大小与属性集合的大小成正比。现在我们介绍一个优化的方案，使得属性全集 $U = Z_p $,并且公共参数的大小只与描述一个实体需要的属性集大小有关。比如，根据"黑洞无毛定理",描述一个静态黑洞只需要三个物理量(质量，角动量，电荷)，那么优化后的ABE只需要约为 3 个公共参数。除此之外，将 U 的范围扩展到 $Z_p$ 之后，可以使用哈希函数 $H:{0,1}^* -> Z_p $ 来将任意属性，包括字符串映射到 U 中，从而避免了存储 Rel 表。

Setup：

令属性全集为 $U = Z_p$ 。生成 $y\in_RZ_p$ , 计算 $g_1=g^y,g_2\in_R G_1$ 其中 g 是 $G_1$ 的生成元。
生成 n+1 个随机数 $t_1 \in_R Z_p ,…,t_n,t_{n+1} \in_R G_1$ , 令 $N = {1,2,…,n+1}$
定义函数 $T(x)=g_2^{x^n}\cdot \prod_{i=1}^{n+1}t_i^{L_i(x)}$
则，系统私钥为 $msk = y$ , 系统公钥为 $MPK=(g_1,g_2,t_1,…,t_{n+1})$.

KeyGen：

假设在这个系统中，要求解密者至少需要拥有 t 个加密使用的属性才能解密密文，则首先生成一个 t-1 阶的多项式 $q(x) = y + a_1x + … + a_{t-1}x^{t-1}$ . 生成随机数 $r_i\in_R Z_p , i\in Z_p^* $ , 然后计算第 i 个属性对应的解密密钥 $d_i=g^{r_i}$ 和 $D_i=g_2^{q(i)}\cdot T(i)^{r_i}$, 其中 $ i\in U $，若某用户拥有一个属性，则将该属性对应的密钥 $D_i$ 分发给该用户。

Encryption：

假设一个用户想要使用属性 $ w’ = \{ i_1,…,i_n \}_{i\in U}$ 对消息 m 进行加密，那么她执行以下步骤：

生成随机数 $s\in_R Z_p$ 并计算 $C’= m \cdot e(g_1,g_2)^s$ , $C’’=g^s$ 和 $\{ C_i = T(i)^s \}_{i\in {w’}}$
令最终的密文 $C=(w’,C’,C’’,\{C_i\}_{i\in w’})$ 。

Decryption：

$$m = C’ \cdot \prod_{i\in S}(\frac{e(d_i,C_i)}{e(D_i,C’’)})^{L_i(0)}, 其中 \ \ L_i(x)=\prod_{i=1}^{t} \frac{i}{j-i}$$

正确性证明

上述解密的正确性很容易证明，具体过程如下： $$\begin{align} C’ \cdot \prod_{i\in S}(\frac{e(d_i,C_i)}{e(D_i,C’’)})^{L_i(0)} &= m\cdot e(g_1,g_2)^s \cdot \prod_{i\in S}(\frac{e(g^{r_i},T(i)^s)}{e(g_2^{q_i},g^s)e(T(i)^{r_i},g^s)})^{L_i(0)} \\ &= m\cdot e(g,g_2)^{y\cdot s} \cdot \prod_{i\in S} \frac{1}{e(g_1,g_2)^{q(i)\cdot s\cdot L_i(0)}} \\ &= m\cdot e(g,g_2)^{y\cdot s} \cdot \frac{1}{e(g_1,g_2)^{s\cdot \sum_{i=1}^{t} q(i)\cdot L_i(0)}} \\ &= m\cdot e(g,g_2)^{y\cdot s} \cdot \frac{1}{e(g_1,g_2)^{s\cdot y}} \\ &= m \end{align}$$

基于ABE的细粒度访问控制

什么是细粒度的访问控制

正式描述

细粒度访问控制基于多个多个条件、权限来决定一个用户是否拥有对资源的访问权。与之相对的是粗粒度的访问控制，它一般基于单个因素（即角色或权限）决定用户是否拥有资源的访问权。细粒度授权等同于基于属性的访问控制（ABAC）或基于策略的访问控制，而粗粒度访问控制等同于基于角色的访问控制（RBAC）。

细粒度的访问控制通过多个条件或属性为用户授权，而粗粒度的访问控制通过单个条件或属性为用户授权。举个通俗的例子来说，粗粒度访问控制是基于角色的，它规定某个人可以访问哪些文件，而细粒度访问控制是基于文件的，它规定符合哪些条件的人可以访问某个文件。

通俗描述

在RBAC中，规定某个角色可以访问哪些文件，例如：董事长可以访问文件 A，B，C ；经理可以访问文件A，B ；而员工只能访问文件A。 在ABAC中，规定某个文件可以被那些人访问，例如：文件C 必须是 “A公司"中的"董事长"才能访问，而文件B 只要是"A公司中"的"经理"即可访问，文件A则只要是"A公司"的"员工"都能访问。

使用基于RBAC的访问控制方法实现密文存储时，一般使用访问控制表(ACL)去管理用户的权限，它面临维护困难、不灵活或者无法应对复杂授权需求等挑战。在一个大型企业中，可能有数千个员工和数百个不同的部门或项目组，每个员工可能需要访问多个不同的文件或系统资源。使用传统的ACL，管理员可能需要为每个文件或资源设置复杂的权限列表，这不仅管理起来困难，而且容易出现安全漏洞。 而使用基于ABAC的访问控制方法，则可以使用属性{“A公司”,“董事长”,“经理”,“员工”}对文件A，B，C分别进行加密。使得拥有相应属性的人才能解密相应的文件。并且当文件和属性变化时，可以以较低的开销对访问控制策略进行修改。

细粒度的访问控制有什么用

细粒度的访问控制可以根据资源的特征、用户的属性定义精细灵活的访问控制策略，并可根据环境动态的调整访问策略，在复杂的控制系统中更有效。它可以：

解决复杂的访问控制需求：

在一个大型企业中，可能有数千个员工和数百个不同的部门或项目组，每个员工可能需要访问多个不同的文件或系统资源。使用传统的ACL，管理员可能需要为每个文件或资源设置复杂的权限列表，这不仅管理起来困难，而且容易出现安全漏洞。ABE可以根据员工的角色、部门或其他属性，动态地分配和调整访问权限，避免了ACL所面临的管理复杂性和错误风险。
实现跨组织的数据共享：

在跨多个组织进行数据共享时，例如在医疗保健行业或跨国公司中，传统的ACL可能无法有效地管理不同组织之间的权限控制需求。ABE允许根据数据的敏感性和用户的属性（如所属组织、授权级别等）来动态地控制数据的访问权限，而无需为每个组织设置独立的ACL。
完成动态访问控制调整：

在动态环境中，例如云计算环境中的虚拟机实例，用户需要根据需求访问不同的资源和服务。传统ACL可能无法实时调整以满足这种动态性，而ABE可以根据用户的临时属性或临时授权来动态地调整访问控制策略，保证了资源的安全性和灵活性。

如何实现细粒度的访问控制

这里介绍 Waters 于 2006 年在论文 KP-ABE中提出的第一个基于属性加密的细粒度访问控制方案，作者在论文中详细介绍了如何定义访问策略，如何根据访问策略实现细粒度的访问控制。

预备知识

Shamir秘密共享

为了分发秘密，秘密分发者首先随机生成 $ t - 2 $ 个小于 $ p $ 的随机数 $ a_{1}, a_{2},…, a_{t - 1} $ 并构造一个 t-1 阶的多项式 $ f (x) = a_0 + a_{1} x + \cdots + a_{t-1} x^{t-1} \pmod p $ ，其中 $ f (0) = a_{0} = s $ 是要保护的秘密， $ p $ 是一个大素数，且 s < p 。秘密分发者随机选取 $ n $ 个互不相同的整数 $ x_{1}, x_{2}, \cdot, x_{n} $ 并将 $ n $ 个整数代入多项式函数 $f(x)$得到 $ n $ 个值 $ y_1 = f (x_1)$, $ y_2 = f(x_2)$,…, $y_{n} = f (x_{n}) $ , 然后将计算得到的 $ n $ 个坐标 $(x_i,y_i)$ 分别发给 $ n $ 各参与方并销毁 $ f (x) $，即第 $ i $ 个参与方获得 $ (x_{i}, y_{i}) $ 。
为了恢复秘密，收集到 t 个参与者的份额、也就是 t 个点的坐标之后，将得到的 t 个点利用拉格朗日插值法计算出拉格朗日插值多项式，也就是 $f(x)$ , 然后计算 $f(0)=s$ 得到秘密值。

访问控制树

为了更好的描述访问策略，我们引入访问控制树这个数据结构。假设 T 是一个表示访问结构的访问控制树，那么在 T 中，每个非叶节点(用 x 表示)表示一个阈值门，由它的子节点和一个阈值描述。假设 $num_x$ 是节点 x 的子节点数量，$k_x$ 是它的阈值，则 $0 < k_x < num_x$ 。容易看出，当 $k_x = 1$ 时，节点表示 OR 门，当 $k_x = num_x$ 时，节点表示 and 门，否则节点表示阈值门。

如何判断拥有一组属性的用户是否满足访问树呢？我们给出方法如下：设 T 是根为 r 的访问控制树，用 $T_x$ 表示根为 x 的 T 的子树，因此 $T = T_r$ 。如果一组属性 γ 满足访问树 $T_x$，则记为 $T_x(γ) = 1$。我们递归地计算 $T_x(γ)$ 如下，如果 x 是一个非叶节点，计算节点 x 的所有子节点 $x’$ 的 $T_x’(γ)$。当且仅当至少 $k_x$ 个子节点返回 1 时，$T_x(γ)$ 返回1。如果 x 是叶节点，则 $T_x(γ)$ 返回 1 当且仅当 $att(x)\in γ$。如果 $T_r(γ)=1$, 我们说这组属性 $γ$ 满足访问控制树。

为了方便使用访问树，我们定义 parent(x) 表示树中节点 x 的父节点。当 x 是叶节点时，函数 att(x) 表示叶节点 x 对应的属性。访问树 T 对每个节点的子节点进行编号，最简单的编号方式是将其子节点从左到右依次编号为 $1,2,…,num_x$ ，函数 ind(x) 返回 x 的父节点对 x 的编号。值得注意的是，子节点的编号方式可以是任意的，只要保证同一节点的子节点编号中没有重复即可。

访问控制树的图示如下：

具体构造

一种直观构造

这篇文章实际上是 Waters 对其 2005 年提出的"基于属性加密(ABE)“的应用，方案几乎没有大的变化。

Setup：

令属性全集为 $U=\{1,2,…,n\}$ 这里 U 中的每个元素可以映射到一个属性，例如：1 表示"国家”,2 表示"省份”，3表示"性别"等等。
生成 n 个随机数 $t_1 \in_R Z_p ,…,t_n \in_R Z_p$ , 计算 $T_1 = g^{t_1} ,…,T_n = g^{t_n}$
生成随机数 $y\in_R Z_p$ 计算 $Y=e(g,g)^y$
则，系统私钥为 $msk=(t_1,…,t_n,y)$ , 系统公钥为 $MPK=(T_1,…,T_n,Y)$.

Encryption：

假设一个用户想要使用属性 $ \gamma = \{ i_1,…,i_n \}_{i\in U}$ 对消息 m 进行加密，那么她执行以下步骤：

生成随机数 $s\in_R Z_p$ 并计算 $C’= m \cdot Y^s$ 和 $\{ C_i = T_i^s \}_{i\in {\gamma}}$
令最终的密文 $C=(\gamma,C’,\{C_i\}_{i\in \gamma})$ 。

KeyGen：

该算法输出一个密钥，当且仅当 $T(γ) = 1$ 时，用户能够解密在一组属性 $γ$ 下加密的消息。算法的过程如下。首先为树 T 中的每个节点 x (包括叶子)选择一个多项式 $q_x$。从根节点 r 开始，以自顶向下的方式选择这些多项式。对于树中的每个节点x，设置随机多项式 $q_x$ 的阶数 $d_x$ 比该节点的阈值 $k_x$ 小 1，即 $d_x = k_x - 1$ 。现在，对于根节点 r，令 $q_r(0) = y$并随机选择多项式 $d_r$ 个随机数作为 $q_r(x)$的系数得到$q_r(x) = y + a_1x + … + a_{d_r}x^{d_r}$。对于其他任意节点x，设 $q_x(0) = q_{parent(x)} (ind(x))$，随机选择其他 $d_x$ 个随机数，生成多项式 $q_x(x)$。（可参考上面的访问控制树看）

一旦确定了多项式，对于每个叶节点 x，我们计算其对应属性的解密密钥： $D_i=g^{q_x(0)/t_i}$ , 其中 $i\in att(x) $ 若某用户拥有一个属性，则将该属性对应的密钥 $D_i$ 分发给该用户。

Decryption：

为了清楚的介绍解密算法，我们首先定义算法 DecrypNode(C,D,x) , 该算法的定义如下：

当 x 是叶节点时， $$DecrypNode(C,D,x)= \begin{cases} e(D_x,C_i)=e(g^{q_x(0)/t_i},g^{s\cdot t_i})=e(g,g)^{s\cdot q_x(0)},&if \ i\in \gamma \\ \perp , &otherwise \end{cases}$$
当 x 是非叶节点时，我们设他的子节点为 z ，并且定义 $F_z = DecrypNode(C,D,z)$ 。假设 $S_x$ 是节点 x 的一个大小为 $k_x$ 的子节点集合使得 $F_z \neq \perp$。如果没有这样的集合，返回 $\perp$ ,否则计算：

有了上述定义，我们只需要在根节点调用算法得 $ DecryptNode (E;D;r) = e(g,g)^{ys} = Y^s$, 然后计算 $m=C’/Y^s$。

正确性证明

上述解密的过程是正确的，首先我们知道： $$\begin{align} C’ / \prod_{i\in S}e(D_i,C_i)^{L_i(0)} &= m\cdot e(g,g)^{sy}/ \prod_{i\in S}e(g^{q_i/t_i},g^{s\cdot t_i})^{L_i(0)} \\ &= m\cdot e(g,g)^{sy}/ \prod_{i\in S}e(g,g)^{s\cdot q(i)\cdot L_i(0)} \\ &= m\cdot \frac{e(g,g)^{s\cdot y}}{e(g,g)^{s\cdot \sum_{i=1}^{t} q(i)\cdot L_i(0)}} \\ &= m \end{align}$$

Decryption中的解密过程实际上就是把上式中的 q(i) 作为其子节点的秘密值，通过嵌套秘密共享的方式依次恢复。

Large Universe Construction

在上述方案中，属性全集 $U=\{1,2,…,n\}$, U 中每个元素 i 对应于一个属性，这导致需要额外存储一个 U 中元素与属性的对应关系表 Rel。除此之外，上述方案中的公共参数的大小与属性集合的大小成正比。现在我们介绍一个优化的方案，使得属性全集 $U = Z_p^* $,并且公共参数的大小只与描述一个实体需要的属性集大小有关。比如，根据"黑洞无毛定理",描述一个静态黑洞只需要三个物理量(质量，角动量，电荷)，那么优化后的ABE只需要约为 3 个公共参数。除此之外，将 U 的范围扩展到 $Z_p$ 之后，可以使用哈希函数 $H:{0,1}^* -> Z_p $ 来将任意属性，包括字符串映射到 U 中，从而避免了存储 Rel表。

Setup：

令属性全集为 $U = Z_p$ 。生成 $y\in_RZ_p$ , 计算 $g_1=g^y,g_2\in_R G_1$ 其中 g 是 $G_1$ 的生成元。
生成 n+1 个随机数 $t_1 \in_R Z_p ,…,t_n,t_{n+1} \in_R G_1$ , 令 $N = {1,2,…,n+1}$
定义函数 $T(x)=g_2^{x^n}\cdot \prod_{i=1}^{n+1}t_i^{L_i(x)}$
则，系统私钥为 $msk = y$ , 系统公钥为 $MPK=(g_1,g_2,t_1,…,t_{n+1})$.

Encryption：

假设一个用户想要使用属性 $ w’ = \{ i_1,…,i_n \}_{i\in U}$ 对消息 m 进行加密，那么她执行以下步骤：

生成随机数 $s\in_R Z_p$ 并计算 $C’= m \cdot e(g_1,g_2)^s$ , $C’’=g^s$ 和 $\{ C_i = T(i)^s \}_{i\in {w’}}$
令最终的密文 $C=(w’,C’,C’’,\{C_i\}_{i\in w’})$ 。

KeyGen：

一旦确定了多项式，对于每个叶节点 x，我们计算其对应属性的解密密钥：

生成随机数 $r_x\in_R Z_p$ , 然后计算该节点对应的属性解密密钥 $R_x=g^{r_x}$ 和 $D_x=g_2^{q(0)}\cdot T(i)^{r_x}$, 其中 $ i = att(x) $，若某用户拥有一个属性，则将该属性对应的密钥 $(R_x,D_x)$ 分发给该用户。

Decryption：

解密和上面的同理，敲不动了，直接贴图：

私钥委托

对于一个已有的访问控制树，可以对其进行以下类型的修改。详情参考原论文。之所以不重构一个访问控制树是因为对访问控制树进行以下修改的开销低于直接重构一颗树，并且拥有一定权限的人可以将权限收紧之后派发给其他人。

1. 添加平凡门

2. 修改(t,n)门到(t+1,n)门

3. 修改(t,n)门到(t,n-1)门

4. 修改(t,n)门到(t+1,n+1)门

5. 密钥的重随机

应用

审计日志
定向广播加密

← Cuckoo过滤器

秘密共享 →