前向安全的格基代理签名

谢 佳1 胡予濮2 江明明3

1(河南财经政法大学计算机与信息工程学院 郑州 450046) 2(综合业务网理论及关键技术国家重点实验室(西安电子科技大学) 西安 710071) 3(淮北师范大学计算机科学与技术学院 安徽淮北 235000)

(xiejia199325@163.com)

摘 要 顾名思义,前向安全的代理签名具备前向安全性和可代理性,因而,自提出以来,已被广泛应用在移动通信、电子拍卖等众多应用场景中.目前现有的前向安全的代理签名基本上都是基于离散对数难题亦或是大整数分解问题.而这些问题随着量子计算机逐渐成为现实,将会变得不再困难.因而,寻找量子计算环境下前向安全的代理签名已迫在眉睫.现存的量子安全的公钥密码体制有4类,分别为基于Hash的密码体制、基于编码的密码体制、多变量公钥密码体制以及格公钥密码体制.在这4类公钥密码体制中,格公钥密码以其量子免疫性,计算简单高效,任意实例下的安全性和最坏实例下的安全性相当等优势在近10年得到了快速发展,并已经取得了显著成就.在格上引入前向安全的代理签名这一概念并给出其安全性模型,基于格上已知NP困难的小整数解问题(small integer solution, SIS)提出了2个前向安全的格基代理签名.在这2个签名中,其中1个签名在随机预言机模型下被证明是不可伪造的,能够抵抗恶意原始签名人和未被授权代理签名人攻击,且与之前格基代理签名相比较,以牺牲效率为代价,达到了实现前向安全性的目的;另外1个签名在标准模型下是安全的,且能实现前向安全性.

关键词 格公钥;前向安全;代理;签名;不可伪造性

中图法分类号 TP309

收稿日期2020-05-13;修回日期:2020-11-27

基金项目国家自然科学基金青年科学基金项目(61802110,61702161);河南省重点研发与推广专项(科技攻关)(202102310195);河南省高等学校重点科研项目(19A413005,18A520003)

This work was supported by the National Natural Science Foundation of China for Young Scientists (61802110, 61702161), the Key Research and Development and Promotion Program of Henan Province (Science and Technology) (202102310195), and the Key Research Found for Higher Education of Henan Province (19A413005, 18A520003).

Lattice-Based Forward Secure Proxy Signatures

Xie Jia1, Hu Yupu2, and Jiang Mingming3

1(College of Computer and Information Engineering, Henan University of Economics and Law, Zhengzhou 450046) 2(State Key Laboratory of Integrated Services Networks(Xidian University), Xian 710071) 3(College of Computer Science and Technology, Huaibei Normal University, Huaibei, Anhui 235000)

Abstract With advantages of both forward security and proxy, the forward secure proxy signature has been widely applied in mobile communication and electronic auction since it was proposed. However, most of the existing forward secure proxy signatures are based on the classic number theory problem, such as the problem of discrete logarithms and the problem of factorization, which are no longer secure when the general quantum computers become a reality. So looking for the quantum-immune forward secure proxy signature is much urgent. Among the four quantum-immune public key cryptographies, lattice-based cryptography enters a rapid development period in the last ten years and has got many achievements, having the advantages of quantum-immune, computing simply and efficiently, and the worst-case to average-case security guarantees. In this paper, we firstly introduce the concept and the security model of forward secure proxy signature in lattice-based cryptography, and propose two forward secure proxy lattice-based signature schemes based on the small integer solution problem, which is the NP-hard problem. One is the first lattice-based forward proxy signature in the random oracle model, which is proven secure against the polynomial time adversary(both of the unauthorized proxy signer and the malicious original signer). And the forward security is satisfied at the expense of efficiency. The other is proven unforgeable and forward secure in the standard model, which is also the first lattice-based attempt in the standard model.

Key words lattice; forward secure; proxy; signature; unforgeable

1996年Mambo等人[1]首次提出代理签名这一概念.在代理签名模型中,原始签名人委托代理人进行签名,签名验证者能够有效区分当前签名来自代理签名人还是原始签名人.由于其在移动通信、分布式系统和电子拍卖等领域的广泛应用[2-5],2003年前后,各种代理签名[6-9]如雨后春笋般涌现.然而,量子计算机的出现使得我们对代理签名的安全性有了更高的要求.2010年Jiang等人[10]首次利用盆景树模型构造了格基代理签名方案.该方案在标准模型下代理签名人不能伪造原始签名人进行签名权力委托,但原始签名人却可以成功伪造出代理签名者的签名.2011年夏峰等人[11]和Wang等人[12]同样使用盆景树模型构造了格上代理签名方案.为了克服格维数随代理权利委托逐渐增大的问题,Kim等人[13]使用格上固定维数的委派技术构造了格上高效的身份基代理签名方案.随后,更加高效的格基代理签名方案[14-16]相继被提出.

在传统的签名方案中,一旦签名密钥暴露,签名就变得不可信任,无论该签名来自密钥泄露事件之前还是密钥泄露之后.为了解决这个问题,1997年Anderson[17]提出了前向安全签名的概念.前向安全签名,顾名思义,即使暴露当前时段签名密钥,也不会影响之前签名的有效性.因而,前向安全签名可以减少密钥暴露的威胁.前向安全的签名方案大致可分为2类:1)常规前向安全签名[18-21];2)具有特殊性质的前向安全签名,如身份基前向安全签名[22-24]、前向安全阈值签名[25-26]、前向安全代理签名[27-32]、前向安全群签名[33-37]、前向安全的序列聚合签名[38]等.

由于兼顾可代理和前向安全的优势,前向安全的代理签名自提出以来得到了快速发展[27-32].然而,现存的前向安全代理签名大都基于离散对数或整数分解问题,而Shor[39]早在1997年已经指出,经典数论问题(大整数分解和离散对数问题)在量子计算环境下已不再安全.随着量子计算机的逐渐推广,寻找量子免疫的前向安全代理签名就显得尤为迫切.

幸运的是,格公钥密码以其存在任意实例到最坏实例的规约、计算简单高效(格基密码的相关运算只是简单的矩阵向量乘法和模加法)、能抗量子攻击等诸多优势,成为后量子时代密码算法的不二选择.因而,基于格基困难问题构造前向安全代理签名可能会是一个很好的尝试.

本文的主要贡献有2个方面:

1) 基于格上的小整数解问题,我们提出了首个随机预言机模型下前向安全的格基代理签名;

2) 借助于格基委派技术和消息添加技术,我们构造了标准模型下前向安全的格基代理签名.

1 预备知识

本节我们将对文中用到的一些符号和参考文献中已知的一些结论作出说明.

1.1 基本定义

本文中,我们将安全参数约定为正整数n,其他参数均为其函数.文中向量和矩阵分别用小写黑斜体字母和大写黑斜体字母表示.分别表示矩阵A和向量a的欧几里德范数.表示矩阵A的Gram-Schmidt正交化.表示矩阵A和矩阵B的级联.表示向量的级联.

1.2 格的相关知识

定义1. 格.已知矩阵B=(b1b2‖…‖bm),b1,…,bm∈Rnm个线性无关向量,则由B生成的格Λ

其中,格Λ的秩、格Λ的维数分别为mnB为格Λ的一组基.

定义2[40]. q-ary格.已知素数q,正整数nm,任意矩阵A∈Z以及向量u∈Z定义m维满秩q-ary格为

Zm|Ax=0(mod q)};
Zm|Ax=u(mod q)}.

定义3. 高斯函数.已知正数∀s∈R+c∈Rmn维格Λ.那么,则以s为参数、以c为中心的高斯函数定义为而格Λ上以c为中心、s为参数的离散高斯函数则定义为

DΛ,s,c(x)=ρs,c(x)ρs,c(Λ),

其中,当向量c=0时,DΛ,s,0(x)和ρs,0(x)可简写为DΛ,s(x)和ρs(x).

定义4. Dm×m分布.已知q为素数,表示可逆矩阵Ai=[ai1ai2‖…‖aim]在空间Z上的分布.其中aijDZm,σj∈[m].

引理1. 给定任意实数σ>0,正整数m,有:

引理2[41]. 设素数q≥3,正整数满足m6n lb q,存在1个概率多项式时间(PPT)算法TrapGen(1n)输出矩阵A∈Z和格Λ(A)的一组基T,其中A的分布与Z上的均匀分布统计不可区分,且以极大概率成立.

引理3[42]. 已知正整数q≥2,m>n,矩阵A∈ZΛ(A)的一组基T以及高斯参数则对任意的向量c∈Rmu∈Z

1) 存在1个PPT算法SampleD(A,T,σ,c)能够输出一个分布统计接近于DΛ(A),σ,c的向量v

2) 存在一个PPT算法SamplePre(A,T,σ,u)能够输出一个分布统计接近于DΛu(A),σ的向量v.

引理4[43]. 给定格Λ(A)的一组基T,其中,A∈ZZZ那么,存在一个PPT算法能够输出一个更大维数的格及其基T′.算法具体描述为:

其中si满足是第i个标准基向量.

引理5[43]. 已知Tn维整数格Λ的任意一组基,参数存在PPT算法RandBasis(T,σ)能够输出格Λ的另一组基T′满足另外,若对于同一个格的不同基T0T1,设则算法RandBasis(T0,σ)的输出和RandBasis(T1,σ)的输出统计不可区分.

引理6[44]. 已知A∈Z为满秩矩阵,矩阵RDm×mT为格Λ(A)的一组基,高斯参数其中高斯参数σR满足σR=为空间Zm×m中满足且模q可逆的矩阵的分布.则存在一个PPT算法BasisDel(A,R,T,σ)能够输出格Λ(AR-1)的一组基T′,使得若矩阵R是从Dm×m中抽取的l个矩阵的乘积,则参数满足ω(lb m)12)l·ω(lb m).

定义5. 小整数解问题.给定随机矩阵A∈Z和实数β>0,格上的小整数解(small integer solution, SIS)问题即求得一个向量v使得Av=0 mod q均成立.

2 前向安全代理签名的定义

本节我们将对前向安全代理签名的定义以及安全性证明作出阐述.

定义6. 前向安全代理签名方案.1个完整的前向安全签名方案由7个多项式时间算法构成:系统建立算法Setup、密钥生成算法Keygen、代理委派算法Delegate、委派认证算法D-Verify、密钥更新算法KeyUpdate、代理签名算法ProxySign和签名验证算法ProxyVerify.

1) Setup.输入安全参数n,密钥生成中心(KGC)运行该算法生成并输出系统公共参数PP.

2) Keygen.输入公共参数PP,KGC运行该算法输出原始签名人Alice的公私钥对(ska,pka)和代理签名人的公私钥对(skb,pkb).

3) Delegate.为了将签名权利委派给代理人Bob,原始签名人Alice以自身私钥ska和Bob的身份idb为输入,运行该算法生成代理签名私钥SKid|0并将该私钥发送给Bob.

4) D-Verify.接收到SKid|0后,Bob验证其是否为Alice的合法委派私钥,若否,则返回至上一步继续请求委派.

5) KeyUpdate.输入当前时间i、代理签名者身份idb以及之前时段的代理签名私钥SKid|i-1,该算法输出当前最新的代理签名私钥SKid|i.

6) ProxySign.输入签名消息m和当前时间i,Bob利用代理签名私钥SKid|i生成签名sigi,并将sigi作为m的代理签名.

7) ProxyVerify.以(sigi,m)为输入,当且仅当sigi为消息m的合法签名时,算法输出为“1”;否则输出“0”.

定义7. 正确性.定义6的前向安全代理签名方案中,签名方案满足正确性是指ProxyVerify(sigi,m,id,i)能以压倒势的概率输出“1”.

定义8. 不可伪造性.考虑前向安全代理签名方案的不可伪造性时,往往有2种安全威胁要考虑:

1) 敌手A1,即未被授权的代理签名人想要模仿被授权的代理签名人进行签名;

2) 敌手A2,即恶意的原始签名人试图代替代理签名人完成代理签名.

对于任意多项式时间的敌手A1和A2,挑战者能够赢得以下游戏(游戏由Setup,Queries和Forgery三个步骤组成)的概率均为可忽略时,我们称该方案是不可伪造的,且是前向安全的.

1) Setup.挑战者C运行方案的初始化算法,生成系统公共参数PP,并将其向敌手公布.

2) Queries.在询问阶段敌手可作3个询问.

① DelegateQuery.当敌手发送代理签名者身份id作委派询问时,挑战者C生成相应的代理签名私钥SKid|0并将其返还给敌手.

② BereakinQuery.当敌手发送时段j,代理签名者身份idb作询问时,挑战者C生成当前时段的代理签名私钥SKid|j并将其返还给敌手.

③ ProxySignQuery.当敌手发送(id,i,m)作代理签名询问时,挑战者C生成当前时段的代理签sigi并将其返还给敌手.

3) Forgery.在伪造阶段,敌手输出一个关于的签名(u*,v*).当签名满足3个条件时,我们称敌手伪造成功:

① 1≤t*<j

未被用作委派询问;

未被用作代理签名询问,且签名验证者对签名的输出为“1”.

3 随机预言机模型下格基前向安全代理签名

3.1 方案描述

n为安全参数,素数那么格上的前向安全代理签名方案可分为7步.

1) Setup.输入系统的安全参数n,KGC生成系统公共参数PP如下.T为预先指定的时间段数以及高斯参数(σ0,σ1,…,σT-1),高斯参数(s0,s1,…,sT-1),其中2个Hash函数分别为H:{0,1}*→ZH1:{0,1}*→Z

2) Keygen.输入公共参数PP,原始签名人Alice(身份为ida)和代理签名人Bob(身份为idb)分别运行引理2中的格基陷门生成算法TrapGen(1n)生成2组随机格和其陷门基,分别为Λ(A),Λ(B),TA∈ZZ满足A∈ZB∈Z

3) Delegate.为了将签名权利委派给代理人Bob,原始签名人Alice计算H(ida|idb|0)=R0=Ra→b|0.随后Alice运行引理6中的格基委派算法BasisDel(A,R0,TA,σ0)生成并输出Ta→b|0=[t1t2‖…‖tm]作为Alice授权给Bob的代理签名密钥.

4) D-Verify.接收到签名密钥Ta→b|0后,Bob验证是否满足.若否,则返回至步骤3,继续完成代理权利的委派.

5) KeyUpdate.输入(idb,i,Ta→b|i-1),其中i为当前时间,0<iT-1,以及之前的代理签名私钥Ta→b|i-1,Bob计算Ra→b|i-1=H(ida|idb|i-1)…H(ida|idb|0),Rb|i-1=H(idb|i-1)…H(idb|1)∈Z以及矩阵和矩阵Bb|i-1=令矩阵随后Bob运行格基委派算法BasisDel(Aa→b|i-1,Ri,Ta→b|i-1,σi)和分别生成Ta→b|iTb|i作为当前时段的签名私钥.

6) ProxySign.输入签名消息m,Bob计算μ=H1(ida|idb|m|i),随后运行引理3中的原像采样算法得向量uiSamplePre(Aa→b|i,Ta→b|i,si,μ)和viSamplePre(Bb|i,Tb|i,si,μ).最后,Bob输出(ui,vi)作为当前时段对消息m的签名.

7) ProxyVerify.接收到签名之后,验证者首先计算矩阵Ra→b|i=H(ida|idb|i)…H(ida|idb|0)和矩阵Rb|i=H(idb|i)…H(idb|1),μ=H1(ida|idb|m|i).算法输出为“1”,当且仅当:

3.2 正确性

定理1. 3.1节构造的格基前向安全代理签名满足正确性.

证明. 假设(ui,vi)为对消息m的签名,由ProxySign可知ui,vi分别来自2个原像采样算法,即由SamplePre(Aa→b|i,Ta→b|i,si,μ)求得ui以及viSamplePre(Bb|i,Tb|i,si,μ).由引理3可知uivi分别服从分布DΛμ(Aa→b|i),siDΛμ(Bb|i),si.因而可得Aa→b|iui=μ mod qBb|iui=μ mod q.由KeyUpdate以及引理6可知:

A(H(ida|idb|i)…H(ida|idb|0))-1=

故而可得μ mod q.再由引理1可知故而ProxySign中①和②这2个条件满足,即ui,vi满足正确性.

证毕.

3.3 安全性分析

定理2. 假定格上的SIS问题在多项式时间算法攻击下是困难的,则以上格上的前向安全代理签名方案在随机预言机模型下是存在性不可伪造的.

引理7. 假定格上的SIS问题在多项式时间算法攻击下是困难的,则3.1节构造的格前向安全代理签名方案在类型1敌手攻击下是存在性不可伪造的.

证明. 假定存在一个多项式时间的敌手A1能够以不可忽略的概率攻破前向安全代理签名方案,那么我们可以构造一个模拟器C能够求解格上的SIS问题.假定被选中的身份为

调用:调用格上的SIS问题实例,模拟器C需要返还一个合法的解.

已知:矩阵Aa→b*|t*∈ZΛ(Aa→b*|t*)和实数

返回:任意向量u∈Zm,满足Aa→b*|t*u=0 mod q

首先,我们假设3个条件成立:

1) 对于每一个时间段i=0,1,…,T-1,敌手A1可以适应性地对任意身份作多项式次H询问;

2) 对于任意的j<i,当敌手A1在时刻i对某一身份作H询问时,假设A1对该身份在时刻jH询问已经完成;

3) 在对任意签名人作签名私钥询问之前,假定A1已经预先完成相关的HH1询问.

Setup.C运行格基陷门生成算法TrapGen(1n)生成2组随机格和其陷门基,分别为Λ(A),Λ(B),TA∈ZZ满足A∈ZZ并公布矩阵AB.

Queries.当敌手A1伪造签名时,假设C随机选择i*(1≤i*T-1)作为伪造签名的时段.敌手A1可以适应性地作询问:

1) H-Oracle-Query.对于任意的时间i=0,1,…,T-1,A1可以适应性地对任意身份作H询问.

模拟者C维持一个列表L1={ida,idb,i,Ri}.输入身份和时间的一组数据(ida,idb,i),C首先在列表L1中查找(ida,idb,i).若(ida,idb,i)已存在于L1中,则模拟者C返还相应的Ri给敌手A1.否则,C从Dm×m中选择1个矩阵Ri并存储(ida,idb,i,Ri)在列表L1中.最后,模拟者C返还相应的Ri给敌手A1.

模拟者C维持1个列表输入身份和时间列表(idb,i),C首先在列表L2中查找(idb,i).若(idb,i)已存在在L2中,则模拟者C返还相应的给敌手A1.否则,C从Dm×m中选择1个矩阵并存储在列表L2中.最后,模拟者C返还相应的给敌手A1.

2) DelegateQuery.模拟者C维持1个列表L3={ida,idb,0,Ta→b|0}.假定Q表示敌手能够作委派询问的最大次数,敌手A1随机选择l∈{1,2,…,Q},C所作回应如下:

如果idb并非第l次委派询问,则C回应如下.输入身份和时间的一组数据(ida,idb,0),C首先查找列表L1找到其对应的Hash值R0并运行BasisDel(A,R0,TA,σ0)生成Ta→b|0.最后,模拟者C将(ida,idb,0,Ta→b|0)存储在列表L3中,并将Ta→b|0发送给A1.

如果idb刚好是第l次委派询问,则C终止操作.

3) KeyUpdateQueries.C维持列表L4={ida,idb,i,Aa→b|i,Ta→b|i,Bb|i,Tb|i}.当敌手A1发送(ida,idb,i)作签名私钥询问时,C所作回应为:

如果idb并非第l次委派询问,则C回应如下.对于任意的i∈[T-1],j<i,由之前的假设可知,在此之前,A1已完成对(ida,idb,j)和(idb,j)的H-Oracle-Query.当敌手A1对(ida,idb,i)和(idb,i)作H-Oracle-Query时,C查找列表L1L2找出对应的然后,C运行格基委派算法BasisDel(Aa→b|i-1,Ri,Ta→b|i-1,σi)和BasisDel(Bb|i-1,分别生成Ta→b|iTb|i.最后,C将(ida,idb,i,Aa→b|i,Ta→b|i,Bb|i,Tb|i)存储至L4中,并将Ta→b|i返还给敌手.

如果idb刚好是第l次委派询问,则C回应为:

① 如果ii*,C随机选择2个矩阵W,X∈Z并将(ida,idb,i,Aa→b|i,W,Bb|i,X)存储在列表L4中.最后,C将W作为Ta→b|i返还给敌手A1.

② 如果i=i*+1,C运行2次TrapGen(1n)分别生成Aa→b|i*+1∈ZZBb|i*+1∈ZTb|i*+1∈Z最后C返还Ta→b|i*+1给敌手,并将数据(ida,idb,i*+1,Aa→b|i*+1,Ta→b|i*+1,Bb|i*+1Tb|i*+1)存储在列表L4中.

③ 如果i*+1<i<T,模拟者C操作与idb并非第l次委派询问时一致.

4) H1-Oracle-Queries.C维持列表L5={ida,idb,i,m,ui,vi,Aa→b|iui}.当敌手A1发送(ida,idb,i,m)作H1询问时,C所作回应如下:如果L5列表中已经存在(ida,idb,i,m),则将其对应的Aa→b|iui作为其Hash值H1(ida|idb|m|i)发送敌手;否则,C在列表L1L2L4中分别查找H(ida|idb|i),H(idb|i))和(ida,idb,i,Aa→b|i,Ta→b|i,Bb|i),然后模拟者计算uiSampleDom(1n)以及Aa→b|iui,由于A1知道TB,在做完H询问后敌手A1可知Tb|i,而后计算viSamplePre(Bb|i,Tb|i,Aa→b|iui,si).最后,模拟者将(ida,idb,i,m,ui,vi,Aa→b|iui)存储于列表L5中,并将Aa→b|iui作为其Hash值H1(ida|idb|m|i)发送敌手A1.

5) ProxySignQueries.当敌手A1发送(ida,idb,i,m)作代理签名询问时,C所作回应为:

① 如果idb并非第l次委派询问,C在列表L5中查找(ida,idb,i,m),并将其对应的(ui,vi)作为代理签名发送给敌手A1.

② 如果idb刚好是第l次委派询问,当i*<i<T时,C在列表L5中查找(ida,idb,i,m),并将其对应的(ui,vi)作为代理签名发送给敌手A1;否则,则C终止计算.

6) BreakinQueries.当敌手A1发送(idb,j)作密钥更新询问时,C所作回应为:

① 如果idb并非第l次委派询问,C在列表L4中查找(Ta→b|j,Tb|j),并将其作为此时的签名私钥发送给敌手A1.

② 如果idb为第l次委派询问且j=i*,C终止计算.

Forgery:在这个阶段,敌手A1输出关于的签名(u*,v*).当签名满足3个条件时,我们称敌手A1伪造成功:

1) 1≤t*<j

未被用作委派询问;

未被用作代理签名询问,且签名验证者对签名的输出为“1”.

如果敌手A1输出伪造签名则模拟者C作如下操作:首先C检测是否为第l次询问且t*=i*是否成立.如果有一条不满足,C终止操作.否则,C就完成了完美模拟.在伪造签名之前,对于敌手对H1询问,C在列表中存储一组数据由Hash函数的原像最小熵可知,ut*的最小熵为ω(lb n).所以签名ut*u*的概率为(1-2-ω(lb n)).由于(u*,v*)为合法签名,必然成立.因而,u=u*-ut*满足Aa→b*|t*u=0所以,C可以输出u为调用阶段SIS问题的解.

如上所说,如果并非第l次询问或t*i*,C终止操作.所以,C能够解决SIS问题的概率与A1能输出伪造签名概率仅仅差一个系数1TQ.又由于解决格上SIS问题的概率几乎可忽略,所以敌手A1输出伪造签名的概率也必然为可忽略的.

证毕.

引理8. 假定格上的SIS问题在多项式时间算法攻击下是困难的,则以上格上的前向安全代理签名方案在类型2敌手攻击下是存在性不可伪造的.

证明. 假定存在一个多项式时间的敌手A2能够以不可忽略的概率攻破以上前向安全代理签名方案,那么我们可以构造1个模拟器C能够求解格上的SIS问题.假定被选中的身份为

调用:调用格上的SIS问题实例,模拟器C需要返还一个合法的解.

已知:矩阵Bb*|t*∈ZΛ(Bb*|t*)和实数

返回:任意向量v∈Zm,满足Bb*|t*v=0 mod q

首先,我们假设3个条件成立:

1) 对于每一个时间周期i=0,1,…,T-1,敌手A2可以适应性地对任意身份作多项式次H询问;

2) 对于任意的j<i,当敌手A2在时刻i对某一身份作H询问时,假设A2对该身份在时刻jH询问已经完成;

3) 在对任意签名人作签名私钥询问之前,假定A2已经预先完成相关的HH1询问.

Setup.C运行格基陷门生成算法TrapGen(1n)生成2组随机格和其陷门基,分别为Λ(A),Λ(B),TA∈ZZ满足A∈Z并公布矩阵AB.

Queries.当敌手A2伪造签名时,假设C随机选择i*(1≤i*T-1)作为伪造签名的时段.敌手A2可以适应性地作询问.

1) H-Oracle-Query.对于任意的时间i=0,1,…,T-1,A2可以适应性地对任意身份作H询问.

模拟者C维持一个列表L6={ida,idb,i,Ri}.输入身份和时间的一组数据(ida,idb,i),C首先在列表L6中查找(ida,idb,i).若(ida,idb,i)已存在在L6中,则模拟者C返还相应的Ri给敌手A2.否则,C从Dm×m中选择一个矩阵Ri并存储(ida,idb,i,Ri)在列表L6中.最后,模拟者C返还相应的Ri给敌手A2.

模拟者C维持一个列表输入身份和时间的一组数据(idb,i),C首先在列表L7中查找(idb,i).若(idb,i)已存在在L7中,则模拟者C返还相应的给敌手A1.否则,C从Dm×m中选择一个矩阵并存储在列表L7中.最后,模拟者C返还相应的给敌手A2.

2) DelegateQuery.模拟者C维持一个列表L8={ida,idb,0,Ta→b|0}.假定Q表示敌手能够做的委派询问的最大次数,敌手A2随机选择l∈{1,2,…,Q},C所作回应如下:

如果idb并非第l次委派询问,则C回应为:输入身份和时间列表(ida,idb,0),C首先查找列表L6找到其对应的Hash值R0并运行BasisDel(A,R0,TA,σ0)生成Ta→b|0.最后,模拟者C将(ida,idb,0,Ta→b|0)存储在列表L8中,并将Ta→b|0发送给A2.

如果idb刚好是第l次委派询问,则C终止操作.

3) KeyUpdateQueries.C维持列表L9={ida,idb,i,Aa→b|i,Ta→b|i,Bb|i,Tb|i}.当敌手A2发送(ida,idb,i)作签名私钥询问时,C所作回应如下.

如果idb并非第l次委派询问,则C回应为:对于任意的i∈[T-1],j<i,由引理8证明中的假设可知,在此之前,敌手A2已经完成对(ida,idb,j)和(idb,j)的H-Oracle-Query.当A2对(ida,idb,i)和(idb,i)作H-Oracle-Query时,C查找列表L6L7找出对应的然后,C运行算法BasisDel(Aa→b|i-1,Ri,Ta→b|i-1,σi)和分别生成Ta→b|iTb|i.最后,C将(ida,idb,i,Aa→b|i,Ta→b|i,Bb|i,Tb|i)存储至L9中,并将Ta→b|i返还给敌手.

如果idb刚好是第l次委派询问,则C回应为:

① 如果ii*,C随机选择2个矩阵W,X∈Z并将(ida,idb,i,Aa→b|i,W,Bb|i,X)存储在列表L9中.最后,C将W作为Ta→b|i返还给敌手A2.

② 如果i=i*+1,C运行2次TrapGen(1n)分别生成Aa→b|i*+1∈ZZBb|i*+1∈ZTb|i*+1∈Z最后C返还Ta→b|i*+1Tb|i*+1给敌手,并将数据(ida,idb,i*+1,Aa→b|i*+1,Ta→b|i*+1,Bb|i*+1,Tb|i*+1)存储在列表L9中.

③ 如果i*+1<i<T,模拟者C操作与idb并非第l次委派询问时一致.

4) H1-Oracle-Queries.C维持列表L10={ida,idb,i,m,ui,vi,Bb|ivi}.当敌手A2发送(ida,idb,i,m)作H1询问时,C所作回应为:如果L10列表中已经存在(ida,idb,i,m),则将其对应的Bb|ivi作为其Hash值H1(ida|idb|m|i)发送敌手;否则,C在列表L6L7L9中分别查找H(ida|idb|i),H(idb|i))和(ida|idb,i,Aa→b|i,Ta→b|i,Bb|i),然后模拟者采样可得viSampleDom(1n)并计算Bb|ivi.由于敌手A2知道TA,在做完H询问后敌手A2可知Ta→b|i,然后计算uiSamplePre(Aa→b|i,Ta→b|i,Bb|i,si),并将数据(ida,idb,i,m,ui,vi,Bb|ivi)存储于列表L10中.

5) ProxySignQueries.当敌手A2发送(ida,idb,i,m)作代理签名询问时,C所作回应为:

① 如果idb并非第l次委派询问,C在列表L10中查找(ida,idb,i,m),并将其对应的(ui,vi)作为代理签名发送给敌手A2.

② 如果idb刚好是第l次委派询问,当i*<i<T时,C在在列表L10中查找(ida,idb,i,m),并将其对应的(ui,vi)作为代理签名发送给敌手A2;否则,C终止计算.

6) BreakinQueries.当敌手A2发送(idb,j)作密钥更新询问时,C所作回应为:

① 如果idb并非第l次委派询问,C在列表L9中查找(Ta→b|j,Tb|j),并将其作为此时的签名私钥发送给敌手A2

② 如果idb为第l次委派询问且j=i*,C终止计算.

Forgery.在这个阶段,敌手A2输出关于的签名(u*,v*).当签名满足3个条件时,我们称敌手A2伪造成功:

1) 1≤t*<j

未被用作委派询问;

未被用作代理签名询问,且签名验证者对签名的输出为“1”.

如果敌手A1输出伪造签名则模拟者C的操作为:首先C检测是否为第l次询问且t*=i*是否成立.如果有一条不满足,C终止操作;否则,C就完成了完美模拟.在伪造签名之前,对于敌手对H1询问,C在列表中存储一组数据由Hash函数的原像最小熵可知,vt*的最小熵为ω(lb n).所以签名vt*v*的概率为1-2-ω(lb n).由于(u*,v*)为合法签名,等式必然成立.因而,向量v=v*-vt*必定满足Bb*|t*v=0和不等式所以,C可以输出v和为调用阶段SIS问题的解.

因此,如果并非第l次询问或t*i*,C终止操作.所以,C能够解决SIS问题的概率与A2能输出伪造签名概率仅仅差一个系数1TQ.又由于解决格上SIS问题的概率几乎可忽略,所以敌手A2输出伪造签名的概率也必然为可忽略的.

证毕.

由引理7和引理8可知,定理2必然成立.故而3.1节构造的前向安全的格基代理签名在随机预言机模型下是不可伪造的,且是前向安全的.

3.4 效率分析

本节我们从代理私钥尺寸和代理签名尺寸2个方面来比较格上的代理签名方案与之前签名方案的效率,如表1所示.其中,参数满足为小正整数,且0≤iT-1.

由表1容易看出,文献[14-15]中方案的代理私钥长度和代理签名长度明显比其他方案的相应长度短.这是由于采用了抛弃采样技术而非原像采样技术,而抛弃采样技术是提高格基签名效率的主要应用手段.本文提出的代理签名方案由于要实现前向安全性,故而采用了格基委派技术和原像采样算法技术(而非抛弃采样技术,若采用抛弃采样技术则无法逐级实现密钥更新),因而,相较于文献[13],私钥及签名长度会随着分级i增大而增加.

Table 1 The Efficiency Comparison of Different Schemes in Random Model

表1 随机模型下不同方案的效率比较

方案代理私钥长度代理签名长度前向安全文献[11]4m2lb(L·M·2m)2mlb(L·M2·2m)否文献[13]m2lb(L·M4·m3∕2)mlb(L·M5·m2)否文献[14]ml'lb(q)2mlb(12σ^)否文献[15]ml″ lb(q)mlb(12σ^)否本文方案2m2lb(L·M2(i+1)·mi+1∕2)2mlb(L·M2i+3·mi+1)是

4 标准模型下格基前向安全代理签名

4.1 方案描述

令素数qβ·ω(lb n),n为安全参数,那么格上的前向安全代理签名方案描述如下.

Setup.输入系统的安全参数n,KGC生成系统公共参数PP如下:T为预先指定的时间段数以及高斯参数(σ0,σ1,…,σT-1),(s0,s1,…,sT-1),其中为正整数.有2Tt1个随机矩阵满足其中,参数i,j满足0≤iT-1,1≤jt1.有t2个随机矩阵满足Fj∈Z其中1≤jt2.1个随机非零向量μ∈Z个Hash函数分别为H:{0,1}*→{0,1}t1H1:{0,1}*→{0,1}t2.

Keygen.输入公共参数PP,原始签名人Alice(身份为ida)和代理签名人Bob(身份为idb)分别运行引理2中的格基陷门生成算法TrapGen(1n)生成2组随机格和其陷门基,分别为Λ(A),Λ(B),TA∈ZZ满足A∈ZZ令格Λ(A)的光滑参数为η.

Delegate.为了将签名权利委派给代理人Bob,原始签名人Alice计算Hash值H(ida|idb|0)=ρ0和矩阵随后Alice运行引理6中的格基委派算法BasisDel(A,R0,TA,σ0)生成并输出作为Bob的代理签名密钥.

D-Verify.接收到密钥Ta→b|0后,Bob验证是否满足.若否,则返回至上一步,继续完成代理权利的委派.

KeyUpdate.输入(idb,i,Ta→b|i-1),其中i为当前时间,iT-1,以及之前的代理签名私钥Ta→b|i-1,Bob计算Hash值以及矩阵和矩阵Ra→b|i-1=以及矩阵随后Bob运行格基委派算法BasisDel(Aa→b|i-1,Ri,Ta→b|i-1,σi)和分别生成Ta→b|iTb|i作为当前时段的签名私钥.

ProxySign.输入签名消息m,Bob计算k=H1(ida|idb|m|i),以及矩阵F然后运行算法RandBasis(ExtBasis(Ta→b|i,Ai))和随机算法RandBasis(ExtBasis(Tb|i,Bi))分别生成Ti最后,Bob分别计算向量uiSamplePre(Ai,Ti,μ,si)和输出(ui,vi)作为当前时段对消息m的签名.

ProxyVerify.接收到签名之后,验证者首先计算向量k=H1(ida|idb|m|i),矩阵Ra→b|i=Ri,Ri-1,算法输出为“1”,当且仅当:

4.2 正确性

定理3. 以上格基前向安全代理签名满足正确性.

证明. 假设(ui,vi)为消息m的签名,由ProxySign可知向量uiSamplePre(Aa→b|i,Ta→b|i,si,μ)以及viSamplePre(Bb|i,Tb|i,si,μ).由引理3可知uivi分别服从分布DΛμ(Aa→b|i),siDΛμ(Bb|i),si.因而可得Aa→b|iui=μ mod qBb|iui=μ mod q.由KeyUpdate以及引理6可知:

故而可得由引理1可知故签名方案满足正确性.

证毕.

4.3 安全性分析

定理4. 假定格上的SIS问题在多项式时间算法攻击下是困难的,则以上格上的前向安全代理签名方案在标准模型下是存在性不可伪造的.

引理9. 假定格上的SIS问题在多项式时间算法攻击下是困难的,则以上格上的前向安全代理签名方案在类型1敌手攻击下是存在性不可伪造的.

证明. 假定存在一个多项式时间的敌手A1能够以不可忽略的概率ε攻破以上前向安全代理签名方案,那么我们可以构造一个模拟器C能够求解格上的SIS问题.假定被选中的身份为

调用:调用格上的SIS问题实例,模拟器C需要返还一个合法的解.

已知:矩阵Aa→b*|t*∈ZΛ(Aa→b*|t*)和实数

返回:任意向量u∈Zm,满足Aa→b*|t*u=0 mod q

Setup.首先,C运行格基陷门生成算法TrapGen(1n)生成一组随机格和其陷门基,为Λ(B),TB∈Z满足B∈Z其次,C选择一个随机矩阵随机选择一个矩阵A0∈Z.随后,挑战者C选择t2个随机矩阵E1,E2,…Et2∈Z其中所有矩阵Ej的每一列都随机独立地按照分布选取.对所有的j∈[t2],计算Fj=A0Ej.挑战者C随后选择T×t1个随机矩阵Ri,jDm×m(其中i∈{0,1,…,T-1},j∈[t1]).对于所有的j∈[t1],其余的公共参数选择为:

1) 对于i∈{0,1,…,T-1},令

2) 计算A=A0(R*iR*0).

3) 随机选择向量并计算μ=A0x0.如果μ=0(mod q),则重复本步骤直至μ为非零向量.

4) 对所有的时段i∈{0,1,…,T-1},计算矩阵并且定义A0,1=A1,2=…A1,t1=A1,1=A.

5) 运行SampleRwithBasis(Ai,j),生成1个矩阵RDm×m以及格Λ(Ai,jR-1)的1个小范数基T.

6) 存储项{i,j,R,Ai,jR-1,T}至列表L1,令

最后,C发送给敌手A1.

Queries.当敌手A1伪造签名时,假设C随机选择i*(1≤i*T-1)作为伪造签名的时段.敌手A1可以适应性地作询问.

1) DelegateQuery.模拟者C维持一个列表L2={ida,idb,0,Ta→b|0}.假定Q表示敌手能够做的委派询问的最大次数,敌手A1随机选择l∈{1,2,…,Q},C所作回应为:

如果idb并非第l次委派询问,挑战者C执行如下:

① 输入身份(ida,idb,0),挑战者C定义ρ0=H(ida|idb|0)然后计算

② 令j是满足的第1个位置,其中,j∈[t1].

③ 挑战者C在列表L1中找到对应项(0,j,R,AR-1,T).随后运行格基委派算法求得Ta→b|0.

④ 挑战者C将(ida,idb,0,Ta→b|0)存储至列表L2中,并将Ta→b|0返还给敌手A1.

如果idb刚好是第l次委派询问,则C终止操作.

2) KeyUpdateQueries.C维持列表L3={ida,idb,i,Aa→b|i,Ta→b|i,Bb|i,Tb|i}.当敌手A1发送(ida,idb,i)作签名私钥询问时,C所作回应如下.

如果idb并非第l次委派询问,则C回应为:

① 计算以及矩阵和矩阵Ra→b|i-1=以及矩阵

② 令j是满足的第1个位置,其中,j∈[t1].

③ 挑战者C在列表L1中找到对应项(i,j,R,Ai,jR-1,T).随后运行格基委派算法求得格基Ta→b|i.由于敌手A1为未被授权的代理签名人,故而知晓格Λ(B)的陷门基TB.随后,挑战者C运行格基委派算法生成Tb|i.

④ C将(ida,idb,i,Aa→b|i,Ta→b|i,Bb|i,Tb|i)存储至L3中,并将Ta→b|iTb|i返还给敌手.

如果idb刚好是第l次委派询问,则C回应为:

① 如果ii*,C随机选择2个矩阵W,X∈Z并将(ida,idb,i,Aa→b|i,W,Bb|i,X)存储在列表L3中.最后,C将WX分别作为Ta→b|iTb|i返还给敌手A1.

② 如果i=i*+1,C运行2次TrapGen(1n)分别生成Aa→b|i*+1∈ZZBb|i*+1∈ZZ最后C返还Ta→b|i*+1给敌手,并将数据(ida,idb,i*+1,Aa→b|i*+1,Ta→b|i*+1,Bb|i*+1Tb|i*+1)存储在列表L3中.

③ 如果i*+1<i<T,模拟者C操作与idb并非第l次委派询问时一致.

3) ProxySignQueries.挑战者C维持一个列表L4=(ida,idb,i,m,ui,vi).当敌手A1发送(ida,idb,i,m)作代理签名询问时,C作询问应答:

① 如果idb并非第l次委派询问,C首先在列表L3中查找其对应的(Ta→b|i,Tb|i).随后,C计算k=H1(ida|idb|m|i),以及矩阵然后,C运行算法RandBasis(ExtBasis(Ta→b|i,Ai))和随机算法RandBasis(ExtBasis(Tb|i,Bi))分别生成Ti最后,Bob分别计算向量uiSamplePre(Ai,Ti,μ,si)和输出(ui,vi)作为当前时段对消息m的代理签名,并将其发送给敌手A1.

② 如果idb刚好是第l次委派询问,挑战者C执行为:

Ⅰ.当i*<i<T时,C首先在列表L3中查找其对应的(Ta→b|i,Tb|i).随后,C计算选择1个随机向量并计算ui2=y-Ekui1(mod q),如果Ekui1=0,则重复以上步骤,直至Ekui10.令签名最后,C按照idb并非第l次委派询问时的情况计算并将其对应的(ui,vi)作为代理签名发送给敌手A1.

Ⅱ.如果i*i<T不成立,则C终止计算.

4) BreakinQueries.当敌手A1发送(idb,j)作密钥更新询问时,C所作回应为:如果idb并非第l次委派询问,C在列表L3中查找(Ta→b|j,Tb|j),并将其作为此时的签名私钥发送给敌手A1;如果idb为第l次委派询问且j=i*,C终止计算.

Forgery.在这个阶段,敌手A1输出关于的伪造签名(u*,v*).当签名满足3个条件时,我们称敌手A1伪造成功:

1) 1≤t*<j

未被用作委派询问;

未被用作代理签名询问,且签名验证者对签名的输出为“1”.

如果敌手A1输出伪造签名则模拟者C所作的操作为:首先C检测是否为第l次询问且t*=i*是否成立.如果有1条不满足,C终止操作.否则,C就完成了完美模拟.由于从未在签名询问阶段出现过,则我们知道u*是1个新向量满足y=A0x0,令向量满足由原像最小熵性质可知向量u满足Pr(u=0)≤negl(n).而下列不等式也必然成立.所以,令实数可以输出u为调用阶段SIS问题的解.

如上所说,如果并非第l次询问或t*i*,C终止操作,且Pr(u=0)≤negl(n).所以,C能够解决SIS问题的概率与A1能输出伪造签名概率为εTQ-negl(n).由于多项式时间内解决格上SIS问题的概率ε几乎可忽略,故敌手A1输出伪造签名概率必然可忽略,即满足不可伪造性和前向安全性.

证毕.

引理10. 假定格上的SIS问题在多项式时间算法攻击下是困难的,则以上格上的前向安全代理签名方案在类型2敌手攻击下是存在性不可伪造的.

证明. 假定存在一个多项式时间的敌手A2能够以不可忽略的概率ε攻破以上前向安全代理签名方案,那么我们可以构造一个模拟器C能够求解格上的SIS问题.假定被选中的身份为

调用:调用格上的SIS问题实例,模拟器C需要返还一个合法的解.

已知:矩阵Bb*|t*∈ZΛ(Bb*|t*)和实数

返回:任意向量v∈Zm,满足Bb*|t*v=0 mod q

Setup.首先,C运行格基陷门生成算法TrapGen(1n)生成一组随机格和其陷门基,为Λ(A),TA∈Z满足A∈Z其次,C选择一个随机矩阵随机选择一个矩阵B0∈Z.随后,挑战者C选择t2个随机矩阵E1,E2,…Et2∈Z其中所有矩阵Ej的每一列都随机独立地按照分布选取.对所有的j∈[t2],计算Fj=B0Ej.挑战者C随后选择T×t1个随机矩阵Ri,jDm×m(其中i∈{0,1,…,T-1},j∈[t1]).对于所有的j∈[t1],其余的公共参数选择为:

1) 对于时间段i∈{1,2,…,t2},令

2) 计算

3) 随机选择向量并计算μ=B0x0.如果μ=0(mod q),则重复本步骤直至μ为非零向量.

4) 对所有的时段i∈{0,1,…,T-1},计算矩阵并且定义B1,1=B.

5) 运行SampleRwithBasis(Bi,j),生成一个矩阵RDm×m以及格Λ(Bi,jR-1)的一个小范数基T.

6) 存储项{i,j,R,Bi,jR-1,T}至列表L1,令

最后,C发送给敌手A1.

Queries.当敌手A2伪造签名时,假设C随机选择i*(1≤i*T-1)作为伪造签名的时段.敌手A2可以适应性地作询问.

1) DelegateQuery.模拟者C维持一个列表L2={ida,idb,0,Ta→b|0}.假定Q表示敌手能够做的委派询问的最大次数,敌手A2随机选择l∈{1,2,…,Q},C所作回应:

如果idb并非第l次委派询问,挑战者C执行如下.

① 输入身份(ida,idb,0),C定义ρ0=H(ida|idb|0)然后计算

② 由于敌手为恶意的原始签名人,故而知晓TA.挑战者C运行引理6中的格基委派算法BasisDel(A,R0,TA,σ0)生成并输出Ta→b|0=[t1t2‖…‖tm]运行格基委派算法T,σ0)求得Ta→b|0.

③ 挑战者C将(ida,idb,0,Ta→b|0)存储至列表L2中,并将Ta→b|0返还给敌手A2.

如果idb刚好是第l次委派询问,则C终止操作.

2) KeyUpdateQueries.C维持列表L3={ida,idb i,Aa→b|i,Ta→b|i,Bb|i,Tb|i}.当敌手A1发送(ida,idb,i)作签名私钥询问时,C所作回应.

如果idb并非第l次委派询问,则C回应.

① 计算以及矩阵和矩阵以及矩阵

② 令j是满足的第1个位置,其中,j∈[t1].

③ 挑战者C在列表L1中找到对应项(i,j,R,Bi,jR-1,T).随后运行格基委派算法求得格基Tb|i.由于敌手A2为恶意的原始签名人,故而知晓格Λ(A)的陷门基TA.随后,挑战者C运行格基委派算法BasisDel(Aa→b|i-1,Ri,Ta→b|i-1,σi)生成Ta→b|i.

④ C将(ida,idb,i,Aa→b|i,Ta→b|i,Bb|i,Tb|i)存储至L3中,并将Ta→b|iTb|i返还给敌手.

如果idb刚好是第l次委派询问,则C回应:

① 如果ii*,C随机选择2个矩阵W,X∈Z并将(ida,idb,i,Aa→b|i,W,Bb|i,X)存储在列表L3中.最后,C将WX分别作为Ta→b|iTb|i返还给敌手A2.

② 如果i=i*+1,C运行2次TrapGen(1n)分别生成Aa→b|i*+1∈ZZBb|i*+1∈ZZ最后C返还Ta→b|i*+1给敌手,并将数据(ida,idb,i*+1,Aa→b|i*+1,Ta→b|i*+1,Bb|i*+1Tb|i*+1)存储在列表L3中.

③ 如果i*+1<i<T,模拟者C操作与idb并非第l次委派询问时一致.

3) ProxySignQueries.挑战者C维持1个列表L4=(ida,idb,i,m,ui,vi).当敌手A1发送(ida,idb,i,m)作代理签名询问时,C按照如下方式作询问应答:

如果idb并非第l次委派询问,挑战者C执行如下:

① C首先在列表L3中查找其对应的(Ta→b|i,Tb|i).

② C计算k=H1(ida|idb|m|i),以及矩阵

③ C运行算法RandBasis(ExtBasis(Ta→b|i,Ai))和随机算法RandBasis(ExtBasis(Tb|i,Bi))分别生成Ti

④ Bob分别计算向量uiSamplePre(Ai,Ti,μ,si)和输出(ui,vi)作为当前时段对消息m的代理签名,并将其发送给敌手A2.

如果idb刚好是第l次委派询问,挑战者C执行为:

① 当i*<i<T时,C首先在列表L3中查找其对应的(Ta→b|i,Tb|i).随后,C计算选择一个随机向量并计算vi2=y-Ekvi1(mod q),如果Ekui1=0,则重复以上步骤,直至Ekvi10.令签名最后,C按照idb并非第l次委派询问时的情况计算uiSamplePre(Bi,并将其对应的(ui,vi)作为代理签名发送给敌手A2.

② 如果i*i<T不成立,则C终止计算.

4) BreakinQueries.当敌手A1发送(idb,j)作密钥更新询问时,C所作回应如下:如果idb并非第l次委派询问,C在列表L3中查找(Ta→b|j,Tb|j),并将其作为此时的签名私钥发送给敌手A1;如果idb为第l次委派询问且j=i*,C终止计算.

Forgery.在这个阶段,敌手A1输出关于的伪造签名(u*,v*).当签名满足3个条件时,我们称敌手A1伪造成功:

1) 1≤t*<j

未被用作委派询问;

未被用作代理签名询问,且签名验证者对签名的输出为“1”.

如果敌手A1输出伪造签名则模拟者C作如下操作:首先C检测是否为第l次询问且t*=i*是否成立.如果有1条不满足,C终止操作.否则,C就完成了完美模拟.由于从未在签名询问阶段出现过,则我们知道v*是1个新向量满足y=B0x0,令向量满足由原像最小熵性质可知向量v满足Pr[v=0]≤negl(n).而以下不等式也必然成立.所以,令实数可以输出v为调用阶段SIS问题的解.

如果并非第l次询问或t*i*,C终止操作,且Pr(v=0)≤negl(n).所以,A能输出伪造签名概率为εTQ-negl(n).由于在多项式时间内解决格上SIS问题的概率ε几乎可忽略,所以敌手A输出伪造签名概率也可忽略,故而,签名方案不可伪造且前向安全.

证毕.

由引理9和引理10可知,定理4必然成立.故而4.1节构造的前向安全的格基代理签名在标准模型下满足不可伪造性和前向安全性.

5 总 结

鉴于其众多的应用场景,前向安全代理签名自提出以来就受到了广泛的关注.然而,随着量子计算机的出现,基于传统数论问题——大整数分解和离散对数的前向安全代理签名方案在量子计算环境下已不再安全.因此,如何构造量子免疫的前向安全代理签名是后量子时代迫切需要解决的问题.

由于具备量子免疫性,计算简单高效,任意实例下的安全性和最坏实例下的安全性相当等诸多优势,格公钥密码成为后量子时代公钥密码的最佳选择.本文基于格基困难问题——SIS问题提出了2个前向安全代理签名方案.第1个签名方案是在随机预言机模型中被证明是不可伪造的;第2个签名方案则是在标准模型中被证明是安全的.为了进一步丰富格基签名的应用场景,在后续的工作中,我们将逐步关注具有特殊性质的前向安全代理签名,构造格上安全的前向安全盲代理签名、前向安全多级代理签名,将成为我们今后的工作重心.

参考文献

[1]Mambo M, Usuda K, Okamoto K. Proxy signatures: Delegation of the power to sign messages[J]. IEICE Transactions on Fundamentals, 1996, E79-A(9): 1338-1354

[2]Kim H, Baek J, Lee B, et al. Secret computation with secrets for mobile agent using one-time proxy signature[C] Proc of the 2001 Symp on Cryptography and Information Security. Tokyo: IEICE, 2001: 845-850

[3]Lee B, Kim H, Kim K. Strong proxy signature and its applications[C] Proc of the 2001 Symp on Cryptography and Information Security. Tokyo: IEICE, 2001: 603-608

[4]Leiwo J, Hanle C, Homburg P,et al. Disallowing unauthorized state changes of distributed shared objects[G] IFIPAICT 47: Proc of IFIP TC11 16th Annual Working Conf on Information Security. Berlin: Springer, 2000: 381-390

[5]Park H U, Lee I Y. A digital nominative proxy signature scheme for mobile communications[G] LNCS 2229: Proc of the 3rd Int Conf of Information and Communications Security. Berlin: Springer, 2001: 451-455

[6]Li Lihua, Tzeng Shiangfeng, Hwang Minshiang. Generalization of proxy signature-based on discrete logarithms[J]. Computers and Security, 2003, 22(3): 245-255

[7]Hwang Shinjia, Chen Chiuchiu. Cryptanalysis of nonrepudiable threshold proxy signature schemes with known signers[J]. Informatica, 2003, 14(2): 205-212

[8]Shao Zuhua. Proxy signature schemes based on factoring[J]. Information Processing Letters, 2003, 85(3): 137-143

[9]Zhou Yuan, Cao Zhenfu, Lu Rongxing. Provably secure proxy-protected signature schemes based on factoring[J]. Applied Mathematics Computation, 2005, 164(1): 83-98

[10]Jiang Yali, Kong Fanyu, Ju Xiuling. Lattice-based proxy signature[C] Proc of Int Conf on Computational Intelligence and Security 2010. Piscataway, NJ: IEEE, 2010: 382-385

[11]Xia Feng, Yang Bo, Ma Sha, et al. Lattice-based proxy signature scheme[J]. Journal of Hunan University: Natural Sciences, 2011, 38(6): 84-88 (in Chinese)(夏峰, 杨波, 马莎, 等. 基于格的代理签名方案[J]. 湖南大学学报: 自然科学版, 2011, 38(6): 84-88)

[12]Wang Chunxiao, Qi Mingnan. Lattice-based proxy signature scheme[J]. Journal of Information and Computational Science, 2011, 12(8): 2451-2458

[13]Kim K S, Hong D, Jeong I R. Identity-based proxy signature from lattices[J]. Journal of Communications and Networks, 2013, 15(1): 1-7

[14]Jiang Mingming, Hu Yupu, Wang Baocang, et al. Efficient lattice-based proxy signature[J]. Journal of Beijing University of Posts and Telecommunications, 2014, 37(3): 89-92 (in Chinese)(江明明, 胡予濮, 王保仓, 等. 格上的高效代理签名[J]. 北京邮电大学学报, 2014, 37(3): 89-92)

[15]Wu Fangguo, Yao Wang, Zhang Xiao,et al. An efficient lattice-based proxy signature with message recovery[G] LNCS 10656: Proc of SpaCCS 2017. Berlin: Springer, 2017: 321-331

[16]Fan Xiong, Liu Fenghao. Proxy re-encryption and re-signatures from lattices[G] LNCS 11464: Proc of ACNS 2019. Berlin: Springer, 2019: 363-382

[17]Anderson R. Two remarks on public key cryptology[EBOL]. [2020-11-18]. http:www.cl.cam.ac.ukusersrja14

[18]Bellare M, Miner S. A forward-secure digital signature scheme[G] LNCS 1666: Proc of Cryptology-CRYPTO’99. Berlin: Springer, 1999: 431-448

[19]Itkis G, Reyzin L. Forward-secure signatures with optimal signing and verifying[G] LNCS 2139: Proc of Cryptology-CRYPTO 2001. Berlin: Springer, 2001: 499-514

[20]Kozlov A, Reyzin L. Forward-secure signatures with fast key update[G] LNCS 2576: Proc of Security in Communication Networks 2002. Berlin: Springer, 2002: 247-262

[21]Malkin T, Micciancio D, Miner S. Efficient generic forward-secure signatures with an unbounded number of time periods[G] LNCS 2332: Proc of Cryptology-EUROCRYPT 2002. Berlin: Springer, 2002: 400-417

[22]Zhang Xiangsong, Liu Zhenhua. Lattice-based strongly-unforgeable forward-secure identity-based signature scheme with flexible key update[J]. KSII Transactions on Internet and Information Systems, 2017, 11(5): 2792-2810

[23]Ko H, Jeong G, Kim J, et al. Forward secure identity-based signature scheme with RSA[G] IFIPAICT 562: Proc of Int Conf on ICT Systems Security and Privacy Protection 2019(SEC 2019). Berlin: Springer, 2019: 314-327

[24]Swati K, Tabassum M. Forward secure ID based ring signature for data sharing[J]. International Journal of Advance Research, Ideas and Innovations in Technology, 2019, 5(2): 26-30

[25]Abdalla M, Miner S, Namprempre C. Forward-secure threshold signature schemes[G] LNCS 2020: Proc of the Cryptographers’ Track at RSA Conf 2001(CT-RSA 2001). Berlin: Springer, 2001: 441-456

[26]Yu Ju, Kong Fanyu. Forward secure threshold signature scheme from bilinear pairings[G] LNCS 4456: Proc of Int Conf of Computational Intelligence and Security 2006(CIS 2006). Berlin: Springer, 2006: 587-597

[27]Wang Xiaoming, Chen Huoyan, Fu Fangwei. A forward secure proxy signature[J]. Journal on Communications, 2005, 26(11): 38-42 (in Chinese)(王晓明, 陈火炎, 符方伟. 前向安全的代理签名方案[J]. 通信学报, 2005, 26(11): 38-42)

[28]Tan Zuowen, Liu Zhuojun. A forward secure strong proxy signature[J]. Information and Electronic Engineering, 2003, 1(4): 257-259 (in Chinese)(谭作文, 刘卓军. 一个前向安全的强代理签名方案[J]. 信息与电子工程, 2003, 1(4): 257-259)

[29]Wang Liang, Jia Xiaozhu. Forward-secure proxy signature scheme based on discrete logarithm[J]. Journal of Qingdao University: Natural Science Edition, 2007, 20(2): 46-49 (in Chinese)(王亮, 贾小珠. 基于离散对数的前向安全代理签名方案[J]. 青岛大学学报: 自然科学版, 2007, 20(2): 46-49)

[30]Alomair B, Sampigethaya K, Poovendran R. Efficient generic forward-secure signatures and proxy signatures[G] LNCS 5057: Proc of the 5th European PKI Workshop: Theory and Practice(EuroPKI 2008). Berlin: Springer, 2008: 166-181

[31]He Jun, Li Ximei, Li Lijuan, et al. A new forward-secure proxy signature scheme[G] Proc of the 2010 Int Forum on Information Technology and Applications.Piscataway, NJ: IEEE, 2010: 30-33

[32]Sunitha N R, Amberker B B. Forward-secure proxy signature scheme for multiple proxy signers using DSA with proxy revocation[G] Proc of the 2009 IEEE Int Advance Computing Conf(IACC2009). Piscataway, NJ: IEEE, 2009: 681-686

[33]Song D X D. Practical forward secure group signature schemes[G] Proc of the 8th ACM Conf on Computer and Communications Security(CCS2001). New York: ACM, 2001: 225-234

[34]Zhang Jianhong, Wu Qianhong, Wang Yumin. A novel efficient group signature scheme with forward security[G] LNCS 2836: Proc of the 5th Int Conf of Information and Communications Security(ICICS 2003). Berlin: Springer, 2003: 292-300

[35]Zhou Xuanwu, Yang Xiaoyuan, Wei Ping, et al. Dynamic group signature with forward security and its application[G] Proc of the 6th Int Conf on Grid and Cooperative Computing(GCC2007). Piscataway, NJ: IEEE, 2007: 473-480

[36]Meenakshi K, Ratna D, Sourav M. Forward secure efficient group signature in dynamic setting using lattices[EBOL]. [2020-10-30]. https:eprint.iacr.org2017112820190107:173023

[37]Ling San, Nguyen K, Wang Huaxiong, et al. Forward-secure group signatures from lattices[G] LNCS 11505: Proc of Int Conf on Post-Quantum Cryptography 2019(PQCrypto 2019). Berlin: Springer, 2019: 44-64

[38]Ma D, Tsudik G. Extended sbstract: Forward-secure sequential aggregate authentication[G] Proc of the 2007 IEEE Symp on Security and Privacy(SP 2007). Piscataway, NJ: IEEE, 2007: 86-91

[39]Shor P W. Polynomial-time algorithm for prime factorization and discrete logarithm on a quantum computer[J]. SIAM Journal on Computing, 1997, 26(5): 1484-1509

[40]Micciancio D, Regev O. Worst-case to average-case reductions based on Gaussian measures[J]. Society for Industrial and Applied Mathematics(SIAM) Journal on Computing, 2007, 37(1): 267-302

[41]Alweny J, Peikertz C. Generating shorter bases for hard random lattices[J]. Theory of Computing Systems, 2009, 48(3): 535-553

[42]Gentry C, Peikert C, Vaikuntanathan V. Trapdoors for hard lattices and new cryptographic constructions[G] Proc of the 40th Annual ACM Symp on Theory of Computing. New York: ACM, 2008: 197-206

[43]Cash D, Hoflieinz D, Kiltz E, et al. Bonsai trees, or how to delegate a lattice basis[G] LNCS 6110: Proc of the 29th Annual Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2010: 523-552

[44]Agrawal S, Boneh D, Boyen X. Lattice basis delegation in fixed dimension and shorter-ciphertext hierarchical IBE[G] LNCS 6223: Proc of the 30th Annual Cryptology Conf. Berlin: Springer, 2010: 98-115

Xie Jia, born in 1990. PhD, lecturer. Her main research interests include lattice public key cryptography and quantum computation and quantum attack.

谢 佳,1990年生.博士,讲师.主要研究方向为格公钥密码、量子计算、量子攻击.

Hu Yupu, born in 1955. PhD, professor. His main research interests include multilinear map and public key cryptography.

胡予濮,1955年生.博士,教授.主要研究方向为多线性映射、公钥密码.

Jiang Mingming born in 1985. PhD, associate professor. His main research interests include lattice public key cryptography.

江明明,1985年生.博士,副教授.主要研究方向为格公钥密码.