格上可编程哈希函数的环签名方案

葛炳辉,赵宗渠,何 铮,秦攀科

(河南理工大学 计算机科学与技术学院,河南 焦作 454000)

0 概述

随着现代科技的发展,电子签名技术已广泛应用于人们的日常生活。环签名作为电子签名中的一种,常用于电子现金、匿名电子投票、匿名举报和区块链应用等。环签名由密码学家RIVEST等人[1]于2001年提出,其与群签名一样,都为签名者提供匿名性签名方案。在环签名中,没有管理者只有环成员,环成员之间彼此独立,无需相互合作。在签名过程中,签名者首先选定1个临时签名者集合,签名者也包含在该集合中,然后签名者利用自己的私钥和集合成员的公钥就可单独对消息进行签名。任何1位环成员都能代表集合对消息进行签名,且验证签名只需集合成员的公钥、消息和签名,无需签名者的私钥,从而确保环签名的匿名性。研究人员采用不同安全模型提出多种环签名方案,其安全性主要基于大整数因子化[1-3]、离散对数[4-5]和双线性配对[6-8]等数论假设。随着量子计算机技术的进步,大整数因子化和离散对数等问题可用Shor量子算法在概率多项式时间(Probabilistic Polynomial Time,PPT)内求解,这给密码设置带来新的挑战,上述环签名方案等传统安全保护方法在量子计算环境下已不再安全[9]。

基于格的密码构造能抵抗量子攻击,且格中主要为线性运算和模运算,相较传统密码指数运算速度更快,因此其有望成为后量子传统公钥替代者之一,基于格的密码方案设计也成为学者们的研究热点[10-11]。由于格中问题在一般情况和最坏情况下困难性相同,因此格上任意实例的安全性都相同,该特性吸引众多密码学家对基于格的环签名方案进行研究[12-13]。2010年,CASH等人[14]提出首个基于格的环签名方案,并采用格基派生技术为环成员产生公私钥,但是该方案签名长度较长,计算费时不利于实施。2011年,WANG等人[15]提出基于格的环签名新方案,但该方案缺少标准模型下的安全性证明。2012年,田苗苗等人[16]利用GPV格点筛选算法[11]提出一种基于格的环签名高效方案,但如果将该方案中验证矩阵的l+2个公钥和环签名向量代入签名验证公式,则敌手最多试(l+2)2次就可找到满足签名验证公式的公钥从而找到签名者,因此该方案不具备匿名性。2018年,热娜等人[17]针对文献[15]方案中不满足不可伪造性的问题进行优化后,提出基于格的环签名改进方案,该方案在随机预言模型下证明满足环签名中的匿名性和不可伪造性,并使用MP12陷门函数[10]生成陷门。虽然该方案已证明具有安全性,但是在随机预言模型下证明安全的方案在实际应用中有可能不安全,且该方案的签名密钥和签名长度较长。

2012年,HOFHEINZ等人[18-19]提出可编程哈希函数(Programmable Hash Function,PHF),该函数是一种可模拟随机预言机某些可编程性质的特殊哈希函数[20],并利用可编程哈希函数分别构造了基于双线性映射和基于RSA算法的签名方案,这2种方案具有更短的签名长度,且从理论上更容易证明其安全性。传统可编程哈希函数的定义与构造都存在特定于DL群之间的代数结构问题,这也是几乎所有已知可编程哈希函数均由DL问题构造的原因。2016年,ZHANG等人[21]提出格上可编程哈希函数的概念,利用格上可编程哈希函数重新构造了格上签名方案,该方案继承了传统可编程哈希函数签名方案的优点,改进了公钥过长的不足。虽然格和DL群之间代数结构差异较大,传统可编程哈希函数定义看似不适合格,且格上可编程哈希函数已超过传统可编程哈希函数的范围,但由于格上可编程哈希函数继承了传统可编程哈希函数的概念,并运用格上分区证明技巧[21],因此仍将其归类于可编程哈希函数。

文献[21]指出在非齐次小整数解(Inhomogeneous Small Integer Solution,ISIS)假设下,任何基于格上的可编程哈希函数均抗碰撞,因此可直接应用于环签名方案。为缩短格上环签名方案的签名和密钥长度,本文提出一种基于格上可编程哈希函数的环签名新方案,利用可编程哈希函数的特殊性质和MP12陷门函数生成陷门,将可编程哈希函数嵌入环签名的构造中,并对本文方案在标准模型下自适应选择消息攻击的存在不可伪造性(Existential Unforgeability against Adaptive Chosen Messages Attack,EUF-CMA)安全进行分析。

1 预备知识

1.1 格

(1)

(2)

1.2 格上的困难问题

本文基于格上的小整数解(Small Integer Solution,SIS)问题和非齐次小整数解问题这2种困难问题研究格上可编程哈希函数环签名方案的安全性。

1.3 格上可编程哈希函数

3)统计上更接近陷门密钥。对于全部密钥(K′,td)←H.TrapGen(1k,A,B)和K←H.Gen(1k),(A,K′)和(A,K)之间的统计距离最大为γ。

若γ可忽略而δ不可忽略,则称该哈希函数为(u,v,β)-PHF;若u为k中随机选取的多项式,则称该哈希函数为(poly,v,β)-PHF。

1.4 环签名

环签名方案由KeyGen、Sign和Verify 3个概率多项式时间算法组成[3]。

1)KeyGen(1n)算法。输入系统安全参数n,KeyGen算法为每位环成员生成其签名密钥ski和验证密钥vki。

1.5 环签名安全模型

若环签名方案满足匿名性和不可伪造性2个条件,则该环签名方案为安全的签名方案。

1)匿名性。假设PPT内敌手A以优势Padv=Psuc-1/2赢得游戏,Psuc为敌手A赢得此游戏的概率,若得到的Padv可忽略,则该环签名方案满足匿名性。

(3)敌手A输出身份猜测b′。

2)不可伪造性。假设PPT内敌手A赢得游戏的概率Psuc可忽略,则称该环签名方案在选择子环和适应性选择消息攻击下具有不可伪造性。

2 方案描述

3 安全性分析

3.1 匿名性分析

定理1本文格上可编程哈希函数的环签名方案满足完全匿名性。

证明对本文方案匿名性的证明过程如下:

3)敌手A适应性选择询问用户i

5)敌手A输出身份猜测b′。

3.2 不可伪造性分析

证明对本文方案不可伪造性的证明过程如下:

(2)t=t′∧b=0:算法B停止。

假设全部消息M1,M2,…,Mu在回答签名查询时,通过算法B使用相同标签t=t′,对于i∈{1,2,…,u}使得(TMi,SMi)=H.TrapEval(td,K′,Mi),给出2个条件:1)某些标签t用于回答超过v个消息的签名;2)SMi对于某些i∈{1,2,…,u}不可逆,当SM*≠0或者t*≠t成立时,模拟过程中止。

4 效率分析

本文利用格上可编程哈希函数的特殊性质设计出一种在标准模型下可证明安全性的环签名方案,并以验证密钥长度、签名密钥长度、签名长度以及基于格上的困难问题作为方案效率评价指标,将本文方案与文献[15-17]中格上同类型环签名方案进行对比,结果如表1所示。

表1 4种格上环签名方案评价指标比较结果Table 1 Evaluation index comparison results of four ring signature schemes on lattices

5 结束语

格上可编程哈希函数能模拟随机预言机部分可编程性质,通过格上分区证明方式直接应用于签名构造和安全性验证。本文提出一种新的格上可编程哈希函数环签名方案,利用MP12陷门函数生成陷门,将可编程哈希函数应用到环签名构造中,进而形成验证密钥、签名密钥和签名。分析结果表明,该方案所得签名和密钥较其他格上环签名方案更短,且在标准模型下满足EUF-CMA安全要求。后续将研究如何在保持签名密钥和签名长度不变的情况下,缩短验证密钥长度并提高效率,同时考虑将本文方案推广到基于身份的环签名方案中,以得到更短的签名和密钥。