NTRU格上基于身份的环签名方案

李金波，张 平，张 冀，刘牧华

（河南科技大学 数学与统计学院，河南 洛阳 471023）

0 引言

随着区块链技术的关注度和重视度越来越高，能够实现链上匿名交易的隐私保护技术成为当前的研究热点，其中，环签名技术因去中心化、匿名性、不可伪造性等优势与区块链系统的结构特征相符合，逐渐成为实现匿名性和安全性保护的主流方案之一，因此越来越多的学者开始研究能实现链上匿名交易的环签名技术［1-2］。所谓去中心化，是指环签名没有中心机构，任何一个环成员都能以他所在的整个环的名义匿名性地签署任意消息。验证者知道签名由哪个环生成，但是无法确定是由环中哪个成员生成的。典型的环签名方案有Herranz 等［3］和Chow 等［4］提出的基于身份的环签名方案的安全性都是归约到双线性对上的离散对数困难假设。然而在后量子时代，人们担心量子计算机的到来将会对传统的基于数论困难假设的环签名技术造成威胁［5］，因而设计出许多后量子安全的环签名方案［6-7］。其中，基于格的后量子签名体系由于具有更高的安全性和更快的计算速度等优点，逐渐成为设计签名方案的首选。

环签名的概念最早由Rivest 等［8］于2001 年提出，此后陆续出现各种基于数论困难假设或者利用双线对构造的环签名方案。直到2010 年，王凤和等［9］利用盆景树算法首次提出了格上的环签名方案，方案对固定环攻击是可证明安全的。随后，Wang 等［10］使用格基委派算法也构造出了格上的环签名方案，方案对任意环攻击是可证明安全的。此后的许多方案都是在上述研究的基础上设计的，这类方案依照GPV 数字签名体制，共同特点是每一位环成员在系统建立阶段需要为自己申请公钥；但是随着环成员数量的不断增加，公钥验证矩阵也随之增大，由此将带来复杂繁琐的公钥认证问题。

由于环中每一个成员的公钥都绑定一个数字认证证书，当签名者签署消息时，需要对其他环成员的数字证书进行有效性验证，而当验证者验证签名时，他也需要验证签名者和其他环成员的数字证书。当环中成员数量庞大时，这需要花费大量的时间成本。2012 年，田苗苗等［11］使用消息添加技术构造了一种标准模型下强不可伪造的环签名方案，方案的不足之处是公私钥及签名的长度比较大，同时他们将级联后的系统公钥和环成员身份的散列值作为环成员的公钥，可将方案推广到身份基环签名方案，但是并没有给出方案的安全性证明和性能分析；2013 年，李玉海等［12］完善了文献［11］中的工作，将消息添加技术和身份密码技术相结合，提出了一种标准模型下可规约至小整数解（Small Integer Solution，SIS）困难问题的身份基环签名方案，方案的整体效率相比以往有所提高；2015 年，张利利等［13］使用格基委派技术设计了一种标准模型下的身份基环签名方案，方案生成的签名较短，计算效率较高；2016 年，孙意如等［14］使用理想格技术构造了标准模型下的身份基环签名方案，在一定程度上缩减了公私钥及签名的长度，提高了运算效率；2017 年，贾小英等［15］使用格基委派技术和拒绝抽样技术构造了随机预言机模型下的身份基环签名方案，方案的签名效率很高，然而存储效率稍低；2021 年，赵宗渠等［16］使用MP12 陷门派生技术构造了一种标准模型下基于理想格的可证明安全的环签名方案，方案利用MP12 陷门派生算法和理想格的代数结构，降低了时间复杂度，提高了存储效率；随后，Tang 等［17］使用紧凑高斯采样（Compact Gaussian Sampler，CGS）算法和拒绝抽样技术设计了一种NTRU（Number Theory Research Unit）格上基于身份的环签名方案，除了实现了在随机预言机模型下的无条件匿名性和存在不可伪造性之外，还具有可链接的特性，能检测用户是否用同一私钥对同一消息进行了两次或多次签名；2022 年，Zhou 等［18］使用格基委派技术构造了标准模型下的身份基环签名方案，方案具有全密钥暴露下的匿名性和抵抗内部腐败的存在不可伪造性。本文参考以上工作，旨在设计一种环签名方案——环成员的公钥不需要数字证书认证。本文的主要工作如下：

1）使用NTRU 格构造环签名，利用NTRU 格比一般格的结构性强的优势，使系统私钥和环成员私钥的存储空间比一般格上的小。

2）引入身份密码技术［19］，使环成员的公钥不再依赖数字证书。环成员的身份信息即他们的公钥，避免公钥分发和证书认证过程中的安全问题和计算问题，以及对认证机构的信任问题。

3）将拒绝抽样技术与NTRU 格相结合，利用拒绝抽样技术的优点——签名值与签名私钥的分布相互独立，来弥补NTRU 格上的数字签名的固有缺陷——签名值的分布与签名私钥的分布相关，从而使本文方案的签名结果与私钥不相关，进一步提高了方案的安全性。

4）将所提环签名技术与区块链技术相结合，应用于车联网（Internet of Vehicles，IoV）场景中，不仅能够实现车联网中的高效快速通信，而且能对发布违法信息的车辆实现定位追踪和即时打击，从而保证隐私数据的安全性。

1 预备知识

1.1 格及NTRU格

定义1 格。令Rm为m维欧氏空间。将Rm中一组线性无关向量b1，b2，…，bn(n≤m)的所有整系数线性组合构成的离散子群Λ，称作由这些向量生成的格，即：

其中：m为格Λ的维数；n为格Λ的秩。

1.2 格上的离散高斯分布

定义3 离散高斯分布。对于m∈Z+，Z+是正整数集，令Λ∈Rm为m维格。对于任意实数σ>0 以及任意向量c∈Λ，定义：

格上的离散高斯分布是格密码设计领域的重要工具。当高斯参数为时，它具有很多良好的密码性质：如可以隐藏格上的陷门信息来保证方案的安全性［20-21］。

1.3 格上困难问题

1.4 NTRU格上的陷门生成算法

1.5 高斯抽样及原像采样算法

1.6 拒绝抽样技术

2 方案定义及安全模型

2.1 方案定义

定义8 NTRU 格上的身份基环签名方案（Number Theory Research Unitlattice-based Identity-Based Ring Signature scheme，NTRU-IBRS）由以下4 个多项式时间算法构成：

1）系统建立算法Setup(1n)：输入安全参数n，算法输出系统公共参数PP和主私钥MSK。

2）私钥提取算法Extract(PP，MSK，ID)：输入公共参数PP，主私钥MSK和用户身份ID，算法输出该用户的私钥SKID。

3）环签名算法R-Sign(R，m，PP，ID，SKID)：输入环R，消息m，公共参数PP，签名者的身份ID和私钥SKID，算法输出消息m的环签名Sig。

4）环验证算法R-Verify(R，m，Sig，PP)：输入环R，消息m，环签名Sig和公共参数PP，算法输出“ACCEPT”当且仅当Sig验证通过；否则，输出“REJECT”。

2.2 安全模型

一个安全的NTRU 格上基于身份的环签名方案需要同时满足匿名性和存在不可伪造性［25］。

定义9 匿名性。设任意PPT 敌手A 赢得以下游戏的概率为如果敌手A的优势是可忽略的，则称身份基环签名方案满足匿名性。敌手A 和挑战者C 的匿名性安全模型由以下游戏定义：

1）挑战者C 输入安全参数n，运行Setup(1n)得到公共参数PP和主私钥MSK，之后将公共参数PP发送给敌手A。

2）敌手A 被允许在多项式时间内向挑战者C 进行下述询问：

①环签名询问：敌手A 选择环R，消息m和索引i，挑战者C 运行R-Sign(R，m，PP，IDi，SKIDi)得到环签名Sig并将它发送给A。

②私钥询问：敌手A 选择索引i，挑战者C 将IDi的私钥SKIDi发送给A。

4）敌手A 输出猜测b′∈{0，1}。若b′=b，则敌手A 赢得游戏。

定义10 存在不可伪造性。如果任意PPT 敌手A 赢得以下游戏的概率是可忽略的，则称身份基环签名方案在适应性选择消息和身份攻击下满足存在不可伪造性。敌手A 和挑战者C 的存在不可伪造性安全模型由以下游戏定义：

1）挑战者C 输入安全参数n，运行Setup(1n)得到公共参数PP和主私钥MSK，之后将公共参数PP发送给敌手A。

2）敌手A 在多项式时间内可以向挑战者C 适应性地进行以下询问：

①环签名询问：敌手A 适应性地选择环R，消息m和索引i，挑战者C 运行R-Sign得到环签名Sig并将它发送给A。

②私钥询问：敌手A 适应性地选择索引i，挑战者C 将IDi的私钥SKIDi发送给A。

3）敌手A 输出一个环签名(R′，m′，Sig′)。若满足下面3条，则敌手A 赢得游戏。

①敌手A 未对(R′，m′)进行环签名询问；

②敌手A 未对身份标识ID∈R′的用户进行私钥询问；

③R-Verify(R′，m′，Sig′，PP)输出“ACCEPT”。

3 本文方案描述

3.1 系统建立算法Setup(1n)

3.2 私钥提取算法Extract(PP，MSK，ID)

3.3 环签名算法R-Sign(R，m，PP，ID，SKID)

设签名者IDi(1 ≤i≤l) ∈Rl={ID1，ID2，…，IDl}⊆R，它的私钥为si，待签名的消息m∈{0，1}*。环签名过程如下：

3.4 环验证算法R-Verify(R，m，Sig，PP)

4 安全性分析

4.1 正确性

定理1 NTRU-IBRS 方案满足正确性。

4.2 匿名性

定理2 NTRU-IBRS 在随机预言机模型下满足匿名性。

证明 敌手A 和挑战者C 的游戏模拟如下：

1）挑战者C 输入安全参数n，运行系统建立算法Setup(1n)生成主私钥Bf，g和公开参数PP={n，q，σ，A，h}，并将PP发送给敌手A。

2）敌手A 在多项式时间内向挑战者C 进行下述询问：

①H1询问：A 向C 提交用户身份信息ID，C 收到请求后随机选择p∈并将p返回给A。

②H2询问：A 向C 提交一个含有l个用户的环Rl和消息m，C 收到请求后随机选择c∈Zq并将c返回给A。

③环签名询问：A 向C 提交消息m，环Rl和签名者的身份信 息ID∈Rl，C 收到请求后调用环签名算法R-Sign(R，m，PP，ID，SKID)输出并返回环签名Sig给A。

④私钥询问：A 向C 提交身份信息ID，C 收到请求后调用私钥提取算法Extract(PP，MSK，ID)输出并返回ID的私钥SKID给A。

4.3 存在不可伪造性

定理3 NTRU-IBRS 在随机预言机模型下对于适应性选择消息和身份攻击满足存在不可伪造性。

证明 如果存在PPT 敌手A 能够以不可忽略的概率ε伪造本文方案的环签名，则可以构造出一个挑战者C，C 通过调用A，能够以不可忽略的概率ε′解决SIS 问题。C 管理维护4 个列表L1，L2，L3，L4分别用来存储A 的H1询问、H2询问、私钥询问和环签名询问。4 个列表的初始化均为空。敌手A和挑战者C 的游戏模拟如下：

1）挑战者C 输入安全参数n，运行系统建立算法Setup(1n)生成主私钥Bf，g和公开参数PP={n，q，σ，A，h}发送给敌手A。

2）敌手A 在多项式时间内可以向挑战者C 适应性地进行以下询问，不妨设A 不会发起重复询问；A 在进行私钥询问和环签名询问之前已经问询过相应的哈希预言机。

①H1询问：A 向C 提交用户身份信息ID，C 收到请求后首先检查(ID，H1(ID))是否在列表L1中。若在，则返回H1(ID)作为应答；否则，C 随机选择，将(ID，p)存储在列表L1中并将p返回给A。

②H2询问：A 向C 提交一个消息m、含有l个用户的环Rl和随机选择的l个向量收到请求后首先检查列表L2中是否有相应的记录。若有，则返回相应的结果；否则，C 随机选择c∈Zq，将存储在列表L2中并将c返回给A。

③私钥询问：A 适应性地选择ID。C 在列表L1中找到(ID，H1(ID))，运行算法SamplePre(h，Bf，g，σ，(H1(ID)，0)) 得到ID的私钥s，将(ID，s)存储在列表L3中并将s返回给A。

④环签名询问：A 适应性地选择消息m、环Rl和ID∈Rl。C 在列表L2中查找出相应的记录在列表L3中查找是否有记录(ID，s)，若没有，在列表L1中找到(ID，H1(ID))，运行私钥提取算法得到ID的私钥s。之后，C计算v=H1(ID)As，并使用高斯消元法计算v=H1(ID)Ax的一个解以极大概率使≠s；若j≠i，zj=yj；若j=i，zj=+yj。C 将最终的签名结果Sig=(zj，1 ≤j≤l，v，c)发送给A。

3）敌手A 以不可忽略的概率ε输出关于的伪造，使R-Verify(R′，m′，Sig′，PP)输出“ACCEPT”，并且还需满足下列两个条件：

①敌手A 未对(R′，m′)进行环签名询问；

5 性能分析

5.1 存储开销分析

本文方案使用了NTRU 格的代数结构，系统私钥就是NTRU 格的一组陷门基Bf，g，而这组基可只用h来刻画，因此所需要的存储空间比普通格上的陷门基所需要的存储空间要小。表1 为本文方案与文献［16-17］方案的系统私钥、签名私钥和签名长度的存储开销对比。文献［16］中是理想格上的环签名方案，文献［17］中是NTRU 格上的身份基可链接环签名方案，l表示环成员的个数。可以看出，NTRU-IBRS 的系统私钥和签名私钥的空间复杂度都是O(n)；而文献［16］方案的系统私钥与签名私钥的空间复杂度分别为O(n2)与O(nl)。因此，NTRU-IBRS 的系统私钥和签名私钥的存储开销比文献［16］方案小。文献［17］方案的系统私钥生成采用和NTRU-IBRS 相同的陷门生成算法，因此系统私钥的存储开销与NTRU-IBRS 相同，都为O(n)；虽然文献［17］方案的签名私钥的空间复杂度为O(n)，但是它的签名私钥在系统中需要占用存储空间，而NTRU-IBRS 的签名私钥在系统中仅需占用存储空间，因此文献［17］方案的签名私钥的存储开销略高于NTRU-IBRS。在签名长度方面，NTRU 格的维数扩张会引起签名长度扩张，NTRU-IBRS 的签名长度O(n2l)均大于文献［16］方案的签名长度O(n)+O(l)和文献［17］方案的签名长度O(nl)。

表1 存储开销对比Tab.1 Comparison of storage overhead

5.2 时间开销分析

表2 对比了3 种方案在系统私钥、签名私钥、签名生成和签名验证阶段的时间开销，主要考虑实际应用中比较耗时的运算，包括1 次陷门生成算法的时间TTG、1 次原像采样算法的时间TSP、1 次扩展控制算法的时间TEB、1 次高斯抽样算法的时间TSD、1 次CGS 算法的时间TCG、1 次拒绝抽样算法的时间TRS和n次标量乘法运算的时间Tmul，忽略了耗时较少的哈希函数运算和矩阵加法运算。文献［26］中指出，由于扩展控制算法是原像采样算法的推广，利用扩展控制算法求与原始格相关的更大维数格的陷门基时，需要借助矩阵原像采样算法来实现，也就是说扩展控制算法的时间复杂度OTEB等于原像采样算法的时间复杂度OTSP加上其余运算的时间复杂度Oother，因此时间复杂度为。文献［27］中指出，原像采样算法的时间复杂度通过并行计算可达到O(n2)，其中符号O隐藏了小常数4；而本文矩阵乘法的时间复杂度也是O(n2)，其中符号O隐藏了小常数2。因此，NTRU-IBRS 与文献［16］方案的系统私钥的时间开销相同，都为TTG；签名生成的时间开销相当，都为O(n3l)+O(n2)=O(n3l)；然而在签名私钥和签名验证的时间开销上，NTRUIBRS 的效率更优。文献［28］中指出，CGS 算法的时间复杂度为O(n2)。因此，NTRU-IBRS 与文献［17］方案的系统私钥的时间开销相同，都为TTG；签名私钥的时间开销相当，都为O(n2)；然而在签名生成阶段和签名验证阶段，NTRU-IBRS 的时间开销分别为O(n3l)和O(n3)，均小于文献［17］方案在签名生成阶段的时间开销O(nlTSD)+O(n3l)+O(nTRS)和签名验证阶段的时间开销O(n3l)。

表2 时间开销对比Tab.2 Comparison of time overhead

6 仿真实验与结果分析

6.1 实验环境

本文实验的软硬件环境采用64 位Windows 10 专业版操作系统，Intel Core i5-9500 CPU @ 3.00 GHz，NVIDIA GeForce GT 720 GPU，8 GB 运行内存；.NET Framework 4.8 Advanced Services 开发平台，Matlab R2018a 实验平台，调用SHA256Managed 算法实例化本文的随机预言机，并将安全参数n、素数q和环成员的个数l分别设置为n=256，q=232，l=64。实验中，系统私钥生成、签名私钥生成、签名生成和签名验证的时间均是1 000 次实验的平均值。

6.2 实验结果

表3 为文献［16-17］方案与NTRU-IBRS 在上述参数设置下的存储开销实验数据对比结果。可以看出，NTRU-IBRS 的系统私钥和签名私钥的存储开销都取得了最优。相较于文献［16-17］方案，NTRU-IBRS 的系统私钥长度下降了0～99.6%，签名私钥长度下降了50.0%～98.4%，但是在签名长度的存储开销方面，NTRU-IBRS 的签名长度需要占据更多的存储空间，具体原因见5.1 节的分析。

表3 存储开销实验数据对比 单位：KBTab.3 Experimental data comparison of storage overhead unit：KB

表4 为文献［16-17］方案与NTRU-IBRS 在上述参数设置下的时间开销对比结果。虽然理论分析表明文献［16］方案与NTRU-IBRS 的系统私钥的时间开销相同，都为TTG，但是实验结果表明，文献［16］方案的系统私钥的时间开销略低，这是因为文献［16］方案使用的陷门生成算法是G-陷门生成算法［29］，而NTRU-IBRS 使用的是NTRU 格上的陷门生成算法。文献［17］方案使用的是NTRU 格上的陷门生成算法，因此文献［17］方案与NTRU-IBRS 在系统私钥生成阶段的时间开销相同。在签名私钥生成、签名生成和签名验证阶段，NTRUIBRS 的时间开销最小，与理论分析的结果吻合。NTRUIBRS 的总时间开销也是最小的，环签名算法的总时间减少了15.3%～21.8%。在签名生成阶段，与文献［17］方案相比，NTRU-IBRS 的签名时间减小了22.6%；在签名验证阶段，与文献［16］方案相比，NTRU-IBRS 的验证时间减小了21.6%。

表4 时间开销实验数据对比 单位：msTab.4 Experimental data comparison of time overhead unit：ms

7 应用场景

NTRU-IBRS 方案在系统私钥生成、签名私钥生成、签名生成和签名验证的时间效率上具有一定的优势，因而在算法的整体实现上具有较小的时间开销。同时，NTRU-IBRS 减小了系统私钥和签名私钥的长度，但是却增加了签名的长度。因此，NTRU-IBRS 适用于对签名的空间开销要求较低，而对其余开销要求较高的场景。动态车联网就是这样一种应用场景，它使用环签名和区块链作为底层技术，实现局部范围内车辆的更新和删除以及车辆间的信息收发。每个车联网单元为辖区内的车辆分发密钥以便对车辆进行管理，不同单元的环参数不同，因此车辆由一个单元驶入另一个单元时需要重新获取密钥。将车辆的移动速度和单元的辖区范围考虑在内，平均每分钟每个单元就要为环列表中新增的车辆生成密钥，因此该场景对密钥的时空开销有较高要求。车联网由区块链网络、路边单元、移动边缘计算（Mobile Edge Computing，MEC）服务器、车辆监管部门、执法部门和车辆6个功能模块构成。区块链网络主要用来存储车辆真实身份信息、环中公共参数和交易信息；路边单元负责车辆和其他实体的信息转发，不同的路边单元覆盖不同的车联网区域；MEC 服务器搭载在路边单元上，转发路边单元收到的信息，为车辆提供边缘计算服务；车辆监管部门负责生成系统初始化参数，将部分参数在网络中广播，并将系统私钥发送给执法部门；执法部门负责生成车辆签名密钥、实时更新和删除驶入和驶离路边单元范围内的车辆信息，并备份车辆身份信息和对应的签名密钥，以便对广播恶意信息的车辆进行身份溯源［30-31］。NTRU-IBRS 与车联网结合除了在通信效率上的优势外，还避免了复杂的公钥数字证书的颁发流程，进一步减小了系统的时间开销。动态车联网模型如图1 所示。

图1 动态车联网模型Fig.1 Dynamic IoV model

该模型共分为4 个阶段，分别是系统建立阶段（1～2）、车辆注册阶段（3～9）、车辆通信阶段（10～12）和车辆溯源阶段（8，13～15）。

1）系统建立阶段：车辆监管部门运行Setup(1n)生成并在网络中广播系统公共参数PP={n，q，σ，H1，H2，A，h}，并将系统主私钥Bf，g发送给执法部门。

2）车辆注册阶段：车辆将自己的身份信息ID发送给车辆监管部门请求加入环列表，车辆监管部门将车辆身份信息ID发送给执法部门请求认证。执法部门管理维护区域内的环列表和身份-密钥列表，首先运行Extract(PP，Bf，g，ID)生成私钥SKID并更新环列表车辆信息，之后将(ID，SKID)存入身份-密钥列表用于追踪违法车辆。执法部门返回认证通过消息，车辆监管部门再将认证通过消息返回给车辆并将身份信息ID和更新后的环列表以交易的形式存入区块链。最终车辆收到自己的私钥SKID，注册成功。

3）车辆通信阶段：车辆输入明文消息m和私钥SKID，运行R-Sign(R，m，PP，ID，SKID)生成环签名Sig。目标车辆接收环签名并运行R-Verify(R，m，Sig，PP)来验证Sig是否可信。若环验证算法输出“ACCEPT”，则目标车辆接收环签名并与发送方建立连接。

4）车辆溯源阶段：若目标车辆接收到违法签名，则目标车辆将向执法部门举报并提交异常签名。执法部门根据签名信息在O(l)（l为环中的车辆数）时间内获得签名值对应的私钥，然后在身份-密钥列表中查询车辆真实身份信息，之后追踪相应车辆并判断其是否合法，若不合法则将它移出环列表。同时，执法部门将违法车辆的身份信息和更新后的环列表发送给车辆监管部门，由车辆监管部门将处理结果打包上链。

8 结语

本文使用拒绝抽样技术设计了一种NTRU 格上的身份基环签名方案NTRU-IBRS，降低了系统私钥和签名私钥的存储开销，避免了繁琐的公钥数字证书的颁发和认证流程，提高了环签名算法的整体计算效率。在随机预言机模型下，证明方案具有匿名性和适应性选择消息和身份攻击下的存在不可伪造性。将方案与区块链技术相结合，应用于动态车联网场景中，有效地保证了车辆在通信过程中身份的隐私性和消息的可靠性。接下来的工作将致力于降低环签名的长度，或者研究如何将格上的累加器技术应用于本文方案以固定环签名的长度，从而进一步优化算法的性能。