1、支持一般电路的高效安全基于属性签名黄振杰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 36
2、3000）2（Xiamen Communication Center,Donghai Navigation Safety Administration of Ministry of Transport,Xiamen,Fujian 361026）AbstractAttribute-basedsignatureisanimportantcryptographicprimitiveandhasattractedtheattentionofmanyscholars.Becauseofitsgoodproperties,attribute-basedsignaturehasfoundsignifican
3、tapplicationsinmanyfields,such as message delivery,anonymous authentication,leaking secrets,trust negotiations,private access control,anonymouscredentials,etc.Toimprovethesecurity,expressiveness,andefficiencyofattribute-basedsignature,anefficientandsecureattribute-basedsignatureschemewithperfectpriv
4、acyforgeneralcircuitsisproposedbyusingmulti-linear mapping.By introducing the concept of node weight and adopting the top-down recursive,thecomputationcostofsignaturegenerationisreduced.Thesizesofthekeysofthegatenodesarereducedbyusingthesymmetryoftheleftandrightchildnodes.Comparedwiththeprevioussche
5、me,theproposedschemeimprovestheunforgeabilityfromexistentialunforgeableunderselectivemessageandselectiveattributeattacktoexistentialunforgeableunderadaptivechosenmessagebutselectiveattributeattack.Theproposedschemeextendstheaccessstructurefromspecialcircuitstogeneralcircuits,whichcansupportarbitrary
6、accessstructuresandachievearbitraryaccesscontrolgranularity.Theproposedschemekeepsthesignatureasonlyonegroupelement,shortensthesizesofthemasterpublickey,masterprivatekey,andsigningkeymarkedly,andreducesthecomputationoverheadsofsigningkeygeneration,signaturegeneration,andsignatureverificationsignific
7、antly.Theanalysisshowsthattheproposedschemehasobviousadvantagesinperformanceandefficiencyandispractical.Key wordsattribute-basedsignature；generalcircuit；multi-linearmapping；perfectprivacy；key-policy摘要基于属性签名（attribute-basedsignature，ABS）是一种重要的密码原语，具有广泛的应用背景，得到众多学者的关注，是密码学的研究热点.为了提高基于属性签名的安全性、表达力和效率，使
8、用多线性映射作为工具，提出一个支持一般电路的具有完善隐私性的基于属性签名方案.引入节点权重概念并采用“从上到下”递归，显著减少生成签名的计算开销；利用左右孩子节点的对称性，缩短门节点的密钥长度.所提出的方案将不可伪造性从“选定消息且选定属性攻击下存在不可伪造”提升到更强的“自适应选择消息但选定属性攻击下存在不可伪造”；将访问结构从特殊电路拓展到一般电路，可以支持任意访问结构，达到任意的访问控制粒度；在保持签名仅为 1 个群元素的前提下，显著缩短主公钥、主私钥和签名钥的大小和显著降低签名密钥生成、签名生成和验证的计算开销.分析表明：所提出的方案在性能和效率方面均有明显优势，是一个实用的方案.收稿
9、日期：20210909；修回日期：20220419基金项目：福建省自然科学基金项目（2019J01750，2019J01752，2020J01814）ThisworkwassupportedbytheNaturalScienceFoundationofFujianProvince(2019J01750,2019J01752,2020J01814).计 算 机 研 究 与 发 展DOI：10.7544/issn1000-1239.202110920JournalofComputerResearchandDevelopment60（2）：351361，2023关键词基于属性签名；一般电路；多线性映
10、射；完善隐私性；密钥策略中图法分类号TP309基 于 属 性 签 名（attribute-basedsignature，ABS）1是一种特殊数字签名体制，可以为用户提供细粒度的隐私保护，在多个领域有重要应用，因此成为密码学的研究热点.ABS 的隐私保护控制是通过属性和属性集上定义的访问结构实现的.根据访问结构使用位置的不同，基于属性签名分为密钥策略 ABS（key-policyattribute-basedsignature，KP-ABS）和签名策略 ABS（signature-policyattribute-basedsignature，SP-ABS）.在 KP-ABS 中，用户从属性机构（
11、attributeauthority，AA）处获得其所拥有的访问结构所对应的签名密钥，之后可用其对属性满足其访问结构的消息进行签名.签名可以确保消息是由拥有能被指定属性满足的访问结构的用户签发的（不可伪造性），但不能辨认出签名人所拥有的具体访问结构，更不能辨认出签名人的身份（隐私性）.SP-ABS 则相反，用户从属性机构处获得其所拥有的属性所对应的签名密钥，然后对具有其属性所满足的访问结构的消息进行签名.举个简单的说明性例子：ABS 可为教学管理系统提供匿名评价功能.假设每个课程都表示为“课程名称、开课教师姓名、开课年份、开课学期”，那么每位学生所选的课程组可以表示成(C1T1Y1S1)(C2
12、T2Y2S2)(CkTkYkSk)，其中 Ci,Ti,Yi,Si分别表示课程名称、开课教师姓名、开课年份和开课学期.在学生选定其课程组后，系统根据其所选课程组所对应的访问结构为其发放签名密钥，此后，学生可以使用其签名密钥匿名发表课程评价.ABS 的不可伪造性保证只有选修的学生才能对课程进行评价，其隐私性保证任何人都不能辨认出评价出自哪位学生.不可伪造性保证评价来源的合法性，隐私性保障评价者的隐私权.由于其良好的性质，ABS 在许多领域有重要的应用，如匿名凭证（anonymouscredentials）、消息传递（messagedelivery）、匿名认证（anonymousauthentica
13、-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 方 案；
14、Tang 等 人10和Sakai 等 人11各 自 提 出 电 路（circuits）访 问 结 构 的ABS 方案；Kaafarani 等人12提出无界电路（unboundedcircuits）访问结构的 ABS 方案；Zhang 等人13提出支持内积（inner-product）访问结构的 ABS 方案；Datta 等人14提出无界算术分支程序（unboundedarithmeticbranchingprograms）访问结构的 ABS 方案.为了克服 ABS 单个属性机构带来的瓶颈和信任过度集中的问题，Maji 等人1和 Okamoto 等人15分别 提 出 多 属 性 机 构（mult
15、i-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提出服务器辅助验
16、证（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 等人
