一种基于密钥策略的属性加密算法研究学士学位论文.docx

一种基于密钥策略的属性加密算法研究Research on a Key Policy Attributed Based Encryption (申请武警工程大学工学学士学位论文)部(系)：电子技术系八队专业：信息研究与安全学员姓名：李金钊指导教师：朱率率二一四年五月指导教师评语指导教师签名： 日 期： 摘要摘要在信息时代，计算机与现代社会中人们的日常生活联系非常紧密，网络已应用到了社会的各个角落，人与人之间的通信方式也发生了巨大的变化，传统的事务越来越多地依赖于网络的协助，相应地，许多数据加密、数字签名和基于口令的认证等密码技术也层出不穷。为了能够提供安全的通信环境，计算机密码学被广泛地应用于军事、政治、外交、商业和其他领域。随着密码学的发展，也出现了多种密码学的分支，如分组密码、公钥密码等，其中尤其以公钥密码发展得较为完善，并且在各种应用尤其是商业上的开发更为广泛，已经成为许多网络、商业通用的加密标准。但是，现在的公钥密码体制仍存在着一些不足或难以解决的缺陷，如密钥的开销巨大、难以保护用户的隐私等，在这种情况下，为了适应一对多的通信模式，基于属性的加密体制应运而生。目前基于属性的加密体制已经有了巨大的成就，这些成就也与Vipul Goyal，Amit Sahai，Omkant Pandey，Brent Waters等人的贡献密不可分，他们把属性基的加密机制在基本ABE的基础上详细地划分为密钥策略和密文策略，并且给出了一个细粒度的属性基加密机制的具体方案。本文将围绕Vipul Goyal等人的论文进行研究，并将基本ABE、密文策略和密钥策略的加密机制在性能、效率、安全等方面作简单的比较，然后就基于密钥策略的属性加密算法进行详细的研究，在性能、系统开销、安全性和应用环境等方面进行分析，再对其存在的问题与缺陷进行探讨。最后，分析该方案在当前的社会应用背景下能够发挥作用的场景并列举其与其他算法相比较的优势，以及在应用中可能会遇到的问题或与其他算法需要改善的地方。关键字：基于属性加密，密钥策略，访问控制，密文策略，基本ABE电子技术系 VAbstractAbstractIn the information year, the computer is closely connected with people's daily life in modern society. The network has penetrated into every corner of the society, and great changes have taken place communication. Traditional transactions are increasingly depending on the network communication. Coordinately, data encryption, digital signature and authentication schemes keep appearing. In order to provide a safe communication environment, the computer cryptography is widely used in military, politics, diplomatic, business and other fields. With the development of cryptography, there have been many branches of cryptography, such as block cipher, public key cryptography, which are perfect, especially in public key cryptography development and widely in various applications. Many algorithms has become general encryption standard, especially in business development. But now, some deficiency still exists in the public key cryptosystems. For example, it is difficult to solve the defect of the key costly, and to protect the users privacy. In this case, in order to adapt to a one-to-many communication mode, attribute based encryption system appeared at the historic moment. So far, attribute based encryption system has achieved many advances, such as the works done by Vipul Goyal, Amit Sahai, Omkant Pandey, Brent Waters and others. Their newly developed attribute based encryption system on the basis of the basic ABE can be divided into two types: key policy and ciphertext policy, which can provide fine-grained access properties based on the concrete scheme of encryption mechanism. In this paper, we will research on the basic ABE and present some critical benchmark of an ABE scheme. And then, Vipul Goyals key policy ABE scheme is fully analyzed in the system performance, algorithm efficiency and scheme security. Then, we discussed a universal key policy based ABE scheme in performance, system cost, security, and applying environment, etc. Finally, we analyzed the existing problems and defects in a key policy ABE scheme. While analyzed Vipul Goyal scheme, we also presented a detailed introduction and analysis upon the KP-ABE algorithms. We analyzed the scheme under the background of the current social application with certain application scenarios by comparing with other algorithms, as well as the problems the scheme needs to improve.Keywords: attribute-based encryption, KP-ABE, access control, CP-ABE, basic ABE 目录目录摘要IAbstractIII第一章 绪论11.1密码学的基本知识11.2基于属性加密的研究背景31.3属性加密的发展及现状3第二章 基于属性加密概述52.1基于属性加密简介52.2经典方案52.2.1基本的属性加密52.2.2密文策略的属性加密（CP-ABE）72.2.3密钥策略的属性加密（KP-ABE）92.3分析与总结11第三章 基于密钥策略的属性加密体制（KP-ABE）的分析133.1相关知识133.1.1细粒度的访问控制133.2关于细粒度的访问控制的一个具体方案143.2.1KP-ABE方案143.2.2安全性证明：163.2.3安全性分析203.2.3.1效率分析203.2.3.2适用环境203.2.3.3存在的不足21第四章 总结与展望23参考文献25致谢27第一章 绪论第一章 绪论1.1密码学的基本知识密码学是一门在破译与反破译的斗争中发展起来的科学，在现在的社会发展中，密码学已经是融合了多个尖端科技的综合性技术科学，与语言学、数学、电子学、声学、信息论、计算机科学等均有密切的联系。密码的产生和应用都是因为战争的需要，但是早期的密码只能是作为一种玩具，直到1949年香农发表了“保密系统通信原理”，才使密码学成为一门科学。香农用统计学理论对密码传输的各个要素进行了定量分析，并用信息论的观点，引入不确定性、剩余度和唯一解距离等概念，作为密码体制安全性的度量，开辟了密码学的新时代。随后，Diffie和Hellman在1976年发表了他们的著名论文“密码学的新方向”，创造性地提出了可以用于认证的新思路，即公钥密码体制的前身。1密码学的定义是研究信息系统安全保密的科学，包括密码编码学和密码分析学。通常情况下，密码技术主要靠一下三个方面保证系统中的消息的安全：保密性：指信息按给定要求不泄漏给非授权的个人、实体或过程，或提供其利用的特性，即杜绝有用信息泄漏给非授权个人或实体，强调有用信息只被授权对象使用的特征。完整性：指信息在传输、交换、存储和处理过程保持非修改、非破坏和非丢失的特性，即保持信息原样性，使信息能正确生成、存储、传输，这是最基本的安全特征。不可抵赖性：指通信双方在信息交互过程中，确信参与者本身，以及参与者所提供的信息的真实同一性，即所有参与者都不可能否认或抵赖本人的真实身份，以及提供信息的原样性和完成的操作与承诺。1另还有其他的服务:可用性：指网络信息可被授权实体正确访问，并按要求能正常使用或在非正常情况下能恢复使用的特征，即在系统运行时能正确存取所需信息，当系统遭受攻击或破坏时，能迅速恢复并能投入使用。可用性是衡量网络信息系统面向用户的一种安全性能。可控性：指对流通在网络系统中的信息传播及具体内容能够实现有效控制的特性，即网络系统中的任何信息要在一定传输范围和存放空间内可以被控制。除了采用常规的传播站点和传播内容监控这种形式外，最典型的如密码的托管政策，当加密算法交由第三方管理时，必须严格按规定可控执行。基于身份的公钥密码学研究基于属性的加密体制，就不得不说到公钥密码学。公钥算法依赖于一个加密密钥和一个与之相关的不同的解密密钥，这些算法都具有下述重要特点：仅根据密码算法和加密密钥来确定解密密钥在计算上是不可行的。两个密钥中的任何一个都可用来加密，另一个用来解密。 公钥密码体制有6部分组成：明文：算法的输入。加密算法：用于对明文进行各种变换。公钥和私钥：算法的输入。一个用于加密，一个用于解密。加密算法执行的变换依赖于公钥或者私钥。密文：算法的输出。由明文加密得到。解密算法：该算法接收密文和相应的密钥，并产生原始的明文。主要步骤如下：每一个用户产生一对密钥，用来加密和解密信息。每一个用户将其中一个密钥存于公开的寄存器或其他可访问的文件中，该密钥称为公钥，而另一密钥则保持私密。每一个用户可以拥有若干其他用户的公钥。若Bob要发信息给Alice，则Bob用Alice的公钥对信息加密。Alice收到信息后，用其私钥对信息解密。由于只有Alice知道其自身的私钥，所以其他的接收者均不能解密该消息。利用这种方法，通信各方均可访问公钥，而私钥是各通信方在本地产生的，所以不必进行分配。只要用户的私钥收到保护，保持秘密性，那么通信就是安全的。在任何时刻，系统可以改变其私钥，并公布相应的公钥以替代原来的公钥。21.2基于属性加密的研究背景Shamir于1984年提出基于身份的加密方案的同时，也提出了一个基于整数分解的身份基加密方案，然后，Boneh和Franklin首次提出了基于身份的加密方案，是利用椭圆曲线上的双线性配对完成的，2007年，Boneh改进了一个由Cocks提出的利用二次剩余理论构造出安全的基于身份加密的方案。但是，基于身份的加密中，双方的通信是一对一的，即加密者与解密者必须互相知道对方的身份，而且信息的传递也是一对一的，这种现今的网络环境中有太多的局限性，难以适应一对多的共享式网络应用环境，因此，基于属性基的加密方法应运而生。基于属性的加密方案是一种融合了基于访问控制和身份基加密的方案，典型方法是基于身份的广播加密，广播加密就是将可以加密的身份集合包含在广播的密文中，只有当解密者满足集合中的要求时，才可以解密。1.3属性加密的发展及现状目前，基于属性的加密算法仍在理论阶段。我们已经知道传统的公钥基础设施（PKI）存在重大缺陷：加密方必须获取解密方的公钥。2001年间，Shamir和Boneh提出了基于双线性对技术的身份基加密（identity-based encryption，简称IBE）机制，使用用户的身份作为加密的公钥，这样加密方不必知道解密方的公钥，以某一类集体用户作为信息的接收方。随后，2005年，Sahai 和Waters5在前者的IBE技术基础上提出了属性基加密（attribute-based encryption，简称ABE）机制，开辟了属性基加解密的先河。基于属性的加解密有许多传统的公钥基础设施（PKI）难以实现的优势：加密方在加密前无需知道接收方的具体身份和数量，极大的保护了解密方的隐私，且大大降低了系统的开销和对带宽的占用；同时，两人的算法还提高了系统的抗串谋攻击，不同用户的密钥不能互相联合，并且还支持灵活的访问控制，可以实现属性的与、或、非和门限操作，充分展示了属性基加密的优越性和先进性。随着对属性基加密的进一步研究，2006年，V.Goyal 等人5提出了密钥策略的属性加密机制（KEY-Policy Attribute Based Encryption，简称KP-ABE）；2007年，Bethencourt等人8提出了密文策略的属性加密机制（Ciphertext-Policy attribute-based encryption，简称CP-ABE）。但是，基于属性的加密机制目前仍不是很完善，仍存在一些缺陷和需要解决的问题，在下文中会进一步探讨。电子技术系 27第二章 基于属性加密概述第二章 基于属性加密概述2.1基于属性加密简介目前互联网的环境下网络信息的安全问题日益增多，传统的基于公钥基础设施的加密机制存在着大量的不足：处理密文、密钥的开销巨大以及无法完全保证用户的隐私；并且在另一方面，网络上的信息犯罪日益增多，个人隐私也面临着极大的威胁。同时，大量新兴的的网络社交应用层出不穷，网络上的数据共享、数据转发和各种分享功能的扩展对传统的加密方式要求也不短提高，传统的加密方式已经难以满足新形势下的网络交流环境，因此迫切的需要一种能够满足在较小密钥开支甚至预先不确定接收方详细信息的情况下实现网络通信的加密方法。用新的加密方式应对新兴的网络安全问题，是解决传统公钥秘密体制的缺陷的科学的方法。2.2经典方案2.2.1基本的属性加密Sahai 和Waters的基本ABE算法，是模糊匹配的基于身份（Fuzzy-IBE）9的加密方案。流程该方案的流程基本是这样的：首先，需要规定一个属性的集合，A，里面有大量的属性。然后，再通过一个密钥抽取算法对属性集合A生成对应的公私钥对，然后再加密明文。当一个用户需要解密密文时，需要比较该用户的私钥SK与属性集A的交集，如果大于之前设定的值（D），才可以对密文进行解密得到明文，反之则没有解密的权限。1、 协议基本步骤可分为4步：Setup，Extract，Encrypt和Decrypt。系统初始化时根据安全参数运行BDH 参数生成器5，产生两个阶为素数q的群G，G，以及双线性对e:G×GG，d 为门限参数.（1） Setup（d）：授权机构执行，选择，系统公钥PK为。主密钥MK为。（2） KeyGen：授权机构执行，生成用户u的私钥.随机选择一个（d1）次多项式p，令p（0）=y，用户私钥SK 为。（3） Encrypt：发送方执行，用属性集加密消息。随机选择，密文为。（4） Decrypt：接收方执行。若，则选择d个属性，计算，再用拉格朗日插值找到，得到。（pdf3、4）上面的方案是一个基本的属性加密算法，也是Shamir的门限共享机制18，具体的做法是把秘密y嵌入到SK的各个构件中，以此来实现门限策略；在上面的算法中，SK与随机多项式p有关，用户与用户之间无法通过交流私来钥实施串谋攻击。同时，Encrypt算法采用双线性对加密消息，并且密文构件与属性相关，从而规定了解密必须的属性；随机数s可以防止多次加密情况下用户首次解密成功即可解密后续密文的问题。2、 评价这算是ABE算法的一个初级模型，即第一次的表示了“门限”的操作以及实现的方法，但是有着极大的局限性，信息的加密方不能规定其所加密的信息的“门限”，实际上在这个算法里的“门限”是由授权机构制定的，难以适应广泛的现实应用需求。3、 总结基本的ABE算法安全性最低，适用于开放度比较高，对策略要求简单的应用，或者个人信息的公开度较低，用户范围较大的网络应用。公钥、主密钥和私钥的生成都由授权机构执行，发送方用公钥、主密钥对密文进行加密，解密由接收方执行，需要用到公钥和自己的私钥。这种基本ABE算法只能表示属性的“门限”操作，且门限参数、访问控制策略均由授权机构决定。2.2.2密文策略的属性加密（CP-ABE）Brent Waters 的CP-ABE 算法8在这一种方案中，作者提出了一种新的描述控制结构的方式，即“线性秘密共享”（Linear Secret Sharing Scheme，简称LSSS）的方案，来判断用户的属性是不是属于被授权集合，并且该方案在标准模型下已被证明是安全的。首先，作者定义了一个“授权集”：即满足了对应的控制结构的属性的集合。“授权集集合”就是所有的授权集的集合，是该类基于属性的加密方法的控制结构。在线性秘密共享中，授权集中的每个元素都可以对应一种属性，每一个矩阵都对应授权集集合，授权集中的元素，可以通过相互之间的分享来恢复出明文。1、 流程该算法的大致运行流程可以这样概括：访问控制策略是由加密方决定的，加密后的密文用树结构描述访问控制策略，用户的密钥与授权集有关，达到最低标准才可以被授权解密。首先，需要有公认的授权机构生成主密钥和公钥，还要为每个用户生成各自的私钥，加密方在加密的过程中规定了密文的门限与访问策略，接收方用公钥和自己的私钥进行解密，当私钥的属性符合要求时，才会被授权解密密文。2、 协议 初始设置：是一个以素数p为阶的双线性群，g是其生成元，为一个双线性配对运算。随机的我们可以在上选取a和。选择哈希函数。 加密算法：对于明文m选择随机向量，则，密文为 密钥抽取：对于某一属性的集合S，在上随机选取t，则密钥为。 解密算法：对于密文 CT 和线性分享的结构对应的矩阵，满足控制访问结构的属性集合S对应的密钥K，以及线性密钥分享方案对应的常量集合，则解密的运算首先计算。之后可以从C中分离出明文m。3、 评价在这个方案中，用户的私钥是由授权机构用两级随机掩码方式生成的，用户的私钥构件与第2 级随机数相关，有效的防止了用户之间的串谋攻击。原本的算法的模式只能使用拉格朗日差值定理构造，是基于属性的加密算法的一大突破。只需要给用户分发一次密钥，用户就可以对符合其权限的密文进行解密。但是也存在一些不足：比如访问结构限制过于复杂，导致设计上的限制比较多，而且密文的解密还需要通过授权机构的认证，并且授权机构的工作量十分巨大，导致授权机构的权力也过于庞大。4、 总结这个密文策略的ABE算法是目前较为完备的方案，并且提出了一种新的对控制结构的描述形式。通过利用线性秘密分享的方案（LSSS）来决定哪些子集属于授权集合哪些属性的集合不是授权集合。基于这种方案的属性基的加密打破了原来众多方案只能使用拉格朗日差值定理进行构造的模式。缺点是非属性的扩展比较困难。2.2.3密钥策略的属性加密（KP-ABE）V.Goyal等人的KP-ABE算法5密钥策略和密文策略的属性基加密算法的区别在于访问结构和属性集分别由什么决定。密文策略的加密系统中，访问结构是由密文决定的，用户的私钥对应属性集合，只有当用户的私钥满足密文的需求时才能有权限解密。而在密钥策略的加密系统中，情况相反。1、 流程加解密的过程与基于密文策略的加密系统类似，同样由授权机构生成主密钥和公钥，然后为每个用户分发各自的私钥，但是用户的私钥采用树结构描述访问策略，私钥生成时是自顶向下的，采用秘密共享机制，主密钥分散到对应于叶节点的私钥构件中，解密算法对访问策略树自底向上采用递归过程解密每个节点，得到恢复明文所需的秘密值。2、 协议基本定义：设是一个以素数 p为阶的双线性群，g是其生成元，为一个双线性配对运算。是拉格朗日参数，S是一个在的集合。所有的属性集合为U，而所有属性都与中的元素关联。初始设置：对于一个集合的属性，为其随机选择上的作为属性的私钥，并公布属性对应的公钥为而系统的公钥为，系统的管理密钥为。加密算法：对于集合和明文选择随机值 s，加密后的结果为密钥抽取：对于每一个访问树中的非叶子节点 x，选择一个多项式 q（x），使得它的度为这个节点的阀值少1，即；对于根节点r则选择，而对于其它非叶子结点，使得;针对于叶子结点的抽取的密钥为解密算法：对于所有的用户拥有的属性对应的叶子叶结点计算 对于非叶子结点利用它的子节点的返回值，由下至上的进行递归运算， 最终可得。（ttkn28）3、 评价密钥策略的加密机制适合用户增加比较频繁或者用户的权限变化较多的应用场景，用于用户访问数据相对稳定的资源，可以将数据资源即加密的密文专门存放，然后为用户分发相应的私钥，用户即可有序地访问被授权的数据。这种算法解决了基本ABE算法的缺陷，具有较灵活的访问控制策略。加密者可以自由的规定属性的门限，而解密者只需要经过一次个人属性密钥的分发就可以对自己已经被授权的信息进行解密。最重要的一点，由于采用的是共享机制，导致这个算法不支持“非”的属性操作。但是后来Ostrovsky等人又在此基础上作了改进，通过采用之前Naor和Pinkas提出的广播撤销机制实现了表示“非”的属性操作，完善了密钥策略加密机制的策略灵活性，代价却是所有的开销都加倍，包括密文和用户私钥的大小，以及加解密的开销等等；再后来，Lewko和Waters又在此基础上对算法进行了改进，缩短了系统公钥的长度，但是又增加了密文的长度。4、 总结综合来讲，密钥策略的加密机制研究的热度比较高，已经有多人对其进行了完善与创新，也有众多适合应用的场景，但是也存在许多缺陷，并且这些缺陷在目前的研究成果中还没有效率比较高、效果比较令人满意的解决办法。虽然如此，但是却受到众多专家学者的关注，具有良好的发展前景，并且具体的应用场景也很广阔。2.3分析与总结三种基于属性的加密机制都是学者们悉心研究的结果，基本ABE首次给出了属性的概念，开创了的基于属性的加密体制的先河，虽然只是一个属性基加密体制的初步概念及方案，却为以后的研究开发了新的视野，奠定了基于属性的加密算法的基础。随后出现的密钥策略的加密机制进一步为属性基加密体制提出了划分的标准，同时引入了访问控制树的概念，加密者可以自由规定解密所需要的属性及权限，对用户的管理更加方便。而密文策略的加密机制通过使用线性秘密共享的方案来决定授权集合，增强了对访问控制的描述能力。具体三种属性基加密机制的比较如下表：名称安全性证明效率不足基本ABEShamir门限秘密共享机制；幂运算次数和双线性对数目较多。加解密均一次访问策略不能由发送方决定；不支持灵活的访问策略KP-ABE选择模型，IND-CPA;基于BDH的假设实验加密：一次双线性运算；解密：双线性运算次数等于访问控制数的节点的个数。安全证明基于的模型不够强；能够被串谋攻击CP-ABE基于BDH问题的选择集合模型；非适应性的IND-CAP。加密：0次双线性运算；解密：需要参与运算的属性的个数次双线新配对运算。难以进行非属性的扩展第三章 基于密钥策略的属性加密体制的分析第三章 基于密钥策略的属性加密体制（KP-ABE）的分析3.1相关知识3.1.1细粒度的访问控制细粒度的访问控制系统便于鉴别不同的用户组，并授予他们各种的访问权限，并允许灵细粒度的访问控制系统便于鉴别授予访问权限一组用户，并允许在指定个人用户的访问权限的灵活性。几种技术是众所周知的实施细粒度的访问控制活地指定各个用户的访问权限。目前已经有是众所周知的几种技术可以实现细粒度的访问控制。现有的技术的一个共同点是（如参考文献15，16，17，18，19，20）：他们共同使用一个受信任的服务器来详细地存储数据。访问控制的实现需要依赖于软件的协助来确保用户只能访问他被授权了的数据。从安全的角度来讲，这种情景不是特别的严密。如果服务器出现故障，比如由于软件的漏洞导致其受到攻击，会导致极大的信息泄露的危险。此外，总是难以避免的“内部攻击”也是存在的，比如有人有足够的权限，为了获取经济利益而访问服务器并窃取和泄漏信息。另外还有一些其他的技术创建了用户层次结构，要求在同一个层次结构中的一类用户共享他们的一组通用的公共密钥，然后利用公开密钥对将数据根据层次分类加密。显然，这种方法是有一些局限性的。如果第三方需要访问一组数据，那么用户需要给予这一类用户的私钥来解密，从而使其能够访问所有的条目。在许多情况下，通过使用层次结构来实现相当于单调访问树的访问控制是不现实的。在这里，我们引入新的技术来实现细粒度的访问控制。在我们的方法中，数据是存储在服务器上以加密的形式而不同用户仍然允许每个不同的数据块进行解密安全策略。这有效地消除了需要依靠存储服务器来防止未经授权的数据上的访问。秘密共享方案：秘密共享方案（SSS）用来划分一部分的秘密，为每一个用户提供一部分信息，然后用户之间有可能互相共享他们的信息来达到解密某一部分秘密的目的。因此很多秘密共享方案都有一定的措施来防止用户之间串谋来解密信息。Shamir和Blakley是最早提出建设秘密共享方案的两位学者，其中他们的接入结构是一个门限方案。也就是说，如果任何t个或更多的解密方联合到了一起，他们可以通过使用他们所有的密钥来恢复他们想要解密的秘密部分;然而，拥有的密钥数目没有达到要求的组合是不会得到任何有关的秘密信息的。不久之后，Benaloh在11中扩展了Shamir的想法，他实现了任何可以被表示的访问结构能作为门限。在SSS中，可以指定一个由不同的部分组成的树状结构的访问树，其内部节点包括AND和OR门和叶子节点。任何一组能够满足访问树的用户能联合在一起，恢复出需要解密的秘密。因此 在SSS中，不同的用户（或多方）之间的勾结是不允许的，但也是需要的。在我们设计的结构中，每个用户的密钥都与它相关联的叶子节点与伴生树共同描述他们的结构的属性。如果用户的密钥属性能够满足密文的访问结构，则用户能够解密密文。同时，在我们的设想中，只要违背了秘密共享方案，用户便不能以任何有意义的方式串谋来进行攻击。3.2关于细粒度的访问控制的一个具体方案3.2.1KP-ABE方案访问树设T是代表一个访问树的结构。树的每个非叶子节点代表一个门限，通过它的子节点和阈值来描述。如果是一个节点x的子节点的个数而KX是它的门限，则。当KX= 1时，阈值门是一个“或”门而当，则是一个“与”门。树的每一个叶子节点x由一个属性和一个阈值来描述。为了方便与访问树木的工作，该方案还定义了几个功能。方案把树中的节点x的父节点表示为parent（x）。函数att（x）定义当且仅当x是一个叶子节点才能表示在树中与该叶节点相关联的属性x。访问树T还定义了每个节点的子节点之间的顺序，即一个子节点的编号为从1到。该函数INDEX（X）返回一个与结点x相关联的数。即索引值在被给定一个密钥时已经被唯一地在接入的节点分配了相应的位置。结构设为 p阶双线性群,g作为的生成元。此外,用表示双线性映射。由安全参数决定组的大小。初始化：定义属性的全局参数。现在,对于每个属性，选择为中的任意值。最后,在中随机选择一个值为y。则公布的公共密钥PK为：。主密钥为：。加密：通过下的一组属性来加密一条消息，选择一个随机值然后发布的密文为：。密钥生成：该算法输出的关键是使用户可以根据加密的消息进行解密一组属性，当且仅当T（）=1，该算法的过程如下：首先选择一个多项式每个节点x（包括叶节点）在树T中。这些多项式被选择以下面的方式在自顶向下方式，从根节点启动r。对于树中的每个结点x，设置多项式的次数,为比该阈值少一个节点，即现在，对于根节点r，设和其他节点的多项式随机 完全定义它。对于任何其他结点x，设，并选择的其他随机节点来完全定义。解密：通过指定一个递归算法作为的解密程序。为了便于说明，只讨论算法中提出的最简单的解密算法的形式，并在下文讨论潜在的性能改进。 我们先定义一个递归算法DecryptNode（E，D，x） 那作为输入的密文，该私钥D（我们假设访问树T嵌入在私钥中）在树中的结点x上。它输出一个或。过程为：现在该算法已经定义了算法的功能DecryptNode，该解密算法简单地调用该函数上的根树。我们观察到，当且仅当所述密文满足树。一直以来，通过的解密算法简单地划分出并恢复消息M。我们将讨论如何优化解密过程中的完整版文21。3.2.2安全性证明基本已经证明了上面的计划，在属性基安全性选择集模型上简化为通过决策性BDH假设来判断算法的强健程度。定理1：如果一个攻击者可以破坏基于属性的选择 - 设置模式的系统的计划，然后就可以创建一个模拟器以一种不可忽视的优势与我们玩一个BDH抉择游戏。证明：假设存在一个可以在选择性 - 设置模型中有巨大优势攻击我们的方案时间多项式的对手 A，并且建立了一个模拟器B，它可以发挥决策性BDH游戏的优势1/2。仿真过程如下：首先，让挑战者设置组G1和G2以及一个高效的双线性映射，e和生成元g。挑战者投掷一个理想化的的两面硬币，在B的观点之外。如果= 0，则挑战者设置;否则,它就随机在A，B，C，Z中设置。前提是我们假设全局参数U已被定义。初始化：模拟器B运行A的算法。A选择一组他希望受到挑战的属性。设置：模拟器设置参数。对于所有的,均如下设置:如果,就随机选择一个并设置 (因此,);否则它选择随机一个并设置(因此,)。然后把公共参数赋予给A。步骤1：A尝试着向任何一个访问结构T查询相应的密钥，这样使得挑战并不适合T。假设A向一个T()= 0的访问结构T请求密钥，来生成私钥，B需要为访问树T中的每个节点分配一个dx的多项式Qx。下面首先定义以下两个过程:PolySat和PolyUnsat。PolySat(,)：这个过程为那些节点建立了一个具有合适的根节点的访问子树的多项式,也就是说,。这个过程需要访问树，即 一个根节点是x，一组属性和整数作为输入。它首先建立了度为多项式根结点x。先设，然后设置的其余的点随机地完全符合。现在，它为每个子结点设置多项式x通过上面的PolySat过程（，）。需要注意的是用这种方法，x中的每个子节点都有。PolyUnsat(,)：这个过程为一个具有不适合的根节点的访问树的每个节点都设置了多项式对于根节点，也就是说，。该过程采用一个具有根节点x访问树的，一组属性的和元素（）作为输入。它首先定义程度DX为根节点x定义了一个多项式，使得。由于，x中不会有大于的的子节点是符合要求的。设作为x中符合要求的子节点的数量。对于x中每一个符合要求的子节点，在这个过程中会选择一个x中随机的点中并使。然后，把中剩余的到的点随混合来完全定义。现在递归算法已经如下定义了树中其余节点的多项式。对于X中的每个子结点，算法表示为：PolySat,前提为是一个符合要求的节点。注意在这种情况下是已知的。PolyUnsat,前提为并不是一个符合要求的节点。注意由于插值在这种情况下是已知的，只有是可以得到的。注意,在这种情况下，对x中的每个子节点也成立。为了给访问结构T分配密钥，模拟器首先运行 PolyUnsat来为T的每一个节点x定义一个多项式。注意，对于T的每个叶结点x，只要x是符合要求的，我们就能完全知道;如果x不是符合要求的，那么至少是已知的，也不排除在某些情况下，可能被完全已知。此外，。模拟器现在为T的每个结点x定义了最后的多项式。需要注意这样的话，。对应于每个叶节点中的密钥是已经如下使用它的多项式给出了。令。5因此，模拟器已经能够访问结构T构建一个私钥了。此外，该私钥在T的分布是与在原方案中是相同的。挑战：对手A将向模拟器提交两份挑战消息和。模拟器则投掷 一个理想化的二元硬币，并返回的加密。则密文输出为：如果，则。如果我们让，那么我们有和。因此，密文是一个有效的随机加密的消息。否则，如果，则。然后，我们有。由于是随机的，将是一个中随机来自对手观点和消息的生成元，即不包含有关的任何信息。步骤2：模拟器与在步骤1中的表现完全相同。假设：A将提交一份的猜测。如果，模拟器将输出，以表明它被赋予了有效BDH-元组，否则它会输出，表明 它被赋予一个随机的4元组。如模拟器在公共参数和私有密钥的生成中的结构所示，他们是相同的实际的方案。在的情况下，对手没有获得任何关于的信息。因此，我们有。 由于模拟器猜测当时，我们有。如果，那么对手看到的加密。在这种情况下对手的优势根据定义是。因此，我们有。由于