后量子安全的群签名和环签名*

冯翰文, 刘建伟, 伍前红

北京航空航天大学 网络空间安全学院, 北京100191

1 引言

在确保业务功能正常运行的前提下尽可能保护用户隐私是现代密码学的主要目标之一. 但是作为实现身份认证等核心业务功能的密码学原语, 数字签名并没有将隐私性作为安全目标. 签名者的公钥是验证签名合法性的必要信息, 因此数字签名的签名者身份总是对验证者可见的. 这种显式的合法性验证方式并不符合某些场景下的用户需求. 例如, 为了避免受到干扰, 电子投票系统[1]中投票人只希望他的选票能够被验证为由合法的选民生成, 但不希望泄露他的身份; 为了避免泄露财产信息, 数字货币系统[2]中的用户只希望系统能验证他所花费的货币是系统内的合法货币, 但不希望明确指出花费的是哪个货币. 这些现实场景需要既能实现身份认证又能保护用户身份隐私的密码学工具.

群签名(group signature)[3]和环签名(ring signature)[4]等密码学原语关注了上述场景下的用户隐私保护问题. 它们允许签名者以群组的名义签名, 验证者只能确认签名由群组内的某个用户生成, 而无法获知签名者的具体身份. 其中, 群签名系统存在群管理员角色, 负责管理群成员, 并可以追踪签名者身份;环签名中的群组是完全自组织的, 不存在任何特殊机构, 签名的匿名性也无法被撤销, 提供了更高级别的隐私保护. 本文在不引起歧义的前提下将群签名和环签名统称为类群签名. 经过几十年的研究发展, 类群签名在理论上形成严格的模型和定义[5,6], 在构造上具有多个满足实际效率需求的方案[7–9], 在功能上具备了适用于不同场景的变种[10,11], 在电子现金[12]、数字货币[13]、电子投票[1]和可信计算[14]等领域发挥着关键作用.

量子计算机的出现对经典密码体系造成了体系冲击. Shor 在1994 年提出了可以有效解决离散对数问题和大整数分解问题的量子算法[15], 从理论上攻破现在所有基于离散对数和大整数分解的密码方案. 近年来量子计算机实用化的进程不断推进, 使得在现实中攻破经典密码体系趋于可能. 如何应对量子计算机的威胁, 是最近十多年来密码学界研究的热点问题, 主流解决思路是基于量子算法不能有效解决的困难问题重新构建完善的后量子公钥加密体系. 基于格上困难问题[16]、编码理论[17]、对称密码学原语[18]、同源函数[19]和多变量多项式[20]等被广泛认为抗量子安全的假设, 公钥加密方案和数字签名等基础密码原语已经具备实用化的后量子安全解决方案. 其中, 基于格的密码体系[16]由于具备代数操作简单、渐进效率高、可归约到最坏情况(worst-case) 困难问题以及支持全同态加密[21]等高级密码学原语构造的优点,受研究者广泛关注.

与数字签名和公钥加密等基础原语不同, 后量子安全的类群签名研究起步较晚, 仍处在快速发展的阶段. 在Asiacrypt 2010 上, Gordon、Katz 和Vaikuntanathan[22]设计了首个基于格上困难问题的群签名方案, 拉开了近十年来后量子安全类群签名研究的序幕. 以丰富功能、提高效率和增强安全性为目标, 大量的后量子安全的群签名[23,24]和环签名方案[25,26]被相继提出. 一方面, 基于格上困难问题的构造最受关注. 功能方面, 以Libert 等人的工作[24]为代表的一系列工作[27–32], 在格密码体系下实现了具有多种不同功能性质的类群签名方案. 效率方面, Esign 等人[25]在2019 年的突破性工作使得基于格的环签名方案满足了实用化需求, Yang 等人的工作[33]和Pino 等人的工作[34]也极大地提高了基于格的群签名方案的效率. 值得注意的是, 这些基于格的类群签名方案设计也极大地推动了基于格的零知识证明系统的研究, 对格密码学产生了更加广泛的影响. 其中部分技术也被延伸到基于编码理论的密码体系, 用于设计相应的类群签名方案[35]. 另一方面, 2016 年Giacomelli、Madsen 和Orlandi[36]基于对称密码学原语提出了高效的非交互式零知识(non-interactive zero-knowledge, NIZK) 证明系统, 丰富了后量子密码体系的工具库, 启发了基于对称密码学原语设计类群签名的新思路[18,37], 为后量子安全的实用化类群签名方案提供了新的可能.

本文结合当前领域的主要成果, 较为全面地介绍了基于格上困难问题和对称密码学原语两类假设的类群签名方案. 从技术角度对现有的后量子安全的类群签名方案进行分类总结, 归纳了现有各类构造技术的特点和局限, 理清了该领域的技术发展脉络, 总结了一些还有待解决的重要问题. 本文组织结构如下: 第2节介绍了类群签名的基本定义和设计思想; 第3 节和第4 节分别具体综述了基于格的和基于对称密码学原语的类群签名方案研究; 第5 节介绍了量子随机预言机模型, 并探讨了如何构造量子随机预言机模型下可证明安全的类群签名方案; 第6 节展望了该领域目前还有待解决的若干问题.

2 类群签名的基本概念及设计思想

2.1 群签名

群签名最早由Chaum 和van Heyst 在1991 年提出[3]. 该密码学原语允许群成员以整个群组的名义签名任意的消息, 从而使验证者可以确认该签名由群中某个成员生成, 但无法得知签证者的具体身份.

根据群成员是否可以在系统启动后动态加入或撤销, 群签名方案可以分为静态群签名[5]、动态群签名[38](仅动态加入), 可撤销群签名[39]和全动态群签名[40](动态加入和撤销) 等. 本节沿用Bellare 等人的静态群签名形式化定义[5], 介绍静态群签名这一基本模型. 动态群签名和全动态群签名的定义和模型可参考Kiayias 和Yang 的工作[38]和Bootle 等人的工作[40].

静态群签名定义. 静态群签名[5]是指所有的群成员及其身份都在启动阶段确定且不能更改的群签名方案. 静态群签名方案存在群管理员和用户两类实体, 其中群管理员负责追踪签名者的身份. 该类方案依赖一个可信机构来生成系统公开参数和群管理员的私钥, 并为所有的群成员分别生成并分发签名密钥. 一个静态群签名方案由两个多项式概率时间(polynomial probabilistic time, PPT) 的随机化算法和两个多项式时间的确定性算法定义, 分别是: 密钥生成(GKg)、签名(GSig)、签名验证(GVf)、开启(Open), 具体描述如下.

(1) (gpk,gmsk,gsk) ←GKg(1λ,1N). 群密钥生成算法是随机化算法, 以安全参数λ ∈N 和群成员数N ∈N 作为输入, 输出群公钥gpk, 群管理员私钥gmsk, 以及每一个群成员i ∈[N] 的签名密钥gsk[i] (构成向量gsk).

(2) σ ←GSig(gsk[i],M). 群签名算法是随机化算法, 以签名密钥gsk[i] 和待签名消息M 作为输入,

输出群签名σ.

(3) b ←GVf(gpk,M,σ). 群签名验证算法是确定性算法, 以群公钥gpk, 消息M 和群签名σ 作为输

入, 输出b ∈{0,1}.

(4) i or ⊥←Open(gmsk,M,σ). 开启算法是确定性算法, 以群管理员私钥gmsk, 消息M 和签名σ

作为输入, 输出签名者身份i ∈[N], 或者开启失败, 返回终止符⊥.

如果消息签名对(M,σ) 满足GVf(gpk,M,σ) = 1, σ 被称为关于群公钥gpk 的对消息M 的合法签名.

静态群签名正确性. 该性质要求诚实生成的签名永远都是合法的, 以及诚实生成的签名始终都能被Open 算法开启为签名者的身份.

静态群签名安全性. 静态群签名的经典安全模型描述了两个独立的安全性质, 即完全匿名性(fullanonymity) 和完全可追踪性(full-traceability):

• 完全匿名性: 敌手可以获得所有群成员的私钥, 可以任意地访问开启预言机(open oracle) 来获得任一签名的签名者身份. 敌手可以指定两个私钥(gsk[i0],gsk[i1]) 和消息M 进行挑战, 但对于返回的挑战签名σ ←GSig(gsk[ib],M) (该签名禁止问询开启预言机), 敌手仍然无法以不可忽略的优势判断出b 的值.

• 完全可追踪性: 敌手可以获得系统主私钥, 任意地获得群成员的私钥, 任意访问特定私钥的签名预言机, 但仍然不能生成一个新的签名使其被开启为某个未被敌手获得的私钥对应的群成员.

根据文献[41] 的结论, 完全匿名的群签名方案必须依赖公钥加密. 不依赖公钥加密可实现的最优匿名性被称为无私匿名性(selfless anonymity), 其中敌手不能获得被挑战的两个私钥. 此外, 部分群签名方案[22]的匿名性定义中, 群签名无法访问开启预言机, 这样的匿名性被称为抗选择明文攻击的匿名性(CPA-anonymity).

2.2 环签名

环签名这一概念最早由Rivest、Shamir 和Tauman[4]提出. 环签名允许用户以一个自组织的用户群体(被称为环) 的名义签名, 而不泄露签名者的确切身份. 环签名的概念与群签名接近, 都是将签名者身份隐藏到某个群体当中, 但存在显著差异. 群签名方案中存在群管理员可以撤销群签名的匿名性, 而环签名中并不存在任何中心化的机构, 用于隐藏签名者身份的群组可以是签名者自己即时选择的, 用户之间也不需要任何的协作. 因此, 环签名提供了更高的匿名性, 也更适用于密码货币等[13]去中心化的应用场景.本综述沿用Bender、Katz 和Morselli 提出的环签名形式化模型及安全定义[6].

环签名定义. 一个环签名方案由以下三个算法定义: 密钥生成(KeyGen)、签名(Sign)、验证(Verify).令公钥序列R=(pk1,··· ,pkN) 为一个环, 令R[i]=pki, 环签名的形式化定义如下:

(1) (pk,sk) ← KeyGen(1λ). 密钥生成算法以安全参数λ ∈ N 为输入, 输出用户的公钥私钥对

(pk,sk).

(2) σ ←Sign(sk,s,M,R). 签名算法以用户私钥sk、位置s、消息M 和环R 为输入, 其中(R[s],sk)是一对由密钥生成算法输出的密钥, R 中包含两个以上的公钥且两两不同. 该算法输出签名σ.

(3) b ←Verify(R,M,σ). 验证算法以环R、消息M 和签名σ 为输入, 验证σ 是否为M 在环R 下的合法签名.

环签名的正确性. 该性质要求所有诚实生成的环签名都是合法的.

环签名安全性. 环签名需要满足两个独立的安全性质, 即匿名性(anonymity) 和不可伪造性(unforgeability) 两个性质. 前者要求攻击者无法获悉签名者身份, 后者要求攻击者无法在不掌握环中任何一个私钥的情况下生成合法的签名. 根据攻击者能力的不同, 匿名性和不可伪造性有多种定义方式. 本综述介绍攻击者能力最强的定义.

• 抗密钥全泄露匿名性. 敌手可以用任意方式(非诚实运行密钥生成算法) 生成公钥, 并获得诚实用户在包含非诚实生成公钥的环下的签名; 敌手可以获得诚实用户的密钥生成过程中使用的随机数(这是比获得私钥更强的能力); 敌手可以指定任意两个诚实生成的公钥(pk0,pk1) 作为挑战公钥,并指定签名消息M 和环R = R′∪{pk0,pk1}; 对于诚实生成的签名σ ←Sign(skb,sb,M,R), 敌手仍然无法以不可忽略的优势判断b 的值.

• 抗内部腐化攻击的不可伪造性. 对于一个诚实生成的公钥集合, 敌手可以任意访问他们对应的签名预言机, 可以任意获得部分公钥对应的私钥; 但对于由没有被获得私钥的公钥构成的子环, 敌手无法以不可忽略的概率伪造签名.

环签名的变种. 环签名较常见的变种包括可链接环签名[10](linkbale ring signature). 标准的可链接性引入标签这一概念来刻画当前使用环签名的具体事项(比如一次投票), 要求由同一个私钥产生的两个同一标签下的环签名可以被公开链接. 如果移除标签的概念, 要求只要两个环签名由同一个私钥产生即可链接, 该性质被称为一次可链接性. 此外, 如果同一私钥产生的两个签名不仅可以被链接, 还会直接暴露签名者的身份, 这样的环签名方案被称为可追踪环签名[11](traceable ring signature).

2.3 后量子安全的类群签名的设计方法概述

群签名和环签名为用户提供了相似的功能: 允许用户以自己所在群组的名义对消息签名, 签名验证者可以确认签名由群成员产生, 但无法获知签名者具体身份. 二者在组织结构上存在差异: 群签名的群组由群管理员维护, 且存在特殊机构可以追踪任一群签名的签名者身份; 环签名系统并不存在中心化机构, 签名时所用的群组由签名者自行定义.

组织结构的不同不仅导致了二者应用场景的差异, 也使得它们的设计方法有所不同. 群签名和环签名都可保证非群组成员无法以该群组的名义签名, 因此每一个群签名或者环签名都可以视作是对群成员关系的证明. 环签名的群组要求具备自组织性, 通常由公钥集合的形式来定义, 签名者实质上需要证明持有其中某个公钥的私钥. 群签名由于引入了群管理员这一特殊机构, 支持更加灵活多样的群组定义方式. 首先, 使用公钥集合定义群组的方法同样适用于有管理员的群组, 其公钥集合由管理员定义并公开; 群组也可以通过管理员持有的秘密信息定义, 例如管理员使用自己的私钥对为所有群成员生成证书, 凡是持有合法证书的用户都被视为群成员. 因此, 从群成员关系证明的角度来看, 群签名可能比环签名更容易构造. 但是, 群签名需要额外支持特殊机构对签名者身份的追踪, 给方案设计增加了难度. 技术上, 几乎所有的群签名[5,38,42]构造都遵循Bellare、Micciancio 和Warinschi[5]提出的“加密后证明”(encrypt-then-prove)范式. 为了签名一个消息, 群成员首先使用追踪机构的公钥加密自己持有的由群管理员提供的证书, 再证明该密文确实是合法生成的. 验证签名的过程即验证证明的过程, 而追踪机构可以用私钥解密密文获得签名者身份. 因此, 群签名的构造除了要证明群成员关系, 需要额外证明密文是正确生成的. 后者通常制约群签名效率提高的原因.

类群签名设计方法在经典密码体制下已有较充分的讨论. 核心密码组件概括如图1所示.

图1 类群签名的构造组件Figure 1 Building blocks of group signatures and ring signatures

(自组织的) 群成员关系定义和证明. 群成员关系定义是任何类群设计的出发点. 群成员关系的定义方法决定了方案的用户密钥形式, 也关系到可以使用何种证明方法来证明此种群成员关系. 在经典密码体制下, 自组织的群成员关系有以下两种常见定义:

• 由公钥集合直接定义. 群组直接表示为用户的公钥集合: G = {pk1,··· ,pkn}. 集合G 对应的关系可以表示为: 存在sk 使得∨i∈[n]R(pki,sk)=1, 其中R(pk,sk)=1 代表sk 是pk 对应的私钥.Cramer、Damgård 和Schoenmakers[43]提出的证明系统构造框架适用于此种群成员关系定义方法. 这种群组定义方法比较直观, 其对应的证明方法通用性强, 可以通过单个公钥对应的身份认证协议转换得到. 其缺点是产生的证明大小与集合大小线性相关.

• 使用累加器(accumulator)[44]定义. 累加器可视为对集合的承诺承诺值u (称为累加值) 与集合大小无关. 集合中每一个元素e 都对应一个短证据w, w 的大小与集合大小成次线性关系, 且任何掌握w,e 和u 的个体都可以高效验证e 是被承诺集合中的元素. 令{pk1,··· ,pkn} 为构成群组的公钥集合, 令u 是该集合对应的累加值. 此时群组可直接用u 表示, 对应的群成员关系为: 存在pk, sk 和w, 使得R(pk,sk)=1 且w 是pk 在u 中的证据. Merkle 树[45]是一种典型的累加器.

对于群签名系统中有管理员管理的群组, 除了使用自组织的群定义方式外, 还可以基于标准模型下的数字签名方案定义. 具体的, 令(vk,sk) 为群管理员持有的签名公私钥对, 群组由所有被管理员签名的元素构成. 群成员关系证明即为证明持有vk 下合法的签名消息对.

密文正确性证明. 公钥加密和密文证明是群签名构造的重要组件, 用于实现签名者的身份追踪功能.在群签名的全匿名性定义中, 攻击者可以任意开启签名者的身份. 为了实现这一安全性, 公钥加密方案需要对应满足选择密文攻击(IND-CCA) 的安全性. 密文证明是指证明密文是在追踪机构的公钥下合法生成的, 且明文满足特定的关系(群签名中常见的是满足群成员关系). 需要指出的是, 基于对称密码原语的群签名方案[18]并不使用公钥加密作为构造组件, 而是采用了文献[41] 提出的基于伪随机函数的构造方法来实现可追踪性, 相应的代价是该方案无法达到完全匿名性.

证明的隐私性要求. 类群签名的主要安全目标是保护用户的隐私, 因此构造中使用的群成员关系证明和密文正确性证明方法应当保证验证者无法从证明中获得签名者的任何身份信息. 现有构造通常使用非交互式零知识(non-interactive zero-knowledge, NIZK) 证明系统[46]来实现隐私保护的目标. 具体的,一个适用于NP 语言L 的NIZK 证明系统由三个算法刻画: 1) 启动算法(Setup), 用于生成共享字符串(common reference string, CRS), 或者确定一个随机预言机; 2) 证明算法(Prove), 以x 的证据w 为输入, 生成证明π 来表明x ∈L; 3) 验证算法(Verify), 用于公开验证证明π 是否合法. NIZK 证明系统需要满足三个独立的安全性质: 完备性(completeness): 诚实生成的证明始终能通过验证; 可靠性(soudness):对于错误的论断x /∈L, 任何人不能产生合法的证明π 表明x ∈L; 零知识性(zero-knowledge): 任何人无法从证明中获得除了x ∈L 以外的任何信息.

此外, 也有部分方案采用非交互式证据不可区分[47](non-interactive witness-indistinguishable) 的证明系统. 对于一个待证明的论断x, 令w0和w1是该论断不同的证据, 证据不可区分性保证验证者无法区分由w0和w1产生的证据. 非交互式证据不可区分证明系统所依赖的假设和模型往往弱于零知识证明系统, 因此通常被用于实现弱假设下的理论构造.

后量子安全的类群签名方案的研究本质上是在解决上述密码组件的后量子安全构造问题. 由于数字签名、公钥加密以及构造Merkle 树所需的Hash 函数都已具备后量子安全的构造, 因此后量子安全类群签名方案要解决的核心问题是这些群成员关系定义对应的具有隐私保护性质的证明方法. 本文在第3 节和第4 节将围绕后量子安全的群成员关系证明方法和密文证明方法, 综述现有方案.

3 基于格的类群签名方案

本节按照安全证明模型(标准模型和随机预言机模型)分别综述格基类群签名的发展历程及研究现状.标准模型下的构造主要是回答标准模型下格基类群签名方案是否存在这一理论问题. 随机预言机模型下的构造主要是考虑方案的功能性和效率, 目前大部分格基类群签名方案在随机预言机模型下可证明安全.随机预言机模型下的方案大多以基于格的NIZK 证明系统作为核心组件, 使用何种零知识证明系统在很大程度上影响了签名方案的构造方法和具体效率.

现有的格基NIZK 证明系统可以分为具备标准可靠性的NIZK (NIZK with standard soundness, ss-NIZK) 证明系统和具备弱可靠性的NIZK (NIZK with weak soundness, ws-NIZK) 证明系统, 它们适用范围和具体效率方面存在较大的差异. 具体的, NIZK 证明系统的可靠性往往通过知识提取器(extractor)定义. 标准的可靠性是指,若证明者可以产生关于x ∈L 的合法证明π,知识提取器从证明者处获得x ∈L的证据w. 弱可靠性是指, 知识提取器只能从证明者处获得某个与x 相关的论断x′的证据w′.

为了理清技术发展脉络, 本节进一步将随机预言机模型下的格基类群签名方案分为基于ws-NIZK 证明系统的方案和基于ss-NIZK 证明系统的方案, 分类进行综述. 此外本文也综述了随机预言机模型下唯一一个不基于NIZK 的格基环签名方案. 本节的所涉及的格密码背景知识可参考王和刘的综述[48].

3.1 标准模型下的后量子安全类群签名方案

类群签名的构造通常依赖于NIZK 证明系统或两轮证据不可区分证明系统(ZAP)[47]. 然而在标准模型, 包括共享字符串模型(common reference string model, CRS) 和朴素模型(plain model) 中, 高效NIZK 证明系统和ZAP 的已知构造方式非常有限, 主要为Groth 和Sahai 利用双线性映射构造的证明系统[49]. Groth 和Sahai 的证明系统也是现有的在标准模型下可证安全的群签名方案和环签名方案的构造基础. 如何基于抗量子的困难问题假设构造类似于Groth 和Sahai 的NIZK 证明系统目前是一个公开难题.

理论上, 可证明所有NP 语言的通用NIZK 证明系统或者ZAP 可以用于证明格密码学和对称密码学相关的语言. CRS 模型下的通用NIZK 证明系统构造是一个非常经典的问题, 早在FOCS 1990 上Feige,Lapidot 和Shamir 就已经提出了基于单向陷门置换(one-way trapdoor permutation) 的通用NIZK 证明系统[46]. 然而, 尽管单向陷门置换是一个简单且优美的密码学基本原语, 且可以基于大整数分解假设构造, 我们对它的其他构造方式尤其是基于抗量子假设的构造方式却知之甚少, 这也使得后量子安全的通用NIZK 证明协议是长期以来的公开难题. 可喜的是, 近年来对Fiat-Shamir 转换在标准模型下的构造方法研究取得了突破性进展. CRYPTO 2019 上, Piekert 和Shehian 基于LWE 假设构造了具有Correlation Intractability (CI) 性质的Hash 函数, 该Hash 函数可以用于替换Fiat-Shamir 转换中的随机预言机, 从而得到CRS 模型下的通用NIZK 证明系统[50]; Eurocrypt 2020 上, Badrinarayanan 等人同样利用具有CI 性质的Hash 函数, 构造了基于LWE 假设的ZAP[51]. 根据群签名的通用构造[5]和环签名的通用构造[6], 上述抗量子的证明系统也从理论上解决了标准模型下后量子安全类群签名构造问题. 在实际效率方面, 基于LWE 的具有CI 性质的Hash 函数构造复杂, 依赖于全同态加密[21]等高级密码学原语, 目前距离实用化还存在非常巨大的差距.

本节所综述的标准模型下的环签名和群签名方案均在上述通用证明系统之前提出, 在当时解决了标准模型下后量子安全的类群签名的存在性问题.

3.1.1 标准模型下的环签名

Brakerski 和Kalai[52]提出了一种高效的通用框架来构造标准模型下的环签名方案. 具体的, 该文献定义了环陷门(ring trapdoor) 函数这一概念, 并展示了如何利用环陷门来构造环签名. 其中, 环陷门函数是对普通陷门函数的扩展, 它不仅要求给定f 和y 找到x 使得f(x) = y 是困难的, 也要求对于给定的f1,··· ,ft,y 来找到x1,··· ,xt使得fi(xi) = y 是困难的; 但如果具有任何一个fi对应的陷门, 则可以有效计算出所有满足条件的x1,··· ,xt. 运用环陷门函数构造环签名方案的思路也比较直观, 函数本身作为签名的公钥, 函数对应的陷门作为签名的私钥, 求出的逆x1,··· ,xt作为环f1,··· ,ft下的签名.

对于环陷门函数这一新定义, 该文献基于格上的最小整数解(short integer solution, SIS) 问题[53]和双线性对上的计算性Diffie-Hellman 问题分别构造了具体的环陷门函数. 使用基于SIS 问题的环陷门函数实例化通用框架可以得到在标准模型下可证安全的格基环签名方案. 由于该方案中, 签名由所有的逆组成, 因此签名的大小和环的规模线性相关. 同时, 基于格的环陷门函数依赖格的陷门函数[54], 该陷门函数需要较大的格维度, 这也导致签名的实际大小过大[55], 不满足实际应用需要.

3.1.2 标准模型下的群签名

Katsumata 和Yamada[56]为了构造在标准模型下可证明安全的格基群签名方案, 他们绕过了传统的群签名设计框架, 提出了不基于非交互零知识证明的构造方法. 他们构造的核心思想是利用属性基签名[57]来替代群签名构造中非交互零知识证明的功能. 属性基签名有基于格的构造[58], 且在标准模型下可证明安全. 属性基签名方案中, 由密钥中心向用户分发某一属性x 对应的私钥skx, 而持有该私钥的用户可以生成满足C(x) = 1 的属性策略C 下合法的签名. 与非交互零知识证明对应, 在属性策略C 下的签名可以视为对满足C(x)=1 的x 的知识证明. 不同的是, 持有属性x 的用户必须事先从密钥中心获得私钥skx才能完成进行签名. 在群签名中, 签名者需要证明密文的正确性, 而加密所用的随机数作为证据的一部分是在签名过程中产生的, 无法被密钥中心事先得知并生成对应的私钥, 因此直接使用属性基签名无法得到安全的群签名方案. Katsumata 和Yamada 借鉴了Kim 和Wu[59]构造预处理非交互零知识证明协议的思想, 使用对称加密方案对凭据进行加密, 并将证明加密正确性转换为证明解密的正确性, 通过解密的确定性移除加密的不确定性, 使得群管理员可以一次性生成用户所需的签名私钥, 从而解决了该问题. 由于用户同样掌握解密密钥, 可以确定某一签名是否由自己的私钥产生, 因此该方案的匿名性为无私匿名性而非完全匿名性. 该方案中, 密钥中心需要掌握用户所有的秘密信息, 并在启动阶段生成对应的私钥, 因此该方案属于静态群签名方案. 如何利用属性基签名来构造动态群签名方案尚缺乏清晰的技术途径.

3.2 基于ws-NIZK 证明系统的类群签名方案

基于ws-NIZK 证明系统的格基类群签名方案可以分为两个阶段. 早期方案使用的ws-NIZK 证明系统为MV03 证明系统[60]和Fiat-Shamir-with-Abort(FSwA) 证明系统[55]. 这两个证明系统最早被用于证明GapCVP 或非齐次最小整数解问题(inhomogeneous small integer solution, ISIS) 等格上困难问题,应用到类群签名的构造时需要配合额外的技术, 效率较低. 2018 年后的部分格基类群签名方案发展了新的ws-NIZK 证明系统, 包括one-out-of-many 的证明系统ESS+19[26]和ESL+19[25](适用于自组织的群成员关系证明), 以及证明自同构不变点的证明系统PLS18[34](适用于有管理员的群成员关系证明). 这些新型证明系统极大提升了格基类群签名的实际效率, 达到或接近了实用化需求.

通用性方面, 基于格的ws-NIZK 证明系统仅适用于非常有限的语言. 弱可靠性在密文正确性证明和数字签名持有证明等常见应用中缺乏明确的意义. 基于ws-NIZK 的群签名方案中, 密文正确性证明需要额外的技术才能完成. 动态群签名所需要的数字签名持有证明难以通过ws-NIZK 证明系统实现, 导致动态群签名难以通过ws-NIZK 证明系统构造. 实际效率方面, 部分良好设计的ws-NIZK 证明系统非常高效, 可以满足特定应用下的实用化需求.

3.2.1 基于MV03 和FSwA 的类群签名方案

MV03 证明系统是由Micciancio 和Vadhan 于CRYPTO 2003 提出的零知识证明系统[60], 可以证明GapCVP 等格上最坏情况的困难问题. FSwA 证明系统由Lyubashevsky 于Asiacrypt 2009[61]和Eurocrypt 2012[55]提出并发展, 其设计思想与基于离散对数的Schnorr 协议[62]类似, 它允许证明者证明自己持有ISIS 问题的证据, 即持有某个短向量x 满足A·x = y(modq)∧//x//≤β, 其中A 和y 为公开的矩阵或向量, β 是公开的数值. MV03 证明系统的单次执行允许恶意证明者以1/2 的概率欺骗验证者(soundness error 等于1/2), 因此需要至少λ 次重复执行协议才能保证恶意证明者成功欺骗的概率是可忽略的(λ 为安全参数), 效率较低. FSwA 证明系统单次执行即可保证soundness error 为可忽略的, 效率明显优于MV03. 事实上, MV03 证明系统仅被使用于非常早期的群签名方案.

据文献[63] 分析, MV03 和FSwA 证明系统只能满足弱可靠性, 即证明者对自己持有短向量x 满足ISIS 的实例(A,y,β) 的证明, 实际上只能确保证明者知道//x′//≤β′满足A·x′= cy, 其中β′> β,c > 1. FSwA 的这一缺点也进一步限制了它在证明密文正确性等需要精确的可靠性场景下的使用. 受限于MV03 和FSwA 可证明的语言类型, 相应的环签名方案只能做到签名大小与环的规模线性相关, 而群签名需要借助格的特殊陷门函数才能完成密文正确性的证明.

基于FSwA 证明系统的环签名方案. 早期的格基环签名方案[64]可以视作是经典的CDS 机制[43]在格密码中的应用. CDS 机制是指Cramer、Damgård 和Schoenmakers 于CRYPTO 1994 上提出的一种按照OR 关系组合Sigma 协议机制. 具体的, 若对于某个NP 语言L, 存在满足特定条件的协议Σ 可以证明x ∈L, 那么经由CDS 机制可以得到一个新的协议ΣOR来证明x1∈L ∨···∨xN∈L. 如果Σ协议是身份认证协议, 则ΣOR可经过Fiat-Shamir 转换[65]得到环签名方案. 使用CDS 机制, Melchor等人[64]将基于FSwA 的格基身份认证协议[55]为环签名方案. 该环签名方案和所有经由CDS 机制构造的环签名方案一样, 签名大小和环的规模线性相关.

类似的构造方法也被应用与设计格基可链接环签名方案. Baum、Lin 和Oechsner 的方案[66]与Torres 等人的方案[67]非常类似. 他们的方案可以视作是基于离散对数的可链接环签名方案[10]在格上的迁移. 他们首先设计FSwA 协议证明用于实现链接性的向量是用签名者的私钥诚实生成的, 再利用CDS机制隐藏签名者的公钥, 经由Fiat-Shamir 转换后形成可链接环签名. 这两个方案签名大小和环的规模成线性关系, 主要应用考虑的是匿名数字货币等环规模较小的场景. 需要指出的是, 这两个方案所实现的可链接性为一次可链接性, 即任意两个由同一私钥产生的签名可以被公开链接. 一次可链接性与标准的基于标签(Tag-based) 的可链接性[68]有严格的区别. 从应用角度, 一次可链接性足够匿名数字货币的使用需求. 从技术角度, 实现基于标签的可链接性需要引入伪随机函数作为组件, 并用零知识证明系统来保证伪随机函数的正确执行[68]. 这样的证明任务难以通过FSwA 完成.

基于FSwA 和MV03 证明系统的群签名方案. 由于MV03 和FSwA 难以直接证明密文的正确性, 早期的格基群签名构造不得不依赖特殊的代数结构来降低需要证明的关系的复杂度. 最早的基于格的群签名方案由Gordon、Katz 和Vaikuntanathan[22]提出. 在该方案中, 他们提出了带陷门的正交格(orthogonal lattice with its trapdoor) 这一概念及其采样方法. 给定矩阵B, 可以生成矩阵(A,T) 使得A·B = 0(modq) 及T 是A 的陷门[64]. A1,··· ,AN作为N 个用户的分别的公钥. 如果编号为j 的用户需要对消息M 签名, 则可以利用对应的陷门Tj可以生成一个短向量ej满足Aj·ej=H(M), 再求解线性方程组生成ei,i ̸= j 满足Ai·ei= H(M). 然后加密每个ei,i ∈[N] 得到ci= Bi·si+ei. 该加密方案的安全性可以归约到格上的容错学习问题(learning with errors, LWE)[69]. 由于Bi和Ai是正交矩阵, 因此验证者可以很轻易的验证Ai·ci=0+Ai·ei=H(M). 唯一需要证明的是至少有一ci对应的ei是一个短向量. 这样的证明系统可以结合MV03 证明系统, CDS 机制, 以及Fiat-Shamir 转换[65]来实现. 安全性上, Gordon 方案提供的匿名性为抗选择明文攻击的匿名性, 即攻击者不具备获得任意指定签名的签名者身份的能力. 效率上, Gordon 方案中签名的大小和群成员个数线性相关, 并且由于使用了特殊的代数结构导致系统参数巨大, 实际效率也无法应用于真实场景. Camenisch、Neven 和Rückert 对此方案进行了改进[70], 实现了具备完全匿名性的格基群签名方案, 且可以保护诚实的用户不被管理员恶意指控,但是构造上仍然依赖于正交格陷门和MV02 协议, 效率没有明显提升.

第一个基于格的对数级的群签名方案由Laguilaumie 等人[23]提出. 该方案将用户的身份编码为ℓ比特的字符串id = id[1]···id[ℓ] ∈{0,1}ℓ, 并使用Boyen[71]提出的格基签名方案来为用户生成证书. 在Boyen[71]的签名方案中, 签名是一个陷门矩阵而非短向量, 获得签名的用户可以利用这个签名来生成自己的临时凭证x. 对消息M 进行签名时, 用户需要对所有的j ∈[ℓ] 逐项加密x·id[j], 再证明密文是对x 的加密(对应id[j] 为1) 或者0 (对应id[j] = 0) 的加密. 因为ℓ 比特的身份编码最多有2ℓ个, 因此群成员最多有2ℓ个. 签名的大小与群成员个数成对数关系. 然而, 该方案在证明密文属性的时候仍然依赖于Gordon 等人[22]提出的带陷门的正交格, 因此产生的群签名的实际大小仍然非常巨大. Laguilaumie 等人在随后的工作中提出了支持了验证者本地撤销的格基群签名方案[27], 但此方案的效率相比不支持本地撤销的方案[23]没有提升. Nguyen、Zhang 和Zhang[72]利用Agrawal 等人在基于格的身份基加密[73]方案中提出的身份编码技术, 来编码群签名中的用户身份, 并基于FSwA 证明系统来完成对方案中密文正确性的证明. 由于使用了更紧致的身份编码, Nguyen 等人的方案较Laguilaumie 等人的方案[23]有所提升,但是仍然依赖Gordon 等人[22]提出的陷门函数. 根据文献[74] 的测试, 在群成员总数为210时, Nguyen等人的方案的签名大小为500 MB, 私钥大小为90 GB. 上述群签名方案用户的密钥均是在系统启动阶段由群管理员生成, 用户无法动态加入, 因此上述方案为静态群签名方案.

3.2.2 PLS18 的群签名方案

在CCS 2018 上, Pino、Lyubashevsky 和Seiler[34]充分利用了环的代数结构来设计群签名方案. 对于分圆环Rq= Z/(Xd+1), 存在多个元素可以在对应分圆数域的Galois 自同构映射下保持不变. Pino等人针对这种自同构不变性, 设计了一种高效格基NIZK 证明系统, 证明某个承诺值属于自同构下的不变点. 将所有的不变点视作群元素, 该零知识证明协议可以用于证明群成员关系. 技术上, 该证明系统与FSwA 证明系统类似, 单次执行即可实现可忽略的soundness error, 但也仅满足弱可靠性. 为了证明密文是正确生成的, Pino 等人使用了Lyubashevsky 和Neven 在Eurocrypt 2017 上提出的可验证加密技术[75]. 结合可验证加密与新的群成员关系证明系统, Pino 等人提出了基于模SIS 和模LWE 问题[76]的群签名方案. 该方案是目前最高效的格基群签名方案, 签名大小仅为580KB 左右, 所有操作都可以在0.5秒以内完成. 但由于环中的不变点是在系统启动阶段就已经确定的, 如何利用该证明系统来设计动态群签名方案和环签名方案尚不清晰.

3.2.3 ESS+19 和ESL+19 的环签名方案

经典密码体制下Groth 和Kohlweiss[8]设计基于离散对数困难问题设计了签名大小与环的规模成对数关系的环签名方案. 该环签名方案的核心构造是一种新的one-out-of-many 的零知识证明协议: 证明N 个承诺{ci}i∈[N]的某个承诺值的消息为0. FSwA 证明系统与基于离散对数的Schnorr 协议的相似性揭示了将更多的基于离散对数的协议迁移到格基协议的可能, 也启发研究人员思考如何利用Groth 和Kohlweiss 的设计方法来构造高效格基环签名. 在ACNS 2019 上, Esgin 等人[26]等人解决了将Groth和Kohlweiss[8]设计思想迁移到格上的若干问题, 设计了基于模格上[76]的SIS 问题的one-out-of-many协议, 并构造了具有对数级签名大小的环签名方案ESS+19. 该one-out-of-many 协议的soundness error为1/poly, 需要多次重复执行协议才能实现可忽略的soundness error. 在CRYPTO 2019 上, Esgin 等人[25]解决了该问题, 实现了单次执行即可保证可忽略的soundness error. 他们将该证明技术提炼为适用于非线性多项式关系的零知识证明技术, 并发展了基于环中国剩余定理的批处理技术, 进一步降低此类零知识证明的通信复杂度, 提高效率. Esgin 等人[26]也利用这一新型技术对他们之前提出的环签名方案[26]进行了重构, 得到了基于模格上困难问题的环签名方案ESL+19. 对210规模的环, 该方案的签名大小仅为100KB 左右, 是目前适用于大规模环的效率最高的后量子安全环签名方案.

3.3 基于ss-NIZK 证明系统的类群签名方案

现有基于格的ss-NIZK 证明系统包括Stern 类协议[77]和YAZ+19 证明系统[33]. Stern 类协议和YAZ+19 证明系统的通用性强, 可以证明格密码学中常见的一大类语言, 可以构造类群签名的各种功能变种. 但Stern 类协议单次执行的soundness error 为2/3, 需要多次重复执行才能实现可忽略的soundness error, 根本上限制了基于Stern 类协议的类群签名的效率. YAZ+19 可以视作Stern 类协议的改进版本,单次执行的soundness erro 为多项式的逆, 需要重复执行的次数显著降低. 二者都无法通过单次执行实现可忽略的soundness error, 在特定应用上效率明显低于某些ws-NIZK 证明系统.

3.3.1 基于Stern 类协议的类群签名方案

Stern 类协议最早由Stern 提出并用于设计基于编码理论的身份认证协议[77], 而后被Kawachi、Tanaka 和Xagawa 引入到格密码学中用于构造基于格的身份认证协议[78]. Ling 等人[63]改进了Kawachi 等人的工作, 使得Stern 类协议可以“精确地” 证明ISIS 问题(与FSwA 不同). 此后, Stern 类协议被广泛地用于设计基于格的类群签名方案,Stern 类协议的设计技巧也在应用中不断发展. 目前Stern类协议可以证明符合如下形式的NP 关系[74]: RS:= {(A ∈Zn×dq,v ∈Znq,V ⊂{−1,0,1}d);x : A·x =v mod q,x ∈V}. 使用Libert、Ling、Nguyen 和Wang 等人提出并发展的若干技巧[24,30,74], 格密码学中常见的密文结构关系和签名消息对关系等都可以转换为上述形式, 从而可以使用Stern 来协议来证明此关系. Stern 类协议的发展丰富了格密码学工具库, 使得大量此前不知道如何基于格构造的密码学原语第一次有了基于格的具体构造.

需要指出的是, 尽管Stern 类协议功能强大, 基于Stern 协议的类群签名方案的效率距离实际应用仍然有较大距离. 这是由于Stern 类协议单次执行的soundness error 为2/3, 为了使soudness error 下降到可忽略为一个可忽略的值如2−128, 需要重复执行Stern 协议200 次以上. Stern 类协议的这一特性是基于此类协议的签名方案无法进一步提高效率的主要原因.

基于Stern 类协议的环签名方案. 在Eurocrypt 2016 上, Libert 等人基于Stern 类协议设计了签名大小与环规模成对数关系的环签名方案[74], 解决了格基紧致环签名构造这一公开难题. 在经典密码体制下, 紧致的环签名方案通常需要依赖累加器这种特殊结构. 累加器可以视作是对集合的承诺方案, 且具备紧致的成员关系证明方式. 已知的累加器分为三类, 包括基于Strong RSA 假设的累加器[79], 基于双线性对的累加器[80], 以及基于Merkle 树的累加器[45]. Libert 等人[74]使用基于SIS 困难问题的[53]杂凑函数构建了墨克树(Merkle tree)[45]作为基于格的的累加器方案, 再针对该累加器设计了Stern 类型[77]的零知识证明协议. 对于墨克树中的叶子节点, 它到根节点的路径可以作为该叶子节点属于该墨克树的证据,而该证据的大小和叶子节点的总数成对数关系. 这也是Libert 等人的方案可以实现对数级签名大小的根本原因.

Stern 类协议作为核心组件被用于设计一些环签名的变种方案. Yang 等人[29]在Libert 等人[74]提出的格基环签名方案基础上设计了基于格的可链接环签名方案. 在CT-RSA 2020 上, 笔者[32]提出了可追踪环签名的通用设计框架, 并基于Stern 类协议构造了格基可追踪环签名方案.

基于Stern 类协议的群签名方案. Ling、Nguyen 和Wang[81]发展了Stern 协议[63], 使得群签名方案中的密文正确性可以通过Stern 协议证明, 从而摆脱了对Gordon 等人[22]提出正交格基陷门的依赖,而仅使用标准的格陷门函数[54]. 相比于之前基于正交格基陷门的群签名方案, 该方案的安全假设更弱, 并且可以很容易地构造基于环SIS 和环LWE 的版本[82]. 基于环LWE 和环SIS 的方案通常比基于标准LWE 和标准SIS 的方案更加高效, 但此前的群签名方案所使用的正交格陷门缺乏基于环的构造方法.

Libert 等人[74]采用拓展环签名的方式来构造静态群签名方案. 他们所拓展的环签名方案也即上文介绍的基于Merkle 树累加器的环签名方案. 他们的群签名方案的群公钥可以看做包含所有群成员公钥的一个固定的环. 在对消息进行签名时, 签名者需要加密自己的公钥, 并证明密文是对环中某个公钥的加密.该方案的构造方式移除了对格上陷门函数的需求, 可以更灵活的设置系统参数. 在此之前的格基群签名方案都是用了格上的陷门函数来为群中的用户生成凭证, 受限于陷门所需的系统参数选择, 签名的实际尺寸都过于巨大[55]. 同时, 由于对应环签名方案的签名大小和环规模成对数关系, 该方案的签名尺寸也是对数级的. 根据Libert 等人自己的测试结果, 该方案在群成员为210时, 签名大小为60 MB 左右, 较之前GB级的签名大小有显著提升.

利用Stern 协议, Libert 等人[24]在Asiacrypt 2016 上构造了第一个基于格的动态群签名方案. 该构造的关键是设计零知识证明协议证明密文对应的明文是合法的格基数字签名[83]. 在ACNS 2017 上,Libert 等人[30]拓展了文献[74] 提出的累加器方案, 使其支持加入和撤销等动态操作, 从而得到了第一个基于格的全动态群签名方案. 此工作后, 大量的具有不同安全特性或者功能特性的格基群签名方案被提出, 包括具有前向安全性的群签名方案[84]、支持对开启机构行为审计的群签名方案[85]、支持层次结构的群签名方案[86]和多群签名方案[87]. Ling 等人[31]为Ducas 和Micciancio[88]的数字签名方案设计零知识证明协议, 支持证明持有该方案合法的消息签名对, 从而构造出了第一个基于格的常数级群签名方案.这也是目前渐进效率最优的格基群签名方案.

3.3.2 基于YAZ+19 证明系统的类群签名方案

在CRYPTO 2019 上, Yang 等人[33]提出了一种新的格基零知识证明系统YAZ+19. 功能方面, 该证明系统与Stern 类协议接近, 可以证明格密码学中常见的一大类NP 语言, 并具备标准的可靠性. 效率方面, 该证明系统单轮执行的soundness error 仅为1/poly, poly 代表安全参数的多项式. 该数值小于Stern 类协议的soundness error 2/3, 将soundness error 降低到可忽略的大小所需要的重复次数也随之少于同等安全参数下Stern 类协议所需重复次数, 因此该证明系统效率较Stern 类协议有显著提升.

YAZ+19 证明系统设计上结合了FSwA 和Stern 类协议的优点. 对于需要证明的ISIS 问题(A,y;x),该证明系统首先采用类似于FSwA 的方式, “宽松地” 证明存在向量x′满足A·x′= cy mod q, 再采用类似于Stern 类协议的方式“精确地” 证明存在向量x ∈{−1,0,1}n满足x′= cx. 结合两者的优点,YAZ+19 实现了精确证明和更小的soundness error.

Yang 等人[33]使用该证明系统对基于Stern 类协议的类群签名方案[74]进行了全面的升级, 得到的类群签名方案是目前基于标准格效率最优的方案. 值得一提的是, Bootle、Lyubashevsky 和Seiler[89]也在CRYPTO 2019 上发表了他们关于新型格基零知识证明系统的工作. 他们的证明系统设计方法和效率与YAZ+19 接近, 但他们并没有将该证明系统应用到类群签名的设计中, 在此不再展开介绍.

3.4 基于变色龙Hash 的环签名方案

在ACNS 2019 上, Lu、Au 和Zhang 提出了适用于小规模环的实用格基环签名方案Raptor[90].与第三代的其他工作不同, Raptor 取得的效率提升并非是来源于新型零知识证明协议, 而是来源于环签名方案的新设计框架. Lu 等人深入分析了Rivest、Shamir 和Tauman 提出第一个环签名通用构造框架RST01[4], 提炼出了RST01 框架实际上所需要的密码组件, 即增强变色龙杂凑函数(chameleon hash plus, CH+). 他们基于标准格和NTRU 格分别构造了CH+, 并在此基础上构造了格基环签名方案. 与RST01 框架的其他环签名一样, Lu 等人的方案中签名大小与环的规模线性相关, 因此更适用于小规模环的情况. 他们的实现测试结果说明该方案对于规模较小的环(例如由5 个公钥构成的环) 效率可以满足实用需求(对应签名大小为6.3 KB).

Lu 等人也提出了一种新的一次可链接环签名设计方法. 他们的方案区别于Franklin 和Zhang[68]提出的构造方法, 通过在环签名中附加一次性签名的方法来实现同一私钥产生的不同签名的可链接性.Wang、Chen 和Ma[91]总结并推广了此种可链接环签名设计技巧.

3.5 具体效率

本文结合安全假设、具体功能和应用场景等指标, 在表1 中总结了其中最高效的格基类群签名方案.

表1 格基类群签名方案具体效率Table 1 Performance of group signatures and ring signatures from lattices

4 基于对称密码原语的类群签名方案

基于对称密码原语构造随机预言机模型下的类群签名并非理论上的难题. 在FOCS 1990 上, Feige等人基于单向函数构造了Sigma 协议可以证明哈密顿回路问题[46]. 由于哈密顿回路问题是NPC 问题,所有NP 语言的实例都可以转换为该问题的一个实例, 因此该Sigma 协议可以证明任意的NP 语言. 将Fiat-Shamir 转换应用于该Sigma 协议可以得到随机预言机模型下的通用非交互零知识证明系统, 其安全性仅依赖于单向函数的困难性. 基于对称密码学原语的环签名方案可以通过结合基于单向函数的承诺方案和该通用NIZK 证明系统直接得到, 具体的构造方法可以视作是对文献[92] 提出通用构造的实例化.基于对称密码学原语的群签名方案略显复杂, 不能通过实例化Bellare 等人的通用框架得到[5]. 根据文献[41] 的结论, 完全匿名的群签名方案必须依赖公钥加密, 而基于对称密码学原语设计的群签名方案所能实现的最佳匿名性为无私匿名性(selfless anonymity), 严格弱于标准的全匿名性定义. 二者的区别在于完全匿名性允许攻击者获取全体用户的私钥, 而无私匿名性要求诚实用户的私钥始终保密.

近年来, 基于对称密码学原语的高效零知识证明系统研究取得了突破性进展[36,93], 促进了实用化的基于对称密码原语的类群签名研究. Ishai 等人在此研究方向做出了开创新贡献[93]. 他们注意到多方计算协议(multi party computation, MPC) 的安全目标和零知识证明系统的安全目标存在高度相似性, 提出了基于承诺方案的通用转换框架, 可以将符合一定性质的MPC 协议转换为零知识证明系统. 在他们提出的通用构造中, 证明者首先将需要证明的关系R(x,w) 作为MPC 协议要计算的函数, 将证据w 进行秘密分享, 本地执行MPC 协议各方的所有步骤, 再对每一方的执行流程分别承诺并将承诺值发送给验证者; 验证者随机选取部分承诺要求证明者开启; 证明者将指定的承诺值对应的各方计算流程作为开启值提供给验证者, 验证者检验开启部分是否正确以及各方计算流程是否兼容. 由于MPC 协议所有参与方的所有计算均在证明者本地完成, 因此该转换方法被称为“MPC-in-the-Head”. Giacomelli、Madsen和Orlandi[36]进一步提炼了Ishai 等人[93]的构造方法, 发现MPC-in-the-Head 架构下MPC 协议可以无代价地使用不经意传输信道(oblivious-transfer channels) 和任何的确定性两方功能(deterministic two-party functionality), 评估了不同的MPC 协议转化为零知识证明系统的实际效率, 将转换后效率最优的零知识证明系统与Fiat-Shamir 转换相结合, 提出了ZKBoo 证明系统. 随后, Chase 等人[94]对ZKBoo 进行了优化, 进一步减少了ZKBoo 系统所产生的证明大小, 提出了ZKB++ 证明系统. ZKBoo和ZKB++ 所使用的MPC 协议是一个可执行任意布尔电路的三方协议, 这两个证明系统同样可以用于证明任意布尔电路的可满足性问题.

在PQC 2018 上, Derler、Ramacher 和Slamanig[37]基于ZKB++ 证明系统, 对由杂凑函数形成的默克尔树进行成员关系证明, 得到了基于对称密码学原语的环签名方案. 他们的方案可以看做是Libert等人基于格的环签名方案[74]的对称密码版本. 在CT-RSA 2019 上, Boneh、Eskandarian 和Fisch[18]同样利用ZKB++ 证明系统设计了基于对称密码学原语的群签名方案. 由于公钥加密是实现群签名完全匿名性的必要条件, Boneh 等人的群签名方案满足的匿名性为无私匿名性. 此外, Boneh 等人的群签名方案将Intel SGX 芯片作为应用场景, 实现了该场景下所需的匿名撤销等功能. 上述工作在使用ZKB++证明系统作为关键组件时, 由于ZKB++ 的计算和通信开销与电路的乘法复杂度密切相关, 为了充分提升效率他们并没有采用标准的对称密码设计(如SHA256, AES128 等), 而是使用乘法复杂度较低的分组密码LowMC[95]作为基本组件来设计相应的对称密码原语. 根据具体的应用需求来设计乘法复杂度最低的对称密码原语是此类工作的重要组成部分.

由于使用三方协议作为底层协议, ZKBoo 和ZKB++ 的单次执行都会允许恶意的证明者有2/3 的概率欺骗验证者. 这一性质与基于格的Stern 证明系统相同. 为了确保恶意证明者欺骗成功的概率是可忽略的, ZKBoo 和ZKB++ 都需要多次执行(在128 比特安全性下执行次数为200 次以上), 使得ZKBoo和ZKB++ 产生的证明大小较大. ZKBoo 和ZKB++ 之所以选择三分协议作为底层协议, 是因为Ishai等人提出的框架仅支持两方功能, 在这一限制下选择特定的三方协议实现的效率最高. 在CCS 2018 上,Katz、Kolesnikov 与Wang 将预处理模式引入了MPC-in-the-Head 框架[96], 实现了n 方功能和零知识证明系统安全目标的兼容, 从而允许选择更高效的n 方协议, 进一步降低协议重复执行的次数. Katz 等也将他们提出的高效零知识证明系统应用到环签名和群签名的设计中. 相比直接基于ZKB++的群签名[18]和环签名方案[37], Katz 等人的方案效率提升显著, 是目前基于对称密码学原语的最高效的类群签名方案.具体效率对比见表2, 实验数据来自文献[96].

基于格上困难问题构造类群签名和基于对称密码学原语构造类群签名是目前最主流的构造方法. 这两类构造的安全性根据不同的评价指标互有优劣. 一方面, 基于格的方案的安全性依赖于具体的困难问题假设, 基于对称密码学原语的构造在理论上仅依赖单向函数等基本密码原语的存在性, 似乎基于对称密码原语的方案更为可靠; 另一方面, 基于对称密码原语的具体方案出于效率考虑, 使用了尚未广泛研究的新型分组密码LowMC, 而基于格的方案可以归约到格中最坏情况的困难问题, 这个角度来看基于格的类群签名方案安全性更可靠. 当然, 两种设计方法并非是对立的. 在PKC 2020 上, Baum 和Nof 改进了Katz等人的设计方法, 提出了新的基于对称密码学的NIZK 证明系统, 用于证明格上的困难问题SIS[97]. 尽管在该工作中他们并没有将这一证明系统用于构造群签名或环签名方案, 这一新的证明系统有望有效地结合对称密码和格密码的优势.

表2 基于对称密码学原语的类群签名方案效率Table 2 Performance of group signatures and ring signatures from symmetric-key cryptography primitives

5 从随机预言机模型到量子随机预言机模型

随机预言机模型是形式化证明实用密码方案安全性的重要证明模型, 最早由Bellare 和Rogway 正式提出[98]. 在随机预言机模型中, 密码方案所使用的杂凑函数被建模为随机预言机, 敌手只能通过问询该预言机才能获得杂凑函数在特定输入下的输出, 且输出值在像空间均匀随机分布. 随机预言机模型有非常广泛的应用, NIZK 证明系统和数字签名构造中使用的Fiat-Shamir 转换是一种基于随机预言机的通用转换框架, 它将公开抛币(public coin) 的交互式协议中验证方发送的随机消息替换为随机预言机的输出, 从而移除了对交互的依赖.

真实世界中杂凑函数显然可以在本地执行, 因此拥有量子计算能力的攻击者具备在量子叠加态上运行杂凑函数的能力. 为了真实地反映量子攻击者的能力, 随机预言机也应当允许量子叠加态的问询——这样的随机预言机模型被称为量子随机预言机模型. 然而, 允许量子叠加态问询这一改动直接导致了经典的随机预言机模型下一些常见的证明技术不再有效. 例如, 随机预言机模型的安全证明中, 仿真者采用建立询问-返回表的方式来模拟随机预言机. 对于已经记录在表中的问询值, 直接返回对应的输出值. 对于没有记录的新问询值, 仿真者从输出空间均匀随机选取元素作为输出, 并将它们记录在表中. 对于量子叠加态的问询值, 判断问询值是否记录在表首先要求仿真者对量子叠加态进行测量, 从而导致仿真失败. 值得注意的是, 量子随机预言机模型不仅是让经典的证明技术不可用, 也可能使得原本在随机预言机模型下证明安全的方案不再安全. 在FOCS 2014 上, Ambainis、Rosmanis 和Unruh[99]排除了Fiat-Shamir 转换在量子随机预言机模型下有黑盒安全证明的可能.

目前基于后量子困难假设构造的类群签名方案大都依赖于Fiat-Shamir 转换构造. 根据Ambainis 等人的结论, 这类方案在量子随机预言机模型下的安全性并不清晰. 针对Ambainis 的结论, 目前有两类补救措施. 一类是通过对底层的交互式协议加入特定的限制条件, 使得Fiat-Shamir 转换在这些限制条件下是安全的, 包括文献[100–102] 的工作. 另外一类是提出可替换Fiat-Shamir 的在量子随机预言机模型下可证明安全的通用转换方法, 包括Unruh 在Eurocrypt 2015 上提出的Unruh 转换[103]. 现有的类群签名方案是否满足若干限制条件从而可以使Fiat-Shamir 在量子随机语言机模型下安全还需要大量地针对具体构造的讨论. 更加通用的方法是将这些方案使用的Fiat-Shamir 转换替换为Unruh 转换从而得到量子随机预言机模型下可证明安全的方案. 需要注意的是, Unruh 转换的原始安全证明[103]仅适用于满足标准soundness (2-special soudness) 的Sigma 协议, 而大部分基于抗量子假设的类群签名方案所使用的Sigma 协议满足k-special soundness (k > 2). Chase 等人[94]证明Unruh 转换适用于ZKB++ 协议(k = 3), 笔者在ISC 2019 上[104]提供了补充证明表明Unruh 转换适用于所有具有k-special soudness的Sigma 协议(k = poly(λ)). 因此现有的基于Fiat-Shamir 的转换的类群签名方案都可以通过Unruh转换迁移到量子随机预言机模型下安全的方案.

6 展望与结束语

后量子安全的类群签名是后量子密码体系的重要组成部分, 相关研究旨为后量子时代提供实现用户隐私保护的密码学工具. 目前已有的研究成果主要基于格上困难问题和对称密码学原语两类抗量子假设, 较好地解决了在标准模型、随机预言机模型和量子随机预言机模型下后量子安全的类群签名及其主要变种的存在性问题. 该领域的研究正在从理论走向实际, 主要研究方向是为各种类群签名方案提供实用化的后量子安全构造, 同时尽可能提高这些实用化方案的安全性. 该方向还存在若干关键问题有待解决, 包括:

(1) 实用化的格基动态群签名方案. 动态群签名方案允许用户在系统启动后动态加入, 适用于大规模可延展的应用场景. 经典密码体制下的动态群签名方案的群成员关系往往由群管理员的数字签名定义, 管理员可以通过为新成员产生签名的方式使其加入群签名系统. 由于群成员需要后续证明其持有合法的管理员签名, 该数字签名方案需要在标准模型下可证明安全. 然而, 现有标准模型下格基签名方案均依赖于格的陷门函数, 参数过大, 效率低下, 导致相应的动态群签名方案并不高效.

(2) 量子随机预言机模型下高效的类群签名方案. 在随机预言机模型西可证明安全的类群签名方案在量子随机预言机模型下的安全性缺少严格的讨论和分析. 尽管大部分现有方案均可以通过替换Fiat-Shamir 转换为Unruh 转换实现量子随机预言机模型下的可证明安全性, 但使用Unruh 转换会带来显著的效率下降. 分析现有基于Fiat-Shamir 转换的方案在量子随机预言机模型下的安全性, 以及应用和发展现有的Fiat-Shamir 的若干结论来设计量子随机预言机模型下的类群签名方案, 是解决该问题的可能途径.