基于国产密码算法SM9的可追踪属性签名方案

唐 飞 凌国玮 单进勇

①(重庆邮电大学计算机科学与技术学院 重庆 400065)

②(重庆邮电大学网络空间安全与信息法学院 重庆 400065)

③(北京数牍科技有限公司 北京 100083)

1 引言

面向网络空间安全自主可控的战略需求，我国自主研发了一系列商用密码方案，最为常用的商密方案包括SM2算法[1]、SM3算法[2]、SM4算法[3]、SM9算法[4]。其中，SM9算法是标识密码方案，即为基于身份的密码(Identity-Based Cryptography,IBC)方案，由国家密码管理局于2016年正式发布。它是一种基于双线性映射的标识密码方案，同时也是我国商用密码中的第1个标识密码方案。在标识密码方案中，用户的私钥由密钥生成中心(Key Generation Center, KGC)根据主密钥和用户标识计算得出，用户的公钥由用户标识充当，从而不需要证书中心对用户公钥进行真实性认证。与基于公钥基础设施(Public Key Infrastructure, PKI)的密码方案(例如SM2算法[1]、ElGamal等[5])相比，标识密码方案中的密钥管理环节可以适当得到简化。

近年来，SM9密码方案逐步受到各界关注，涌现了一系列基于SM9密码方案的相关工作。2017年，杨亚涛等人[6]基于SM9设计了可证明安全的区块链隐私保护方案。2018年，马晓婷等人[7]基于SM9设计了区块链技术的跨域认证方案。2019年，林超等人[8]基于SM9设计了范围证明协议。2020年，Mu等人[9]设计了两方协作的SM9签名方案；涂彬彬等人[10]对SM9的密钥生成进行分布式门限化设计；魏荣等人[11]实现了支持SM9的JavaScript通用密码库。2021年，赖建昌等人[12,13]基于SM9分别设计了广播加密方案与签密方案；Ji等人[14]基于SM9加密算法设计了用于云上访问控制的属性加密方案。

属性签名(Attribute-Based Signature, ABS)方案是属性加密方案(Attribute-Based Encryption,ABE)的扩展[15]，正式定义由Maji等人[16]提出。在ABS方案中，签名者对消息进行签名时，使用某一签名策略对消息签名。验证者则可以验证该签名是否满足签名者声明的签名策略。此外，为保护签名者隐私，验证者只能确定签名者的属性满足相应的签名策略，而不能确定是签名者的哪些属性满足该签名策略。ABS方案能够实现细粒度的访问控制，现已被看作一种重要的匿名认证手段，主要应用于工业物联网中边缘节点的数据隐私保护[17]；用户对于自身数据在隐私计算中的个人数据授权[18]；区块链中的数据访问控制[19]等。

ABS方案根据访问策略可分为门限访问策略与树形访问策略等，其中树形访问策略相较于门限访问策略能提供更加细粒度的访问控制机制，使用户的访问权限更为灵活，树形访问策略的ABS方案如文献[20,21]等。为了防止签名滥用，将身份追踪功能加入到ABS方案中是有必要的，即给定一个签名，KGC能够通过该签名恢复出签名者的真实身份信息。否则，签名者可能会利用属性签名的匿名性进行非法签名，因为如果没有人能够知晓签名者的真实身份，那么溯源追责也无法实现。由此可见，可追踪的ABS方案非常具有吸引力。除此之外，现有的ABS方案的验签效率普遍偏低，原因是现有的属性签名的验签算法的计算复杂度通常与策略规模(策略的属性个数)呈线性关系，且至少需要多次的双线性对映射以及指数运算[20–23]，而这两种基本运算均是较为耗时的。因此，设计验签开销与属性策略复杂程度无关且高效的属性签名方案同样是很有必要的。

如上所述，目前缺乏基于国密标准的ABS方案，且存在现有的ABS方案验签效率普遍偏低。针对这一问题，本文凝练SM9签名方案的核心技术，提出一种基于国密SM9的可追踪身份属性签名方案。本文的主要贡献如下：

(1) 基于国密SM9构造了属性签名方案，该方案同时具有树形访问策略、身份追踪的功能。

(2) 安全性方面，形式化安全性证明表明所提方案在随机谕言机模型下具有不可伪造性，同时也可抗合谋攻击。

(3) 效率方面，通过方案对比分析表明本文所提方案的签名开销与验签开销相较于现有的可追踪ABS方案具有较大优势。其中，完成1次本文所提方案的验签操作仅需要各做1次指数运算以及双线性对映射。同时编程实现了所提方案，通过实验验证了所提方案的高效性。实验结果表明，验签算法的计算复杂度与策略规模无关，完成1次验签操作仅需2 ms。

2 预备知识与定义

2.1 双线性映射与复杂性假设

2.2 树形访问策略的可追踪属性签名方案

Escala等人[26]提出了可追踪ABS方案的定义，即KGC可通过签名追踪到签名者的具体身份，避免了传统ABS方案中无条件匿名性下的签名滥用问题，可追踪的ABS方案如文献[21,22]。

一个树形访问策略的可追踪属性签名方案包含以下5个算法。

2.3 拉格朗日插值

2.4 属性树

3 基于国密SM9的可追踪属性签名方案

本节基于国密SM9构造可追踪身份的属性签名方案，该方案支持树形访问策略，并对该方案进行了安全性分析以及功能与效率方面的分析。

3.1 方案构造

3.2 安全性分析

从上述计算过程可以看出，本方案的合法签名能够通过验证算法。

定理2 不可伪造性。若密码杂凑函数H1是随机谕言机，如果τ-SDH问题是难解的，那么基于国密SM9的可追踪属性签名方案的签名是不可伪造的。

证明 如果存在一个概率多项式敌手A能以不可忽略的优势ε伪造基于国密SM9的可追踪属性签名方案的签名，则可以构造一个挑战者C以不可忽略的优势解决τ-SDH问题。

3.3 功能与效率分析

本节给出所提方案与现有的属性签名方案在功能与效率两方面的对比。为保证本文所提属性签名方案的高效性，将对所提方案的系统建立、用户密钥生成、签名、验签等操作进行逐一实验。由于属性签名方案的效率通常与策略复杂度相关，因此本节还会分析属性策略的复杂程度与以上4种操作的关系。测试的硬件平台采用Intel i7-1165G7处理器、内存为16 GB、主频为2.8 GHz。操作系统为Ubuntu18.04，编程语言是Go1.19。

首先，本文比较现有的ABS方案与所提方案在功能方面的对比，如表1所示。从中可以看出，所提方案是同时支持可追踪身份功能与树形访问策略的。

表1 与现有的ABS方案的功能对比

为了保证所提方案的高效性，表2给出了所提方案与现有的ABS方案的效率分析对比。计算开销仅统计最为耗时的指数运算、标量乘运算、双线性映射运算。AID代表签名者拥有的属性集，SΥ代表签名策略Υ的属性集，exp代表群GT上的指数运算，sca1代表群G1上的标量乘运算，E表示一次双线性映射运算，ξ代表属性树T的非叶子节点个数，d代表门限访问策略的门限值。

表2 与现有的ABS方案的效率对比

为了更好地展现本文方案在签名开销与验签开销上的优势，本文给出群G1,G2上的标量乘运算sca1, sca2、群GT上的指数运算exp、双线性运算E这4种基本运算的运行效率，如表2所示。

结合表2与表3，可以明显看出所提方案在签名开销、验证开销上具有较大的优势。其中，在签名开销方面，由于sca1相较于e xp的计算开销要小许多，因此可以明显看出所提方案的签名开销相较于现有的ABS方案更具优势；在验签开销上，所提方案仅需要1次双线性映射和1次指数运算，效率优势更加明显。

除了理论分析以外，本文编程实现了本文所提方案并对方案的效率进行了测试。由于属性签名方案的效率往往与属性策略Υ的规模有关，因此属性签名方案的运行效率一般是基于具体的策略下的。为了不失一般性，本文以策略的属性个数，即|SΥ|作为自变量，分析属性策略Υ的规模与所提方案的效率关系。实验结果如表4所示。

从表4可以看出，所提方案的系统建立算法与验签算法与|SΥ|无关，即与策略复杂度无关；密钥生成算法与签名算法与|SΥ|线性相关。在签名算法开销方面，|SΥ|的大小每增加5，完成一次签名所需时间增加大约0.5 ms，相当于5次sca1的时间，这与表2与表3中本文对于所提方案的签名算法开销的分析是吻合的，也间接说明了表4签名开销的实验结果是正确的。在验签开销方面，不难发现，随着签名策略Υ的复杂性增长，即|SΥ|的数量逐渐变大，签名开销仍为1.96 ms左右，而1次双线性对运算E与1次群GT上的指数运算的总时间已大约为1.6 ms(见表3)。结合以上实验数据，可知本文所提方案的验签操作确实只需要1次指数运算与1次双线性映射。这相比于其他的ABS方案具有较大的效率优势。尽管这带来的代价是用户密钥生成算法的开销会随着|SΥ|的增长而增长，但密钥生成算法毕竟只会在用户生成密钥时执行一次，且效率仍是可观的。当|SΥ| = 25(25个属性)时，执行1次密钥生成算法也仅需3.1 ms左右。除此之外，签名算法与验签算法是需要多次执行的，因此本文认为这是可以接受的。

表3 基本运算效率对比(ms)

表4 本文所提方案实验结果(ms)

除了计算开销以外，本文还给出了所提方案与现有的ABS方案的通信与存储对比，如表5所示。

结合以上对比分析与实验结果，所提方案在功能方面，支持可追踪身份以及树形访问策略；在效率方面，签名开销与验签开销相较于现有的ABS方案更低；通信与存储方面，所提方案也是与现有的ABS方案基本持平。

4 结束语

本文基于国密SM9设计了可追踪属性签名方案，本方案支持树形访问策略，同时KGC可对签名者身份进行追踪。安全性方面证明了所提方案在随机谕言机模型下具有不可伪造性，同时也可抗合谋攻击。相较于现有的可追踪属性签名方案，所提方案的追踪算法避免了复杂的运算，并且在签名开销与验签开销方面具有较大优势。验签开销方面，完成1次所提方案的验签操作仅需要1次双线性对运算与1次指数运算。实验结果表明，所提方案相较于现有的属性签名方案在签名开销与验签开销上均有较大优势，尤其是即便是复杂的属性策略，完成1次验签操作也仅需要2 ms。