GPSW06 KP-ABE 简介
Attribute-Based Encryption for Fine-Grained Access Control of Encrypted Data
Vipul Goyal and Omkant Pandey and Amit Sahai and Brent Waters
ACM CCS 2006
https://eprint.iacr.org/2006/309.pdf
这篇论文是第一篇可证明安全的KP-ABE方案，我第二次听别的同学介绍了，故在此简要记录。
这个方案看上去复杂，但理解起来逻辑还是清晰的。
KP-ABE中，加密者给每个密文附带上属性的标签，私钥和一个特定的访问控制结构绑定，该访问控制结构决定了该私钥可以解密哪种类型的密文。由于访问控制结构(policy)在私钥中，所以叫KP(Key-Policy)-ABE.
KP-ABE的场景和秘密分享十分相像。秘密分享方案是说满足特定条件的多个参与方可以重构出秘密，而满足特定条件的判定可以抽象为一个访问控制结构。比如叶子节点是参与方，内部节点是AND/OR门的一个树型访问控制结构，任何满足该访问控制结构的参与方集合可以重构出秘密。
类似的，KP-ABE中用户私钥和一个叶子节点是属性的访问控制结构绑定。如果密文的属性满足用户私钥的访问控制结构，则该用户可以解密该密文。
KP-ABE和秘密分享最大的区别在于，秘密分享允许多个参与方的交互合作，而这在KP-ABE中是明令禁止的。比如Alice持有密钥的访问控制结构为"X AND Y"，Bob持有密钥的访问控制结构为"Y AND Z"，如果他们合谋，则可以解密属性为Y的密文，这是我们不希望的。
私钥关联的访问控制结构是树型结构，叶子节点关联属性，内部节点是门限门。用户可以用给定私钥解密密文当且仅当存在从该密文到树节点的可以使得树满足的属性赋值。
一个内部节点即一个门限门，由子节点数和门限值描述。子节点数为，门限值为，。一个叶子节点由一个属性描述，门限值。一个节点的子节点从1到进行编号，返回节点的这个编号。
门限门是很具有表达能力的，比如可以用2 of 2门限门和1 of 2 门限门来分别表达AND门和OR门。当，门限门是OR门；当，门限门是AND门。
为访问控制结构，树根为。是以为根的子树。如果属性集合满足访问控制结构，记作。的计算以递归方式进行：如果是叶子节点，当且仅当。如果非叶子节点，对于所有子节点计算，当且仅当至少个子节点返回1。
所有可能的属性集合为，对于每个属性，在中均匀随机选择一个数
下述三个函数比较常规，可以看作是BF01-IBE方案的一个变体：
Public Parameters
Master Key
Ciphertext
解密密钥生成
对于访问控制结构中的每个节点选择一个多项式，该多项式的阶。 对于根节点，令，其他个点随机选择（个点确定阶多项式） 对于其他节点，令，其他个点随机选择。 对于叶子节点 where 的集合即为解密密钥
解密
解密过程就是计算
因为密文，只需要除掉就可以解密。
当且仅当密文满足访问控制结构时，
对于叶子节点和非叶子节点分别递归定义如下：
原理
对于叶子节点 if 对于非叶子节点
最核心的原理如下：当前节点的子节点多项式在0点处的值即为当前节点多项式在相应index(比如1，2等)点处的值，从而在获得超过门限值个当前节点多项式上的点的情况下，可以通过拉格朗日插值求出当前节点多项式在0点处的值。递归结束后可以求出访问控制结构树根多项式0点处的值。
例子
假设有两个属性，即。访问控制结构为 AND .
密文为
解密密钥的生成过程如下图：
解密过程如下：
思考
上述方案的公开参数和系统定义的属性个数线性相关，论文中后文通过构造 Large-Universe 变体规避了这个糟糕的性质。
这篇文章里的访问控制结构是由门限门构成的电路，该电路显然是AND-OR电路的一种推广，但是该电路和图灵完备的通用布尔电路和算数电路是何种关系？换言之，对于非线性逻辑关系的访问控制结构是否已有KP-ABE方案？对于有向无环图DAG拓扑结构的访问控制结构是否已有KP-ABE方案？
该文的访问控制结构可以扩展到任意存在linear secret-sharing scheme(LSSS)可以实现的情况，而对于每一个LSSS可实现的访问控制结构都和一个可以计算相应布尔函数的monotone span program (MSP)一一对应。而MSP又可以和在研究通用zk-SNARKs系统电路表示的QSP/QAP/SSP等联系起来。
该方案在访问控制树层次之间编码多项式的方法让我想到了Sum-check协议的不同轮之间以及相应的多项式低阶扩展/MLE技术，至于两者只是感觉上相似还是真具有内在关联，还有待继续思考。