基于属性的加密算法 23 第二章 预备知识 2.1 数学运算 2.1.1 近世代数基础 定义 2.1(群)：设 G 是一个非空集合，若在 G 上定义一个二元运算“∙”满足：  结合律：对任何的푎, 푏, 푐 ∈ 퐺,有 푎 ∙ 푏 ∙ 푐 = 푎 ∙ (푏 ∙ 푐)  单位元：存在单位元 e 使得对于任何푎 ∈ 퐺有푎 ∙ 푒 = 푒 ∙ 푎 = 푎  逆元：对任何푎휖퐺，都有逆元푎−1使得푎−1 ∙ 푎 = 푎 ∙ 푎−1 = 푒 定义 2.2（阶）：群 G 中的元素的个数叫做群的阶，用|G|表示。如果|G|是悠 闲地，那么称 G 为有限群。 定义 2.3（阿贝尔群）：若对于任何푎, 푏, 푐 ∈ 퐺,有 푎 ∙ 푏 ∙ 푐 = 푎 ∙ (푏 ∙ 푐), 若 G 是 有限的，那么称 G 为可换群。 定义 2.4（循环群）：若存在一个元素 g,使得对于任何푎 ∈ 퐺都存在一个整数 i ∈ Z,满足푎 = 푔푖,则称 G 为一个循环群，其中，g 成为 G 的生成元。 2.1.2 双线性配对 设有一个 q 阶（q 为素数）加法循环群 G1,P 为 G1 的生成元。G2 为一个相同素 数 q 阶的乘法循环群。我们假定在 G1 和 G2 上的离散对数问题(DLP)是难的。双线 性配对 e：G1×G1 G2 具有以下三个性质： （1） 双线性： e(P1+P2,Q1)=e(P1,Q1)e(P2,Q1) e(P1,Q1+Q2)=e(P1,Q1)e(P1,Q2) 其中 P1,P2,Q1,Q2 均属于 G1 （2）非退化性：存在 P，Q 属于 G1 使得 e(P,Q)  1 （3）可计算性：对所有的 P，Q 属于 G1 存在一个高效的算法可以计算 e(P,Q) 2.1.3 拉格朗日插值定理 基于属性的加密算法 24 设 q 是一个素数 f(x)是一个 k 阶的多项式；设 j0,…jk 是 Zq 上的不同元素。设 f0=푓푗0 ,…,fk=푓푗푘 利用拉格朗日插值定理，我们可以将多项式 f(x)表示城 ))(()( 0 xfxf t k t t    其中 ktii xjx kti ti i t ,...,0,)( 0      为拉格朗日系数。 2.2 安全假设与计算复杂性 2.2.1 安全假设 定义 2.5（离散对数问题）:令 G 表示一个 q 阶的群，g 是其生成元。离散对数 问题即给定随机元素푦 ∈ 퐺,求元素푥 ∈ 푍푝满足 y=gx。 定义 2.6（计算 Diffie-Hellman 问题 CDHP）: 令 G 表示一个 q 阶的群，g 是其 生成元。计算 Diffie-Hellman 问题是给定三元组(g,ga,gb),计算 gab。 定义 2.7（判定 Diffie-Hellman 问题 DDHP）：令 G 表示一个 q 阶的群，g 是其 生成元。判定 Diffie-Hellman 问题是给定三元组(ga,gb,gc)判断 gc 是否等于 gab。 定义 2.8（双线性 Diffie-Hellman 问题 BDH）：对于群 G1,G2，g 是 G1 的生成 元，e 为双线性配对运算，则 BDH 问题是给定（g,ga,gb,gc）计算 e(g,g)abc 定义 2.9（判定双线性 Diffie-Hellman 问题 DBDH）：对于群 G1,G2，g 是 G1 的 生成元，e 为双线性配对运算，给定（g,ga,gb,gc,Z）判断等式 e(g,g)abc=Z 是否成立。 定义 2.10（判定 q 双线性 Diffie-Hellman 问题 q-BDHE）: 令 G 表示一个 q 阶的 群，g 是其生成元。判定 q 双线性 Diffie-Hellman 问题是对于随机选取的푎, 푠 ∈ 푍푝对 于给定的参数 y= 푔, 푔푎 ,…, 푔푎푞 ,, 푔푎푞+2,…, 푔푎2푞 , 푔푠 , 푇 判断等式 푇 = 푒 푔, 푔 푎푞+1푠 是否成立 基于属性的加密算法 25 2.2.2 计算复杂性 定义 2.11（函数平凡上界）：对于两个函数 f(x)和 g(x),若存在一个常数 c 和一 个正整数 xc 满足对于所有的 x>xc 都有0 ≤ 푓(푥) ≤ 푐 ∙ 푔(푥)则 f(x)是个 g(x)的一个平 凡上界，即푓 푙 = 푂(푔 푙 )。 定义 2.12（可忽略函数）：对于任意的多项式 p(x)，总存在一个自然数 N 使对 于所有的 x>N 都有푓 푥 < 1 푝(푥) 则称 f(x)为可忽略函数。反之，则称 f(x)为不可忽略 函数 定义 2.13（多项式时间算法）：若一个算法的运行最差时间是 O(lc)，其中 l 是 输入的规模，c 是一个常数，则称此算法为多项式算法。反之，则称其为一个非多 项式时间的算法。 2.3 可证安全模型 2.3.1 可证安全基本定义 定义 2.14(哈希函数)：哈希函数通常为一个确定的函数，它将任意长度的比特 串映射到固定长度的比特串。对于哈希函数 H:{0.1}*→{0,1}n,即将任意长度映射到 n 长度的比特串，它需要满足以下的安全性质：  散列性：对于任意的输入 x，输出地哈希值 H(x)应当在区间[0,2n]中均匀分 布的二进制窜在计算上不可区分。  单向性：已知一个哈希值 h,找出一个输出串 x 使得 H(x)=h,在计算上是不可 行的。  有效性：给定一个输入串 x，哈希值 H(x)的计算可以在关于 x 的长度规模 的多项式时间内完成。  抗强碰撞性：找出两个不同的输入 x 和 y,使得 H(x)=H(y)，在计算上是不可 进行的。  抗弱碰撞性：给定一个输入 x，找出两一个不同的输入 y，使得 H(x)=H(y) 在计算上是不可行的。 常用的哈希函数有 MD5[35],SHA[36]等。 基于属性的加密算法 26 定义 2.15(随机预言机及模型)：对于哈希函数 H:{0,1}*→{0,1}n,如果满足均匀性， 确定性和有效性，则称这个哈希函数为随机预言机。利用随机预言机进行密码体制 安全证明的方法被称为随机语言模型。 随机预言机模型用于证明密码体制的安全时，往往被作为一个随机函数使用。 在体制开始设计的时候，系统中的各个角色共享随机预言机，并利用随机预言机完 成设定和初始操作。对于随机预言模型下证明安全的函数，我们则认为在现实中可 以使用较安全的哈希函数代替随机预言机。 定义 2.16(标准模型)：标准模型是相对于随机语言模型而言，不需要使用随机 预言机假设的安全模型。 与随机预言模型相比，标准模型不能借助随机数生成机制来产生一些假设。在 描述安全证明时，模拟者需要模拟一切真实的环境，包括现实中的哈希函数的使用。 使得欺骗攻击者对模拟的环境进行攻击操作。在密码体系安全证明的过程中，最后 我们总是将其归约到一个假设难的问题上去，如 BDH，CDH 问题等等。如果攻击 者对模拟的环境可以进行成功的攻击，则可以以不可忽略的概率解决或判定这些难 的问题，这与密码学的基本假设是矛盾的，从而使密码体系的安全得到证明。 2.3.2 可证安全模型 定义 2.17（公钥加密方案），一个公钥加密方案一般由以下四个算法组成。  系统初始化(Setup)：这是一个概率算法，以一个安全参数作为输入，一般 是以 1k 的形势输入，k 是与安全的强度规模相关。输出系统的系统公钥和 公共参数 PK。  密钥抽取（KeyGen）：这是一个概率算法，输入为系统公钥和公共参数 PK,输出为一组公私密钥对，我们经常用 pk,sk 分别代表公钥和私钥。  加密（Enc）：加密算法同样为一个概率算法，输入为一个消息 m,系统公 共参数 PK，某个接收者的公钥 pk,输出为密文 CT。  解密(Dec)：解密为一个确定性算法，输入为密文 CT 用户私钥 sk 输出为明 文 m 或者终止符⊥。 定义 2.18(选择明文攻击安全 IND-CPA)。对于挑战者 C 和攻击者 A 之间的一 个游戏包含以下几个部分  系统建立阶段：挑战者 C 选择一个安全参数 k，运行系统初始化算法(Setup) 和密钥抽取(KeyGen)算法，并想攻击者 A 提供生成的系统公钥及公共参数 基于属性的加密算法 27 PK 以及公钥 pk。但对于私钥 sk，挑战者并不向攻击者 A 提供而是自行保 留。  挑战：攻击者 A 向挑战者提供两个长度相等的信息 m0,m1,挑战者 C 随机选 取其中一个设为 mt 并生成挑战密文 C’=Enc(pk,mt)。并将挑战密文交与挑战 者。  输出，如果攻击者 A 对于 mt 给出一个猜测 t’=t 或者 t’≠t。如果攻击者 A 给 出了正确的猜测则我们称攻击者赢得了游戏。 对于这样的一个游戏我们称之为选择明文攻击(IND-CPA)游戏，对于攻击者赢 得游戏的概率我们定义为： 퐴푑푣퐴 푘 = | 푃푟 푡′ = 푡 − 1 2 | 如果对于任何的 IND-CAP 攻击者，在这个游戏中的赢得游戏的概率都是可以 忽略的（定义 2.6）,我们称这个 PKE 方案是 IND-CPA 安全的。 定义 2.19（选择密文攻击 IND-CCA）。对于挑战者 C 和攻击者 A 之间的一个 游戏包含以下几个部分  系统建立阶段：挑战者 C 选择一个安全参数 k，运行系统初始化算法(Setup) 和密钥抽取(KeyGen)算法，并想攻击者 A 提供生成的系统公钥及公共参数 PK 以及公钥 pk。但对于私钥 sk，挑战者并不向攻击者 A 提供而是自行保 留。  挑战前查讯阶段：攻击者 A 可以一次或者多次的向挑战者 C 提出解密查询， 挑战者 C 利用私钥 sk，将查询密文 CTi 对应的明文 mi 提供给攻击者。  挑战：攻击者 A 向挑战者提供两个长度相等的信息 m0,m1,挑战者 C 随机选 取其中一个设为 mt 并生成挑战密文 C’=Enc(pk,mt)。并将挑战密文交与挑战 者。  挑战后查询阶段：同挑战前查询阶段，但攻击者不可以询问被挑战的密文。  输出：如果攻击者 A 对于 mt 给出一个猜测 t=0 或者 t=1。如果攻击者 A 给 出了正确的猜测则我们称攻击者赢得了游戏。 如果对于任何的 IND-CCP 攻击者，在这个游戏中的赢得游戏的概率都是可以 忽略的（定义 2.6）,我们称这个 PKE 方案是 IND-CCA 安全的。 2.4 基于属性加密算法的相关定义 基于属性的加密算法 28 定义 2.20(门限，Threshold)：一个门限是一个逻辑运算单元，它具有一个阀值 K 和 num 个输入(퐾 ≤ 푛푢푚)，每一个输入只有 1/0 两种状态。当状态为 1 的输入数 大于等于 K 时，门限将输出 1，否则则输出 0。对于特殊的门限，例如 K=1 则是对 应的或门（OR Gate），当 K=num 时则是对应于与门(AND Gate)。示例如图 2.1 图 2.2，图 2.3 所示。 定义 2.21(访问树，Access Tree)：访问树用于表达一个控制访问结构。每一个 树的非叶子结点都是一个门限，而叶子结点则与某属性绑定。对于叶子结点 x,函数 att(x)则返回叶子结点相对应的属性。对于任意节点 x,函数 index(x)则返回该节点的 索引。如图 2.4 所示 图 2.4 访问控制树 定义 2.22(线性秘密分享方案，Linear Secret-Sharing schemes): 如果对于一个集 合 P,集合中的每一个元素所获得的分享部分可以形成一个 Zp 上的向量。存在一个 l 行 n 列的分享生成矩阵 M,使得对于所有的 i=1,…,l,矩阵 M 的第 i 行代表集合中的一 个元素，并且我们可以通过函数𝜌(푖)找到对应的元素。对于这样一个向量 AND 3 属性 1 属性 2 OR 属性 3 属性 4 属性 5 属性 6 0/1 K , m 0/1 0/1 0/1 num=3 1 , m 0/1 0/1 0/1 3 , m 0/1 0/1 0/1 图 2.2 输入为 3 的与门 图 2.3 输入为 3 的或门 0/1 0/1 图 2.1 输入为 3 的门限 基于属性的加密算法 29 v=(s,r2,…,rn),其中 s 是一个 Zp 上的需要被分享的秘密，r2,…,rn 都是在 Zp 上随机选取 的。则 Mv 得到的向量是这 l 个元素所分享的信息，其中(MV)i 属于元素𝜌 푖 。 由文章[9]可知元素分享的信息具有秘密恢复的属性，即对于某个集合 S 是由矩 阵 M 决定的可以恢复出秘密的集合。则对于퐼 ⊂ 1,2,…, 푙 , 퐼 = {푖: 𝜌(푖) ∈ 푆}存在这 样的常量集合{휔푖휖푍푝}푖∈퐼使得对于秘密 s 的有效分享휆푖信息有 휔푖휆푖 푖∈퐼 = 푠 这些常量的集合可以根据矩阵 M 在多项式的时间内获得。 2.5 本章小结 本章主要介绍了公钥密码学属性加密相关的一些预备知识，首先介绍一些数学 的定义和运算，大部分公钥密码学的运算都是基于抽象代数的。之后我们又分别介 绍了安全假设和可证安全模型以及安全属性的证明方式。在最后一节给出了关于基 于属性的一些相关定义。 基于属性的加密算法 30 基于属性的加密算法 31 第三章 基于属性的加密算法及应用 3.1 模糊匹配的基于身份(Fuzzy IBE)的加密方案 模糊匹配的基于属性的加密方案[3]由 Amit Sahai 和 Brent Waters 于 2005 年发表 于欧洲密码学会议。在这篇文章中结合实际的解释了属性的概念。并通过给出的方 案进一步的引伸出基于生物属性的模糊匹配的应用场景。 这篇论文基于的场景可以描述如下，首先系统通过一个密钥抽取算法对一个集 合的属性（设为휔’）生成对应的公私钥对，之后对明文 M 进行加密。当解密者拥 有的属性私钥集合휔满足휔和휔’的交集的大小大于某个系统设定值 d 则，解密者可 以解密获得明文。 简要的协议描述如下:  基本定义：设 G1 是一个以素数 p 为阶的双线性群，g 是其生成元， 푒: 퐺1 × 퐺1 → 퐺2为一个双线性配对运算。 훥푖,푠 푋 = 푥 − 푗 푖 − 푗푗 ∈푆,푗 ≠푖 为拉格朗日参数，S 是一个在푍푝的集合。所有的属性集合为 U,而所有属性 都与푍푝 ∗中的元素关联。  初始设置：对于一个集合的属性，为其随机选择푍푝 上的푡푖 作为属性的私钥， 并公布属性对应的公钥为 {푇1 = 푔푡1 , ⋯ , 푇 푈 = 푔푡 푈 } 而系统的公钥为푌 = 푒(푔, 푔)푦 ，系统的管理密钥为 푡1, ⋯ , 푡 푈 , 푦。  密钥抽取：对于一组属性集合휔 ⊆ 푈,随机选择一个 d-1 维的多项式 q(x)使 得 q(0)=y。这样对于用户的私钥 Di，i∈ ω对应于 Ti 有퐷푖 = 푔 푞(푖) 푡푖 。  加密算法：对于集合휔’和明文푀 ∈ 퐺2选择随机值 s,加密后的结果为 퐸 = (휔′, 퐸′ = 푀푌푠, 퐸푖 = 푇푖 푠 푖휖휔′)。  解密算法：对于集合휔如果|휔 ∩ 휔’| ≥ 푑则选则任意属于两个集合交集的 d 个元素，利用拉格朗日差值定理，可得