身份基加密，属性基加密以及函数加密

[AlexiaChen]

前言

这里主要是了解基本原理，暂不作很深入的学习。

身份基加密(Identity-Based Encryption, IBE)

先来介绍下IBE的背景知识吧，首先我们现在传统的PKI公钥密码体制存在的一些问题，比如发送者必须拥有接收者的证书，证书管理和CRL的复杂性，还有可能存在的证书数据库被暴露给组织机构等。

主要就是在传统的RSA公钥密码，公钥一般是人类不可理解的大数，无法把公钥与个人身份联系起来。所以在传统的公钥密码体制中，就需要有个可信的第三方中心（证书数据库）为每一个用户的公钥生成一个公钥数字签名（数字证书），主要作用就是认证用户公钥的作用（公钥与用户个人身份的绑定）。一旦有了数字证书，那么就存在管理，撤销，传输等等一系列的复杂操作，这些复杂的操作管理可能就是导致非密码学相关的安全事故发生的根本原因，所以为了解决这些问题，身份基密码体制被提出。

身份基密码体制有以下优势：

• 针对未准备（注册）用户的密码学
• 公钥是用户身份的某些属性，例如电子邮件地址，QQ号码，电话号码，指纹数据等
• 发送者只需要知道接受者的身份属性即可发送加密邮件（公钥加密私钥解密）
• 接收者在收到加密邮件后才需要与身份基密码系统进行交互

身份基密码的概念最开始是1984年由Shamir提出的，在论文Identity-Based Cryptosystems and Signature Schemes中提出了一个身份基签名（Identity-Based signature，IBS）的工作系统，但是并没有提出身份基加密(Identity-Based encryption)的系统方案。所以这个时候，身份基密码还停留在很初步的概念草稿阶段，所以构造一个高效可行的IBE是后来的密码学比较热门的方向。

直到2001年，第一个身份基加密（IBE）的系统方案由斯坦福密码学大佬Dan Boneh和Franklin的2001的论文Identity-Based Encryption from Weil Pairing中提出的，由论文标题可知，这个系统基于Weil配对。这里就涉及到之前写过的双线性映射知识。

假设Alice和Bob在一个IBE的系统上通信：

Alice要发送消息m给Bob，那么Alice可以不用提前通知Bob说我要给你发消息啦（换句话说Bob可以不用提前生成公私钥对，把公钥取得认证），Alice只要拿到Bob的公开信息比如Bob的Email地址，然后再到IBE系统中的秘钥中心拿到IBE系统的公开参数，Alice就可以通过公开参数和Bob的Email地址操作把消息m加密生成密文，Bob收到密文以后，就可以向IBE系统的秘钥中心通过自己的Email地址拿到自己的私钥，对密文进行解密阅读。

那之前提到IBS又是什么呢？ 如果上面案例的Alice，也想颁发一个属于自己的身份信息签名，那么她就需要把自己的身份信息比如QQ号码，发送给IBE的秘钥生成中心，秘钥中心就会把系统的公开参数和Alice的私钥发送给Alice，这样Alice就可以对消息m进行签名，Bob收到签名和消息m之后，就可以通过Alice的QQ号码向IBE的秘钥中心获取公开参数，验证签名。

下面讲解下IBE的数学基础：

主要还是离散对数问题，而且是椭圆曲线上的离散对数问题，这些问题都是安全假设，假设不成立，那么就是不安全的，之前很早写过，也不细说了。直接步入双线性映射的正题。

基于椭圆曲线，我们可以构造一个很重要的数学工具，双线性映射（https://github.com/AlexiaChen/AlexiaChen.github.io/issues/118 ）

这里用到的是Weil Pairing，是一个对称双线性映射，也就是G1,G2两个加法群同构，简单看作是G1。那么该双线性映射就表示为：

• e: G1 * G1 -> G2, 其中G1是q素阶循环加法群，G2是q素阶循环乘法群，g为G1的生成元
• e(g^a, g^b) = e(g,g)^(ab)

以椭圆曲线来表示双线性就是：

• e(a*P, b*Q) = e(P,Q)^(ab)

P,Q是有限域F_p上椭圆曲线上的任意一点 ，因为是素阶群，所以P，Q都是曲线的生成元。映射e的结果就是F_(p^2) 上的q素阶子群。双线性映射是单向函数，结果很难恢复到输入。这里用Miler算法可以高效地找出双线性映射e。 整个Boneh-Franklin这个Weil Pairing的安全可以规约到Weil Deffie-Hellman Assumption(WDH)。

WDH是：

• 给定<G, a*G, b*G, c*G>,其中随机选择a,b,c ∈ Z*q。G是椭圆曲线的生成元，计算W = e(G,G)^(abc) ∈ F(p^2)不可行。
• 当p是随机k位素数时，不存在一个算法可以在概率多项式时间内解决WDH问题

该IBE方案还用到了一个MapToPoint算法，该算法就是将一个二进制的任意序列转换为q阶椭圆曲线上的点，实际上就是一个Hash函数了。

下面讲下该IBE方案的基本原理：

1. 初始化(Setup)，由IBE秘钥中心这样的可信第三方来执行

• 使用已定义的椭圆曲线群E
• 选择q阶的生成元g g ∈ E/F_p
• 选择随机s ∈ Z*_q 并设置 pubkey = s*g
• 选择Hash函数：
  • H：F_(p^2) -> {0, 1}^n （将曲线上的点映射为具有n长度的二进制串）
  • G: {0,1}* -> F_p （MapToPoint Hash函数）
• 消息空间M = ｛0，1}^n ， 密文空间为C = E/F_p × {0, 1}^n
• 系统参数是<p, n, g, pubkey, G, H>. 主秘钥是s

2. 秘钥生成(Extract)， 秘钥生成中心来完成

• 使用MapToPoint Hash函数G将身份信息ID（比如Email地址）映射到点Q_id
• 与身份信息ID对应的私钥就是d_id = s*Q_id , 也就是IBE主秘钥与Q_id进行标量乘法得到的就是ID对应的私钥
• 将私钥d_id通过秘密信道发送给用户

3. 加密(Encrypt)

• 使用MapToPoint Hash函数G将ID映射到点Q_id
• 选择随机r ∈ Z_q
• C = <r*g, M ⊕ H((g_id)^r)>, 其中 g_id = e(Q_id, pubkey) ∈ F_(p^2)

4. 解密(Decrypt C = <U, V>)

• 如果U不是q阶的点，则拒绝密文C
• 否则， M = V ⊕ H(e(d_id, U))

为什么M能够被恢复？ 首先U = r*g, V = M ⊕ H((g_id)^r) 为什么恢复M，必须想方设法把 V ⊕ H((g_id)^r) 也就是异位或当时Hash出来的秘钥，但是当时的秘钥已经不能正向得到了，需要用到双线性映射的性质进行：

• e(d_id, U) = e(s*Q_id, r*g) = e(Q_id, g)^(s*r) = e(Q_id, s*g)^r = e(Q_id, pubkey)^r = (g_id)^r
• H(e(d_id, U)) = H((g_id)^r)
• V ⊕ H(e(d_id, U)) = M ⊕ H((g_id)^r) ⊕ H(e(d_id, U)) = M ⊕ H((g_id)^r) ⊕ H((g_id)^r) = M

属性基加密(Arrtibute-Based Encryption, ABE)

随着云计算，云存储的发展(Google Drive, AWS, Azure)，用户的数据被放到云上，但是用户的数据被放到云上后，用户会担心自己的数据被未授权的系统访问，公司自己的系统当然可以有访问策略比如RBAC等，但是不排除公司自己会作恶，或者被黑客攻击，更或者是公司的代码写错了，所以要用密码学手段来保证合理的数据访问控制。

当然，你可以用传统的公钥密码体制比如RSA来加密用户数据，用户自己解密，公司看不到。或者用IBE来做这样的场景也是可以的，但是当你的加密数据真的需要共享给他人访问的时候，你不可能把私钥拿给其他人吧？ 随着这样的场景增多，ABE逐渐浮出水面。它的演化路径是：

                                       |   ---> Key-Policy ABE        |
IBE(2001) -> Fuzzy IBE -> ABE                                      -> Functional Encryption(2011)
                                       |   ---> Cipher-Policy ABE    |

ABE的性质是：

• 将数据加密给具有某些属性的用户（只有那些属性用户才可以解密），这些属性可以是RBAC里面的角色（Role）
• 一对多公钥加密
• 内置访问控制机制

能力有限，ABE的具体方案原理也不讲解了，慢慢看论文吧。

函数加密(Functional Encryption)

这个是Dan Boneh他们2011提出来的，ABE的演进和推广，已经属于比较前沿的领域了，暂时保留到后面我有能力讲解吧。