用于加密数据细粒度访问控制的属性加密

1.概述

KP-ABE 基于密钥策略的属性加密

每个密文都由加密器用一组描述性属性标记。 每个私钥都与一个访问结构相关联，该结构指定密钥可以解密哪种类型的密文。

秘密共享方案

该方案指定一组各方必须合作以重建秘密。 例如，可以指定一种树访问结构，其中内部节点由 AND 和 OR 门组成，叶子由不同的参与方组成。 满足树的任何一组方都可以重建秘密。

与秘密共享方案的区别

每个用户的密钥都与树访问结构相关联，其中叶子与属性相关联。如果与密文相关联的属性满足密钥的访问结构，则用户能够解密密文。我们的设置和秘密共享方案之间的主要区别在于，虽然秘密共享方案允许不同方之间的合作，但在我们的设置中，这是明确禁止的。 例如，如果 Alice 拥有与访问结构“X AND Y”相关联的密钥，而 Bob 拥有与访问结构“Y AND Z”相关联的密钥，我们不希望他们能够解密其唯一属性的密文通过串通Y。

允许任何拥有访问结构 X 的密钥的用户导出访问结构 Y 的密钥，当且仅当 Y 比 X 更严格。

2.相关工作

细粒度访问控制 Fine-grained Access Control

细粒度的访问控制系统有助于向一组用户授予不同的访问权限，并允许灵活地指定单个用户的访问权限。

数据以加密形式存储在服务器上，同时允许不同的用户根据安全策略解密不同的数据。 这有效地消除了依赖存储服务器来防止未经授权的数据访问的需要。

秘密共享方案 Secret-sharing schemes (SSS)

秘密共享方案 (SSS) 用于在多方之间分配秘密。 提供给一方的信息称为该方的（秘密的）份额 share。 每个 SSS 都实现了一些访问结构，该结构定义了各方能够通过使用他们的份额share来重建秘密的集合。

在 SSS 中，可以指定一种树访问结构，其中内部节点由 AND 和 OR 门组成，叶子由不同的参与方组成。 满足树的任何一组参与方都可以聚集在一起并重建秘密。 因此，在 SSS 中，不仅允许而且需要不同用户（或各方）之间的勾结。

在我们的构造中，每个用户的键都与树访问结构相关联，其中叶子与属性相关联。 如果与密文关联的属性满足密钥的访问结构，则用户能够解密密文。 在我们的方案中，与 SSS 相反，用户不应以任何有意义的方式串通。

基于身份的加密与扩展 Identity-Based Encryption and Extensions

Fuzzy Identity-Based Encryption (FIBE) 基于模糊身份的加密

如果消息使用一组属性 ω' 加密，则一组属性 ω 的私钥可以解密该消息，当且仅当 |ω ∩ω'| ≥ d，其中 d 在设置时间内是固定的。因此，FIBE 实现了容错，使其适用于生物识别。但由于 FIBE 的主要目标是容错，因此唯一支持的访问结构是阈值门，其阈值在设置时固定。因此它对数据访问控制的适用性有限。

我们开发了一种更丰富的基于属性的加密类型。 不同用户的私钥可能与不同的访问结构相关联。 我们的结构支持包括阈值门树

在内的各种各样的访问结构。

3.背景

3.1 KP-ABE的安全性定义

访问结构

设 P=\{P_1,P_2,...,P_n\} 表示参与者的集合，令 2^p=2^{\{P_1,P_2,...,P_n\}}=\{A|A\subseteq\{P_1,P_2,..,P_n\}\} 。集合 A\subseteq 2^P 是单调的，当且仅当任意子集B,C\subseteq P，若 B\in A,B\subseteq C，则 C\in A。

若 A\subseteq 2^{\{P_1,P_2,...,P_n\}}\backslash \{\varnothing\} 且单调，则称 A 是一个访问结构。若集合 D\in A 称 D 为授权集，否则为非授权集。

注: CP-ABE中, 属性就是参与者, 所以满足密文访问结构的属性集合, 就是定义的授权集. 通常只考虑单调访问结构

CP-ABE算法

设置 Setup 随机算法，除了隐式安全参数外不接受任何输入。输出公共参数 PK 和主密钥 MK。

加密 随机算法，输入消息 m、一组属性 γ 和公共参数 PK ，输出密文 E。

密钥生成 随机算法，输入访问结构 A、主密钥 MK 和公共参数 PK ，输出一个解密密钥 D。

解密 输入在属性集 γ 下加密的密文 E、访问控制结构 A 的解密密钥 D 和公共参数 PK。如果γ∈A，则输出消息M。

ABE 方案的安全性

定义了一个选择集模型，用于证明基于选择明文攻击的属性的安全性。

Init 敌手声明他希望受到挑战的属性集 γ。

Setup 挑战者运行 ABE 的 Setup 算法，并将公开参数提供给敌手。

阶段 1 允许敌手为许多访问结构 A_j 发出私钥查询，其中所有 j 的 γ \notin A_j。

challenge 敌手提交两个等长的消息 M_0 和 M_1。 挑战者抛出一个随机硬币 b，并用 γ 加密 M_b。 密文被传递给对手。

阶段 2 重复阶段 1。

Guess 敌手输出对 b 的猜测 b'。敌手 A 在该博弈中的优势定义为 Pr[b' = b] − \frac{1}{2}

定义 如果所有多项式时间对手在 Selective-Set 博弈中最多具有可忽略的优势，则基于属性的加密方案在 Selective-Set 安全模型中是安全的。

3.2 双线性映射 Bilinear Maps

设 G1 和 G2 是素数阶为 p 的两个乘法循环群。 设 g 是 G1 的生成器，e 是双线性映射，e : G1 ×G1 → G2。 双线性映射 e 具有以下性质：

1. 双线性：对所有的 u,v\in G_1,a,b\in Z_P ，均有 e(u^a,v^b)=e(u,v)^{ab}
2. 非退化性：e(g,g)\neq 1
3. 可计算性：G1 中的群操作和双线性映射 e : G1 ×G1 → G2 都是可有效计算的

3.3 决策性双线性BDH假设

随机选择 a, b, c, z \in Z_p，g 是 G1 的生成器。 决策 BDH 假设是概率多项式时间算法 \mathcal{B} 可以区分元组 (A = g^a, B = g^b, C = g^c, e(g, g)^{abc}) 和元组 (A = g^a , B = g^b, C = g^c, e(g, g)^z) 的优势可忽略不计。 \mathcal{B}的优势是

3.4 线性秘密共享方案

参考：https://blog.csdn.net/ping802363/article/details/77900273

Monotone Span Program

没太看懂，有时间读一下引用的论文。

4.访问树的构造

4.1 访问树 access tree \mathcal{T}

access tree \mathcal{T}

令 \mathcal{T} 为代表访问结构的树。树的每个非叶子节点代表一个门限门。num_x 是 x 节点的孩子节点个数，k_x 是其阈值，则0 <kx≤numx。当 k_x = 1 时，阈值门是“或”门，而当 kx = num_x 时，它是“与”门。树的每个叶子节点 x 由属性和阈值k_x = 1来描述。

定义函数 parent(x)表示树中节点 x 的父节点。定义函数 att(x) 表示 x 是叶子节点且与 x 的属性关联。访问树 \mathcal{T} 还定义了每个节点的子节点之间的排序，即一个节点的子节点从 1 到 num 编号。定义函数 index(x)返回与节点 x 关联的数字。其中 index 以任意方式唯一地分配给给定密钥的访问结构中的节点。

Satisfying an access tree

设 \mathcal{T} 为根为 r 的访问树。 用 \mathcal{T_x} 表示以节点 x 为根的 \mathcal{T} 的子树。 因此 \mathcal{T} 与 \mathcal{T_r} 相同。 如果一组属性 y 满足访问树 \mathcal{T_x}，我们将其表示为 \mathcal{T_x}(y)=1。我们递归计算 \mathcal{T_x}(y) 如下。 如果 x 是非叶节点，则为节点 x 的所有子节点 x' 计算 \mathcal{T_{x'}(y)}。 当且仅当至少 k_x 个子节点返回 1 时，\mathcal{T}_x(y) 返回 1。如果 x 是叶节点，当且仅当 att(x)\in y 则 T_x(y) 返回 1 。

4.2 构造

G_1 是一个阶为素数 p 的乘法循环群，g 是群的一个生成元，e:G_1 \times G_1 \rightarrow G_2 表示双线性映射，k 是决定群大小的安全参数。

定义拉格朗日系数：\triangle_{i,s}(x)=\displaystyle\prod_{j\in S,j\neq i}\frac{x-j}{i-j} ，其中 i\in Z_p ，S 是属于 Z_p 的成员集。所有属性的集合为 U 。

初始化 Setup 定义属性 \mathcal{U}=\{1,2,...,n\} 。 现在，对于每个属性 i \in \mathcal{U}，从 Z_p 中随机均匀地选择一个数字 t_i。 最后，在 Z_p 中随机均匀地选择 y。 公开的公共参数 PK 是 T_1=g^{t_1},...,T_{|\mathcal{U}|}=g^{t|\mathcal(u)|},Y=e(g,g)^y 。主密钥 MK = t_1,...,t_{|\mathcal{u}|},y

加密 Encryption(M, γ,PK) 要加密信息 m\in G_2 ，密文对应的属性集为 γ ，选取随机值 s\in Z_p ，产生密文为 E=( γ,E'=MY^s,\{E_i=T_i^s\}_{i\in γ})

密钥产生算法 Key Generation(T,MK) 该算法输出一个密钥，当且仅当 T(γ) = 1 时，该密钥使用户能够解密在一组属性 γ 下加密的消息。密钥产生的过程如下：访问数 T ，根节点为 r，每个非叶子节点 x 都有一个门限值 k_x。而每个叶子节点都对应一个属性。从根节点 r 开始，自上而下为树 T 中的非叶子节点 x 选择一个 d_x=k_x-1 阶多项式 q_x，根对于根节点则选择q_r(0)=y，其他内部节点的多项式要满足 q_x(0)=q_{parent(x)}(index(x)) 。用户的属性私钥从树中叶子节点抽取得到，为D_x=g^{\frac{q_x(0)}{t_i}} \ \ \ \ \ \ \ i=att_{(x)} ,秘密值的集合是解密密钥。

解密算法 Decryption(E, D) 定义一个递归算法 DecryptNode(E, D, x) ，输入密文 E= (γ, E′,\{E_i\}_{i∈γ}) ，用户私钥 D ， x 是树上的一个节点。如果 x 是叶子节点，令 i=att(x)

如果 x 是非叶子节点，对 x 的所有节点 z ，设 F_z=DecryptNode(E,D,z) 。令 S_x 为一个由 x 的任意 k_x 个子节点组成的集合，这些节点要满足 F_z \neq ⊥ 。如果不存在这样的集合，则算法输出为空，否则进行下一步运算：令 i=index(x)\ \ \ S_x'=\{index(z):z\in S_x\}

函数 DecryptNode，解密算法简单地调用树根上的函数。 当且仅当密文满足树， DecryptNode(E, D, r) = e(g, g)^{ys} = Y^s 。 因为， E′ = MY^s 解密算法简单地除掉 Y^s 并恢复消息 M 。