支持一般电路的高效安全基于属性签名_黄振杰.pdf

支持一般电路的高效安全基于属性签名黄振杰1林志伟1,21（福建省粒计算及其应用重点实验室（闽南师范大学）福建漳州363000）2（交通运输部东海航海保障中心厦门通信中心福建厦门361026）（）Efficient and Secure Attribute-Based Signatures for General CircuitsHuangZhenjie1andLinZhiwei1,21（Fujian Key Laboratory of Granular Computing and Application(Minnan Normal University),Zhangzhou,Fujian 363000）2（Xiamen Communication Center,Donghai Navigation Safety Administration of Ministry of Transport,Xiamen,Fujian 361026）AbstractAttribute-basedsignatureisanimportantcryptographicprimitiveandhasattractedtheattentionofmanyscholars.Becauseofitsgoodproperties,attribute-basedsignaturehasfoundsignificantapplicationsinmanyfields,such as message delivery,anonymous authentication,leaking secrets,trust negotiations,private access control,anonymouscredentials,etc.Toimprovethesecurity,expressiveness,andefficiencyofattribute-basedsignature,anefficientandsecureattribute-basedsignatureschemewithperfectprivacyforgeneralcircuitsisproposedbyusingmulti-linear mapping.By introducing the concept of node weight and adopting the top-down recursive,thecomputationcostofsignaturegenerationisreduced.Thesizesofthekeysofthegatenodesarereducedbyusingthesymmetryoftheleftandrightchildnodes.Comparedwiththepreviousscheme,theproposedschemeimprovestheunforgeabilityfromexistentialunforgeableunderselectivemessageandselectiveattributeattacktoexistentialunforgeableunderadaptivechosenmessagebutselectiveattributeattack.Theproposedschemeextendstheaccessstructurefromspecialcircuitstogeneralcircuits,whichcansupportarbitraryaccessstructuresandachievearbitraryaccesscontrolgranularity.Theproposedschemekeepsthesignatureasonlyonegroupelement,shortensthesizesofthemasterpublickey,masterprivatekey,andsigningkeymarkedly,andreducesthecomputationoverheadsofsigningkeygeneration,signaturegeneration,andsignatureverificationsignificantly.Theanalysisshowsthattheproposedschemehasobviousadvantagesinperformanceandefficiencyandispractical.Key wordsattribute-basedsignature；generalcircuit；multi-linearmapping；perfectprivacy；key-policy摘要基于属性签名（attribute-basedsignature，ABS）是一种重要的密码原语，具有广泛的应用背景，得到众多学者的关注，是密码学的研究热点.为了提高基于属性签名的安全性、表达力和效率，使用多线性映射作为工具，提出一个支持一般电路的具有完善隐私性的基于属性签名方案.引入节点权重概念并采用“从上到下”递归，显著减少生成签名的计算开销；利用左右孩子节点的对称性，缩短门节点的密钥长度.所提出的方案将不可伪造性从“选定消息且选定属性攻击下存在不可伪造”提升到更强的“自适应选择消息但选定属性攻击下存在不可伪造”；将访问结构从特殊电路拓展到一般电路，可以支持任意访问结构，达到任意的访问控制粒度；在保持签名仅为 1 个群元素的前提下，显著缩短主公钥、主私钥和签名钥的大小和显著降低签名密钥生成、签名生成和验证的计算开销.分析表明：所提出的方案在性能和效率方面均有明显优势，是一个实用的方案.收稿日期：20210909；修回日期：20220419基金项目：福建省自然科学基金项目（2019J01750，2019J01752，2020J01814）ThisworkwassupportedbytheNaturalScienceFoundationofFujianProvince(2019J01750,2019J01752,2020J01814).计 算 机 研 究 与 发 展DOI：10.7544/issn1000-1239.202110920JournalofComputerResearchandDevelopment60（2）：351361，2023关键词基于属性签名；一般电路；多线性映射；完善隐私性；密钥策略中图法分类号TP309基 于 属 性 签 名（attribute-basedsignature，ABS）1是一种特殊数字签名体制，可以为用户提供细粒度的隐私保护，在多个领域有重要应用，因此成为密码学的研究热点.ABS 的隐私保护控制是通过属性和属性集上定义的访问结构实现的.根据访问结构使用位置的不同，基于属性签名分为密钥策略 ABS（key-policyattribute-basedsignature，KP-ABS）和签名策略 ABS（signature-policyattribute-basedsignature，SP-ABS）.在 KP-ABS 中，用户从属性机构（attributeauthority，AA）处获得其所拥有的访问结构所对应的签名密钥，之后可用其对属性满足其访问结构的消息进行签名.签名可以确保消息是由拥有能被指定属性满足的访问结构的用户签发的（不可伪造性），但不能辨认出签名人所拥有的具体访问结构，更不能辨认出签名人的身份（隐私性）.SP-ABS 则相反，用户从属性机构处获得其所拥有的属性所对应的签名密钥，然后对具有其属性所满足的访问结构的消息进行签名.举个简单的说明性例子：ABS 可为教学管理系统提供匿名评价功能.假设每个课程都表示为“课程名称、开课教师姓名、开课年份、开课学期”，那么每位学生所选的课程组可以表示成(C1T1Y1S1)(C2T2Y2S2)(CkTkYkSk)，其中 Ci,Ti,Yi,Si分别表示课程名称、开课教师姓名、开课年份和开课学期.在学生选定其课程组后，系统根据其所选课程组所对应的访问结构为其发放签名密钥，此后，学生可以使用其签名密钥匿名发表课程评价.ABS 的不可伪造性保证只有选修的学生才能对课程进行评价，其隐私性保证任何人都不能辨认出评价出自哪位学生.不可伪造性保证评价来源的合法性，隐私性保障评价者的隐私权.由于其良好的性质，ABS 在许多领域有重要的应用，如匿名凭证（anonymouscredentials）、消息传递（messagedelivery）、匿名认证（anonymousauthentica-tion）、秘密泄露（leakingsecrets）、信任协商（trustnego-tiations）、隐私接入控制（privateaccesscontrol）等等1-2.自 ABS 被提出以来，众多学者先后提出许多支持各种不同访问结构的方案.Shahandashti 等人2、Li等人3、Herranz 等人4和 Gagne 等人5各自提出支持门限（threshold）访问结构的 ABS 方案；Maji 等人1和Gu 等人6-7各自提出支持单调（monotone）访问结构的 ABS 方案；Okamoto 等人8-9提出支持非单调（non-monotone）访 问 结 构 的 ABS 方 案；Tang 等 人10和Sakai 等 人11各 自 提 出 电 路（circuits）访 问 结 构 的ABS 方案；Kaafarani 等人12提出无界电路（unboundedcircuits）访问结构的 ABS 方案；Zhang 等人13提出支持内积（inner-product）访问结构的 ABS 方案；Datta 等人14提出无界算术分支程序（unboundedarithmeticbranchingprograms）访问结构的 ABS 方案.为了克服 ABS 单个属性机构带来的瓶颈和信任过度集中的问题，Maji 等人1和 Okamoto 等人15分别 提 出 多 属 性 机 构（multi-authority）ABS 和 去 中 心（decentralized）ABS.为了克服 ABS 计算开销过大，不适用于资源受限场景的缺点，学者们将外包技术引入到 ABS 中来，Chen 等人16提出外包（outsourced）ABS，Mo 等人17和 Sun 等人18分别提出新的外包ABS 方案.Huang 等人19指出已有外包 ABS 方案的隐私性缺陷，进而提出具有完善隐私性的外包 ABS方案.Ren 等人20进一步提出可验证（verifiable）外包ABS；Cui 等人21和 Xiong 等人22研究了服务器辅助（server-aided）ABS；Wang 等人23提出服务器辅助验证（server-aidedverification）ABS.此外，学者们还研究了具有附加性质的 ABS，如基于属性环签名（attribute-basedringsignature）24、基于属性代理签名（attribute-basedproxysignature）25、基于属性签密（attribute-basedsigncryption）26、基于属性净化签名（attribute-basedsanitizablesignature）27等.ABS 研究的主要目标是更高的安全性、更高的效率和更强的访问结构表达力.电路是最富表达力的访问结构之一.目前已知有 3 个 ABS 方案支持电路访问结构：Tang 等人10的方案、Sakai 等人11的方案和Kaafarani 等人12的方案.文献 1112 方案的效率都很低，签名的长度都与电路的输入成线性关系.Tang等人10的方案的签名仅为 1 个群元素，效率最高，但在安全性和访问结构表达力方面却比较弱：1）Tang 等人10方案的不可伪造性是很弱的，只是在选定消息和选定属性攻击下存在不可伪造，只能防止敌手伪造特定消息的签名.2）Tang 等人10的方案仅支持特殊电路，要求兄弟节点的深度必须相同，且都是其父节点的深度加 1；要求所有输入节点的深度相同.本文改进了 Tang 等人10的方案，提高了安全性、352计算机研究与发展2023，60（2）丰富了访问结构表达力、缩短了数据长度并降低了计算开销.本文的主要贡献包括 3 个方面:1）增强方案的安全性.从“选定消息和选定属性攻击下存在不可伪造（existentiallyunforgeableunderselectivemessageattackandselectiveattribute,EUF-sA-sMA）”提升到“自适应选择消息但选定属性攻击下存在不可伪造（existentiallyunforgeableunderadaptivechosen message but selective attribute attack,EUF-sA-CMA）”.EUF-sA-CMA 比 EUF-sA-sMA 强很多，能防止敌手伪造任何自适应选择消息的签名.2）丰富了访问结构表达力，将访问结构从特殊电路拓展到一般电路.去掉原有的所有限制，允许兄弟节点的深度不同；允许孩子节点的深度比其父节点的深度大于 1，即可以跳层；允许输入节点的深度不同.另外，任意电路都可以通过德摩根（DeMorgan）定律转换成非叶子节点为“或门”或“与门”，“非门”只出现在叶子节点的电路.如果将带“非门”的叶子节点定义为 1 个新属性（比如“不是教授”）作为 1 个新的输入，就可以支持非单调电路.一般电路的极强表达能力使得方案可支持任意访问结构，达到任意的访问控制粒度.3）缩短了数据长度并降低了计算开销.在保持签名大小仅为 1 个群元素的前提下，将主公钥、主私钥和签名钥的大小都显著缩短；将签名密钥生成、签名生成和签名验证的计算开销都显著降低.1预备知识 1.1符号说明本文使用的符号和参数的含义如表 1 所示.1.2多线性映射与困难性假设G(1,k)kpG1,G2,Gkg1,g2,gkei,j：GiGj Gi+j1 i k1 1 j k1,i+j k，多线性映射.为群生成算法，输入安全参数 和多线性映射级数，输出素数阶群序列和相应的生成元，以及双线性映射序列，,满足ei,j(gai,gbj)=gabi+j:a,b Zp.多线性映射定义为e(a1,a2,an)=e(a1,e(a2,e(an1,an)，ei,j其中右侧的 e 为其输入所对应的双线性映射.p,G1,G2,Gk,e,gc1,gc2,gckgki=1cik1c1,c2,ckRZpk-MCDH（k-multilinear computational Diffie-Hell-man）问题.给定（），计算，其中.Ak-MCDH 假设.任意概率多项式时间算法成功解 k-MCDH 问题的概率都是可忽略的.1.3电路nqG=wn+1,wn+2,wn+qN=IGwtop=wn+qwL(w)R(w)GT(w)wf=(n,q,L,R,GT)假设电路有 个输入节点，个门节点，记输入节点集合为 I=1,2,n，门节点集合为，所 有 节 点 集 合 为，其 中为头部节点.门节点的左、右孩子节点分别记为和.表示门节点的类型，即“AND”或“OR”.电路记为.Table 1Symbols Interpretation表 1 符号释义符号含义系统安全参数k多线性映射的级数p(21,2)中的素数Zpp模素数的整数集aRAAa从集合中随机选取Gi乘法循环群giGi乘法循环群的生成元e多线性映射（含双线性映射）e(A)输入为 A 时多线性映射 e 的值f电路n电路的输入数q电路的门节点数电路的最大深度I电路的输入节点集G电路的门节点集N电路的节点集L(w)w门节点的左孩子R(w)w门节点的右孩子GT(w)w门节点类型函数，输出的门类型D(w)=iww节点的深度电路的输入f()f输入为时电路的输出fw()fw输入为时中门节点的输出Ww()fw输入为时中节点的权重1,n1,2,n表示集合0,1n长度为 n 的比特串集合0,1任意长度比特串的集合M消息签名黄振杰等：支持一般电路的高效安全基于属性签名353D(w)wf()0,1nff()=1fffw()fw表示节点的深度.头部节点的深度为 0，其他节点的深度为其到头部节点的最长路的长度.表示输入为时，电路的输出.当时，称 满足；否则，称不满足.类似地，表示输入为 时，电路 中门节点 的输出.Ww()为了有效降低计算开销，本文为电路引入节点权重的概念，用表示在输入为时节点 w 的权重，其计算方法如 1）3）：1）输入节点.Ww()=n1输入为 1 的节点，；Ww()=输入为 0 的节点，.2）或门.fw()=0Ww()=如果，则；Ww()=minWL(w)(),WR(w)()+2否则.3）与门.fw()=0Ww()=如果，则；否则：D(L(w)=D(R(w)如果，则Ww()=WL(w)()+WR(w)()+2；D(L(w)D(R(w)如果，则Ww()=WL(w)()+WR(w)()+3.这样定义的节点权重其实就是使用本文方案生成签名时，使用该节点所需要计算的对运算的数量.对运算越少，效率就越高.图 1 给出一个一般电路的说明性例子：65552512111111113n=6,q=7,I=1,2,3,4,5,6,G=w7,w8,w9,w10,w11,w12,w13L(w9)=1,R(w9)=2,GT(w9)=AND,D(w9)=2=(1,1,0,1,1,0),f()=fw13()=1,fw9()=1,Ww9()=13节点左侧为其编号,右侧为其权重,线上的数为节点的输出,叶子节点下方的数为其输入.40111717150013521w8w10w11wtop=w13w12w9w7深度 0深度 1深度 2深度 3深度 4Fig.1Exampleofgeneralcircuit图1一般电路示例 2电路访问结构密钥策略 ABS本节给出访问结构为电路的密钥策略 ABS 的定义和安全模型.2.1算法组成电路访问结构密钥策略 ABS 方案由 1）4）算法组成：1n1）Setup(,n,).输入安全参数、电路输入数 和最大深度，输出系统公开参数 pp 和系统主私钥 msk.ffSKf2）KeyGen(pp,msk,f).输入系统公开参数 pp、系统主私钥 msk 和电路，输出电路所对应的签名密钥.SKfSKf3）Sign(pp,M,).输入公开参数 pp、签名密钥、消息 M 及其属性，输出关于(M,)的签名.4）Verify(pp,M,).输入公开参数 pp、消息 M、属性 和签名.如果是关于(M,)的有效签名，输出 1；否则，输出 0.2.2安全性模型Mf()=1f定义 1.正确性.一个电路访问结构的密钥策略ABS 方案是正确的，如果对于任意的消息和满足的任意属性 与电路 都有概率，则Pr|Verify(M,)=1|(pp,msk)Setup(1,n,),SKfKeyGen(pp,msk,f),Sign(pp,SKf,M,)|=1.不可伪造性.大多数 ABS 的文献使用如下不可伪造性定义，其形式化模型如 Game1：Game1（EUF-sA-CMA）.FC1）Initialization.敌手选择挑战属性并发送给挑战者.CF2）Setup.挑战者生成系统公开参数 pp 并发送给敌手.FfC CfSKfF3）KeyGenOracle.敌 手提 交 电 路给 挑 战 者.返回电路 的密钥给.FMC CM F4）SignOracle.敌手提交消息和属性 给挑战者.返回(,)的签名 给.F*,M*,5）Forgery.敌手输出().如果下面都满足，称敌手赢得 Game1.*M*是关于消息和属性的有效签名；M*,*()没有被询问过 SignOracle；ff()=0 任 何 询 问 过 KeyGen Oracle 的 电 路都 使.FAdvEUF-sA-CMAABS,敌手的优势定义为其赢得 Game1的概率.FAdvEUF-sA-CMAABS,F定义 2.一个电路访问结构密钥策略 ABS 方案称为自适应选择消息但选定属性攻击下存在不可伪造的；如果对于任何多项式时间敌手，其赢得 Game1的优势是可忽略的.354计算机研究与发展2023，60（2）Tang 等人10方案的不可伪造性是很弱的“选定消息和选定属性攻击下存在不可伪造”，其 Game 和Game1 基本相同，只是 Initialization 应改为：FMCInitialization.敌手选择并发送挑战消息和挑战属性给挑战者.完善隐私性.本文方案和 Tang 等人10方案都实现了完善隐私性，任何敌手即使拥有无限的计算能力也无法识别用于生成签名的电路.Mf0()=f1()=1f0,f1f0和f1定义 3.如 果 对 于 任 何，和 满 足的，使用所产生的签名分布0 Sign(SKf0,M,),1 Sign(SKf1,M,)是信息论意义不可区分的，则称该电路访问结构密钥策略 ABS 方案具有完善隐私性.3一般电路密钥策略 ABS 方案本节提出一个支持一般电路的密钥策略ABS 方案.3.1主要设计思想本文方案是基于 Tang 等人10方案改进而来的，改进的主要思想如 1）4）所描述：1）以唯一的头部节点为参照原点，其他节点都参照它进行定位，以便支持一般电路.而 Tang 等人10方案采用叶子（输入）节点为参照原点，所以需要假设所有输入节点均有相同的深度.EwEwEw2）引入节点权重的概念并采用“从上到下”递归的方式计算签名，只计算必须计算的且权重较小的节点的.而 Tang 等人10方案“自下而上”计算所有输出为 1 的节点的，许多不必要的也计算了，浪费了计算资源.3）充分利用左右孩子节点的对称性，将孩子节点同深度的门节点的密钥都减少了 1 个分量，“或门”的密钥减少了 25%，“与门”的密钥减少了 33.33%.孩子节点有不同深度的门节点的密钥没有减少，只是为了在安全性证明中方便仿真密钥.实际使用时同深度和不同深度的门节点可不加区别，都减少 1 个分量.4）通过使用安全 Hash 函数，将不可伪造性提升到“自适应选择消息但选定属性攻击下存在不可伪造”，同时将主公钥和主私钥长度各减少 2m 个元素（m 为消息的长度）.3.2签名方案本文所提出的一般电路密钥策略 ABS 方案的算法为：Setup.输入安全参数、电路最大深度 和电路输n入数.G(1,k=n+3)G1,G2,Gkg1(g=g1),g2,gke1）运行得到阶为素数 p 的群序列和对应的生成元序列，以及其上的多线性映射.ai,RZpi 1,n,0,1Ai,=gai,a=a1,0,a1,1,a2,0,a2,1,an,0,an,1A=A1,0,A1,1,A2,0,A2,1,An,0,An,12）随机选取，计算.记，.RZPY=g+23）随机选取，计算.H:0,1 G14）选取防碰撞 Hash 函数.pp=Y,A,n,p,G1,G2,Gk,g1,g2,gk,e,H,a输 出 系 统 公 开 参 数和主私钥 msk=.KeyGen.输入系统公开参数 pp、系统主私钥 msk和电路 f=(n,q,L,R,GT).vwtop=vwRZpw NwtopzwRZpw G1）令，随 机 选 取,和,.Kw2）采用“自下而上”的方式计算密钥组成部分.w I=1,n D(w)=iw输入节点.，计算Kw=gvwaw,1iw+2.w G GT(w)=ORD(w)=iw或门.，.D(L(w)=D(R(w)iL(w)=iR(w)（i）如果,即,计算Kw,1=gzwiL(w)iw,Kw,2=gvwzwvL(w)iw+1,Kw,3=gvwzwvR(w)iw+1.Kw=(Kw,1,Kw,2,Kw,3)令.D(L(w)D(R(w)zwRZp（ii）如果,选取,计算Kw,1=gzwiL(w)iw,Kw,1=gzwiR(w)iw，Kw,2=gvwzwvL(w)iw+1,Kw,3=gvwzwvR(w)iw+1.Kw=(Kw,1,Kw,1,Kw,2,Kw,3)令.w G GT(w)=ANDD(w)=iw与门.，.D(L(w)=D(R(w)iL(w)=iR(w)（i）如果,即,计算Kw,1=gzwiL(w)iw,Kw,2=gvwzw(vL(w)+vR(w)iw+1.Kw=(Kw,1,Kw,2)令.D(L(w)D(R(w)zwRZp（ii）如果,选取,计算Kw,1=gzwiL(w)iw,Kw,1=gzwiR(w)iw，Kw,2=gvw(zwvL(w)+zwvR(w)iw+1.Kw=(Kw,1,Kw,1,Kw,2)令.黄振杰等：支持一般电路的高效安全基于属性签名355SKf=KwwN3）输出签名密钥.SKf=(1,2,n)0,1nf()f()=0f()=1EwSign.输入公开参数 pp、签名密钥、消息 M和属性，计算和各节点的权重.如果，无法签名，停止；如果，按“从上到下”递归方法计算必要节点的.E=e(Ai,ii1,n)1）计算.w G GT(w)=OR2）或门.，.WL(w)()WR(w)()EL(w)如果，调用其左孩子节点的，计算Ew=e(EL(w),Kw,1)e(Kw,2,E).ER(w)否则，调用其右孩子节点的.D(L(w)=D(R(w)如果，计算Ew=e(ER(w),Kw,1)e(Kw,3,E)；D(L(w)D(R(w)如果，计算Ew=e(ER(w),Kw,1)e(Kw,3,E).w G GT(w)=ANDEL(w)ER(w)3）与门.，调用其孩子节点的和.D(L(w)=D(R(w)如果，计算Ew=e(EL(w)ER(w),Kw,1)e(Kw,2,E)；D(L(w)D(R(w)如果，计算Ew=e(EL(w),Kw,1)e(ER(w),Kw,1)e(Kw,2,E).w I4）输入节点.计算Ew=e(Kw,Ai,ii1,nw).5）计算并输出签名=e(H(M),Ewtop).MVerify.输入待验证的签名及相应的消息和属性.如果等式e(,g)=e(H(M),Y,Ai,ii1,n)成立，输出 1；否则，输出 0.4安全性证明与性能效率分析本节证明所提出方案的安全性，并分析其性能和效率.4.1安全性证明定理 1.本文所提出的一般电路密钥策略基于属性签名方案是正确的.fw()=1EwEw=gvw()n+iw+1()=i1,nai,i证明.容易知道，在签名递归过程所有被计算的节点都有.下面，用数学归纳法证明签名生成 过 程 中 所 有 的都 有，其 中.ww I D(w)=iw1）当 为输入节点时，即，有Ew=e(Kw,Ai,ii1,nw)=e(gvwaw,1iw+2,gi1,nwai,in1)gvw()n+iw+1.EL(w)=gvL(w)()n+iL(w)+1ER(w)=gvR(w)()n+iR(w)+1Ew=gvw()n+iw+12）假设和成立，那么有成立.w G GT(w)=OR或门.，.（i）如果是调用左孩子节点，有Ew=e(EL(w),Kw,1)e(Kw,2,E)=e(gvL(w)()n+iL(w)+1,gzwiL(w)iw)e(gvwzwvL(w)iw+1,g()n)=gvw()n+iw+1.（ii）如果是调用右孩子节点，且D(L(w)=D(R(w)，有Ew=e(ER(w),Kw,1)e(Kw,3,E)=e(gvR(w)()n+iR(w)+1,gzwiR(w)iw)e(gvwzwvR(w)iw+1,g()n)=gvw()n+iw+1.D(L(w)D(R(w)（iii）如果是调用右孩子节点，但，有Ew=e(EL(w),Kw,1)e(Kw,3,E)=e(gvR(w)()n+iR(w)+1,gzwiR(w)iw)e(gvwzwvR(w)iw+1,g()n)=gvw()n+iw+1.w G GT(w)=AND与门.，.D(L(w)=D(R(w)iL(w)=iR(w)（i）如果，即,有Ew=e(EL(w)ER(w),Kw,1)e(Kw,2,E)=e(gvL(w)()n+iL(w)+1gvR(w)()n+iR(w)+1,gzwiL(w)iw)e(gvwzw(vL(w)+vR(w)iw+1,g()n)=gvw()n+iw+1.D(L(w)D(R(w)（ii）如果，有Ew=e(EL(w),Kw,1)e(ER(w),Kw,1)e(Kw,2,E)=e(gvL(w)()n+iL(w)+1,gzwiL(w)iw)e(gvR(w)()n+iR(w)+1,gzwiR(w)iw)e(gvw(zwvL(w)+zwvR(w)iw+1,g()n)=gvw()n+iw+1.Ew=gvw()n+iw+1由数学归纳法可知：对所有被计算的节点都成立.w=wtopvw=iw=D(w)=0当时，有，所以有Ewtop=g()n+1 Gn+1.从而有e(,g)=e(e(H(M),Ewtop),g)=e(e(H(M),g()n+1),g)=e(H(M),g+2,g()n)=e(H(M),Y,Ai,ii1,n).验证方程成立，所提出的方案是正确的.证毕.定理 2.如果 k-MCDH 假设成立，则所提出的一般电路密钥策略 ABS 方案是自适应选择消息但选定属性攻击下存在不可伪造的.FCBF证明.假设是具有优势 的 EUF-sA-CMA 敌手，是 k-MCDH 问题的挑战者，我们构建如下的算法，利用来解 k-MCDH 问题.BLHqs维护一个初始化为空的列表.令为查询SignOracle 的最大次数.k-MCDHGen.CG(1,k=n+3)1）运行得到阶为素数 p 的群356计算机研究与发展2023，60（2）G1,G2,Gkg1,g2,gke序列和对应的生成元序列，以及其上的多线性映射.gc1,gc2,gck G12）随机选取.(n,p,G1,G2,Gk,g1(g=g1),g2,gk,e,gc1,gc2,gck)B3）发送给.F=(1,2,n)BInitialization.敌手选取并发送挑战属性给.Setup.Y=e(gcn+1,gcn+2,gcn+2)=cn+1cn+2cn+21）令.这里隐含地令.aiRZp2）选取，并令Ai,=gci,i=，gai,i，i 1,n,0,1，A=Ai,i1,n,0,1.i=ai,=ci当时，隐含地令.Bpp=Y,A,n,p,G1,G2,Gk,g1,g2,gk,eF3）发 送 公 开 参 数给敌手.Ff()=1KwKeyGenOracle.当敌手询问关于电路 f=(n,q,L,R,GT)的密钥时，如果，拒绝；否则，采用“自下而上”的方式计算密钥组成部分.w I D(w)=iw1）输入节点.，.w=1vwRZp如果，选取，计算Kw=e(giw+1,Aw,1)vw=gvwaw,1iw+2.w=0wRZp如果，选取，计算Kw=(e(gcn+1,gcn+2,gcn+iw+2)gwiw+2)aw=g(cn+1cn+2cn+iw+2+w)aw,1iw+2=gvwaw,1iw+2.vw=cn+1cn+2cn+iw+2+w这里隐含地令.w G GT(w)=ORD(w)=iw2）或门.，.fw()=1zw,vwRZp如果，选取.Kw,1=gzwiL(w)iw（i）计算.D(L(w)D(R(w)zwRZpKw,1=gzwiR(w)iw（ii）如 果,选 取,计 算.fL(w)()=1Kw,2=gvwzwvL(w)iw+1（iii）如果，计算.fL(w)()=0vL(w)=cn+1cn+2cn+iL(w)+2+L(w)（iv）如 果，此 时，计算Kw,2=gvwL(w)zwiw+1e(gcn+1,gcn+2,gcn+iL(w)+2,gzwiL(w)iw1)=gvwzw(cn+1cn+2cn+iL(w)+2+L(w)iw+1=gvwzwvL(w)iw+1.fR(w)()=1（v）如果，计算Kw,3=|gvwzwvR(w)iw+1,D(L(w)=D(R(w),gvwzwvR(w)iw+1,D(L(w)D(R(w).fR(w)()=0vR(w)=cn+1cn+2cn+iR(w)+2+R(w)D(L(w)=D(R(w)zw（vi）如 果，此 时.如果，使用；否则，zw使用，计算Kw,3=gvwR(w)zwiw+1e(gcn+1,gcn+2,gcn+iR(w)+2,gzwiR(w)iw1)=gvwzw(cn+1cn+2cn+iw+2+R(w)iw+1=gvwzwvR(w)iw+1.fw()=0fL(w)()=fR(w)()=0vL(w)=cn+1cn+2cn+iL(w)+2L(w)vR(w)=cn+1cn+2cn+iR(w)+2+R(w)w,wRZpw=wtop=wn+qn+q=0如 果，则，有+和.选取（如果，令，下同）.D(L(w)=D(R(w)iL(w)=iR(w)（i）如果,即,计算Kw,1=e(gcn+iL(w)+3,gcn+iL(w)+4,gcn+iw+2)gwiL(w)iw=gzwiL(w)iw，Kw,2=gwiw+1e(gcn+iL(w)+3,gcn+iw+2,gL(w)iL(w)+1)(e(gcn+1,gcn+2,gcn+iL(w)+2,giL(w)iw1)gL(w)iw+1)w=gw(cn+iL(w)+3cn+iw+2)L(w)w(cn+1cn+2cn+iL(w)+2)wL(w)iw+1=g(cn+1cn+2cn+iL(w)+2+w)iw+1g(cn+iL(w)+3cn+iw+2+w)(cn+1cn+2cn+iL(w)+2+L(w)iw+1=gvwzwvL(W)iw+1.Kw,3Kw,2的仿真同，只是得将 L(w)改为 R(w).zw=cn+iL(w)+3cn+iL(w)+4cn+iw+2+wvw=cn+1cn+2cn+iw+2+w这里隐含地令,.D(L(w)D(R(w)Kw,1Kw,2Kw,3Kw,1,Kw,2,Kw,3（ii）如果,的仿真同(i)中的Kw,1=e(gcn+iR(w)+3,gcn+iR(w)+4,gcn+iw+2)gwiR(w)iw=gzwiR(w)iw.zw=cn+iL(w)+3cn+iL(w)+4cn+iw+2wzw=cn+iR(w)+3cn+iR(w)+4cn+iw+2+wvW=cn+1cn+2cn+iw+2+w这 里 隐 含 地 令+,，.iL(w)iR(w)zwzw(i)和(ii)的区别在于与是否相等，如果相等则与相同，不必区别处理；否则必须区别处理.D(L(w)=D(R(w)Kw=Kw,1,Kw,2,Kw,3Kw=Kw,1,Kw,1,Kw,2,Kw,3如果，令；否则，令.w G GT(w)=ANDD(w)=iw3）与门.，.fw()=1D(L(w)=D(R(w)zw,vwRZp如 果且,选 取，计算Kw,1=gzwiL(w)iw，Kw,2=gvwzw(vL(w)+vR(w)iw+1.fw()=1D(L(w)D(R(w)zw,zw,vwRZp如 果但,选 取,计算Kw,1=gzwiL(w)iw,Kw,1=gzwiR(w)iw,Kw,2=gvw(zwvL(w)+zwvR(w)iw+1.黄振杰等：支持一般电路的高效安全基于属性签名357fL(w)()=fR(w)()=0vL(w)=cn+1cn+2 cn+iL(w)+2L(w)vR(w)=cn+1 cn+2 cn+iR(w)+2+R(w)w,wRZp如果，此时有+和.选取.D(L(w)=D(R(w)iL(w)=iR(w)（i）如果,即,计算Kw,1=e(gcn+iL(w)+3,gcn+iw+2)21gwiL(w)iw=gzwiL(w)iw，Kw,2=gww(L(w)+R(w)iw+1e(gcn+iL(w)+3,gcn+iw+2,g21(L(w)+R(w)iL(w)+1)e(gcn+1,gcn+2,gcn+iL(w)+2,giL（w）iw1)2w=gww(L(w)+R(w)21(cn+iL(w)+3cn+iw+2)(L(w)+R(w)iw+1g2w(cn+1cn+2cn+iL(w)+2)iw+1=g(cn+1cn+2cn+iw+2+w)iw+1g(21(cn+iL(w)+3cn+iw+2)+w)(2cn