格上身份基可追踪环签名方案

叶 青,陈晴晴,豆永鹏,张 静,汤永利

(1.河南理工大学 软件学院,河南 焦作 454003;2.陆军装备部驻西安军事代表局驻西安地区第七军事代表室,陕西 西安 710065)

1 引 言

环签名[1]是一种可为签名者提供匿名保护的特殊的数字签名,它允许签名者代表一组用户(环)签名,验证者仅能判定签名者来自一个环,并不能确定具体是哪个用户。可链接环签名(Linkable Ring Signature,LRS)[2]除了具备普通环签名的匿名性功能,还能检测两个签名是否由同一个签名者生成。而可追踪环签名(Traceable Ring Signature,TRS)[3]可看作是功能完备版本的可链接环签名,在可追踪环签名中,如果签名者用相同标签(标签包含一个环和一个关于某个社会问题的字符串issue)对相同消息进行签名,则两个签名能够被检测出属于同一签名者的两次签名,但是签名者的身份不会被泄露;但如果签名者利用相同标签对不同消息进行签名,则追踪环签名可追踪到两个签名的签名者身份,签名者的身份被揭露。可追踪环签名适用于电子投票[4]、区块链[5-6]、匿名电子支付等既需要匿名保护也要避免重复签名的场景。例如,在电子投票系统中应用可追踪环签名时,若某个选民基于同一个环对“张三当选人大代表”(issue)两次投“赞成”票,即对消息“赞成”签名两次,则这两次投票会被检测出为重复投票,但该选民的身份并不会暴露;若他基于同一个环对“张三当选人大代表” (issue)投一次“赞成”票,再投一次“反对”票,即对消息“赞成”和“反对”分别签名时,则其身份会被揭露。FUJISAKI[7]提出了一种在标准模型下次线性尺寸的可追踪环签名,AU 等[8]构造了一个基于离散对数问题的身份基可追踪环签名方案。但上述环签名方案[1-3,7-8]都基于传统数论难题构造,不足以抵抗量子计算机的攻击。近年来,格上密码系统因具有较好的渐近效率、可并行性以及抗量子攻击等特点,成为后量子密码的研究热点。格上可链接环签名最近取得了一些研究进展[9-12],但格上可追踪环签名方面研究成果较少,目前已知的仅有FENG等[13]提出的格上可追踪环签名方案。针对目前格上可追踪环签名方案[13]基于PKI体制构造,具有复杂的数字证书管理负担这一现状,笔者将基于身份的密码体制与格上可追踪环签名相结合,依据BAUM等[12]格上可链接环签名方案的框架,采用原像采样[14]和拒绝采样等技术[15],提出了一个基于SIS困难问题的身份基可追踪环签名方案。与大多数可追踪环签名方案[3,7-8,13]不同,所提方案避免使用臃肿的零知识证明,签名长度较短,方案简洁高效。

2 预备知识

2.1 格的相关定义及困难假设

定义1整数格。Zn中的一个格

2.2 离散高斯分布和拒绝采样技术

2.3 带原像采样的陷门函数

2008年GENTRY等[14]提出的基于SIS问题的带原像采样的陷门函数成为构造格上签名方案的重要技术,具体包括以下3个部分:

2.4 可追踪环签名的定义及安全需求

可追踪环签名方案包括5个算法:参数建立、密钥提取、签名、验证和追踪算法。一个安全的可追踪环签名方案应满足4个性质,即正确性、标签可链接性、匿名性和抗陷害性。正确性包括完备性和公共可追踪性两个方面,其中完备性是环签名的普遍要求,即诚实的签名以压倒性概率能通过验证算法的验证,而公共可追踪性为可追踪环签名的特殊要求,主要是为了保证追踪功能的正确性,即给定针对同一个标签的两个诚实的签名,如果它们为不同签名者所签,追踪算法将接受这两个签名;如果它们为同一签名者对同一消息的签名,追踪算法将把它们“链接”起来;如果它们为同一签名者对不同消息的签名,追踪算法将输出签名者身份。标签可链接性是为了保护整个可追踪环签名系统,它要求即使用户的公私钥都由攻击者产生,攻击者也不可能输出N+1个消息签名对,使它们都能通过验证算法并且它们中的任意两个都被追踪算法接受,其中N代表环中成员的个数。匿名性是环签名的基本要求,即给定一个可追踪环签名,攻击者仅能判断它的签名者来自一个环,而不能确定具体是哪个环成员。抗陷害性要求没有环成员i的私钥,攻击者无法陷害成员i,即攻击者无法产生两个可追踪环签名,使得追踪算法判定它们为成员i所签。可追踪环签名的标签可链接性和抗陷害性包含不可伪造性。可追踪环签名正式的定义及安全模型请参考文献[3,7-8,13],此处不再赘述。

3 方案构造

验证(Vfy(pp,T,μ,Ω))。该算法操作如下:

(1) 对于i∈[N],检查是否‖zi‖≤2σ(m)1/2,如不满足则输出“invalid”;

(3) 如果c1=H(T,μ,pN,gN,hN)=cN+1,输出“valid”,否则输出“invalid”。

(1) 对于所有的i∈[N],如果pi=p′i,将对应的IDi存入TraceList,其中TraceList初始为一个空表;

(2) 如果|TraceList|=N,输出“linked”,其中|·|表示列表或集合中元素的个数;如果IDi是TraceList中唯一的记录,则输出IDi;其他情况,输出“accept”。

下面分析方案的正确性。

由文献[3,7-8,13],可追踪环签名方案的正确性包括完备性和公共可追踪性两个方面,由引理2和引理3,所提方案的完备性是显而易见的,此处不再赘述。下面重点分析所提方案的公共可追踪性:

4 安全性证明

在证明标签可链接性前,首先证明以下相关引理。

引理4给定关于所提方案的一个有效的签名(T,μ,Ω),则

的概率为1-negl(n)。

证明 对以下两种情况分别进行分析:

引理5给定两个签名(T,μ,Ω),(T,μ′,Ω′)满足Trace(pp,T,μ,Ω,μ′,Ω′)=accept,则概率|TraceList|>0的概率是可忽略的。

定理1(标签可链接性) 所提方案在随机预言模型(ROM)下是满足标签可链接性的。

在证明匿名性之前,首先介绍一个关于所提方案的签名模拟算法G。

证明 算法G描述如下:

(3) 输出Ω=(c1,τ,(zi)i∈[N])。

定理2(匿名性) 在ROM下,对于PPT敌手A,所提方案满足匿名性。

证明 C分别接收ISIS或SIS实例如下:

5 性能分析

鉴于目前还没有可以比较的格上基于身份的可追踪环签名方案,这里将所提方案与2个较新的格上基于身份的可链接环签名方案[9,11]进行性能对比,时间开销和存储开销的对比结果分别列于表1和表2中。在这两表中,n为安全参数,q是大素数,正整数m≥5nlogq,N代表环成员个数,T1,TTG,TSP,TSD,TRS,TDT分别表示矩阵-向量乘法、陷门生成、原像取样、高斯取样、拒绝采样和陷门派生等算法运行一次所需的时间。在计算存储开销时,用到了引理2,并且只考虑签名中的向量或矩阵等长度较长的部分。

表1 时间开销比较

表2 存储开销比较 bit

由表1、表2可以看出,在算法时间开销和存储开销方面,本文方案与最新的格上基于身份的可链接环签名方案相当或更小,而普遍认为可追踪环签名比可链接环签名在功能上更加完备。所以总体而言,本文方案优于两个比较对象。

6 结束语

基于原像采样和拒绝采样等技术,笔者提出了第一个格上基于身份的可追踪环签名方案。随机预言模型下,所提方案被证明满足标签的可链接性、匿名性以及抗陷害性,方案的安全性可归约至格上SIS和ISIS困难问题。与类似方案相比,所提方案在时间开销与存储开销方面具有一定的优势。