基于格的代理签名方案

摘 要：利用原像采样单向陷门函数和盆景树下格的扩展及格基的随机化方法，基于格构造了一个代理签名方案.在随机预言机下，基于平均情况的小整数解问题SIS(Small Integer Solution)和非均匀小整数解问题ISIS(Inhomogeneous Small Integer Solution)的困难性假设，证明该方案在适应性选择消息攻击下是安全的.与基于数论假设方案相比，该方案密钥空间较大，但计算效率更高.

关键词：格；随机预言机；代理签名；原像采样

中图分类号：TP309 文献标识码：A

Lattice-based Proxy Signature Scheme

XIA Feng1,2, YANG Bo1, MA Sha1, SUN Wei-wei1 , ZHANG Ming-wu1

( 1. College of Informatics, South China Agricultural Univ, Guangzhou, Guangdong 510642，China;

2. School of Information Science and Technology, Hainan Normal Univ, Haikou, Hainan 571158, China)

Abstract:By using trapdoor functions with preimage sampling, lattice"s growth, and lattice basis randomization in the bonsai tree, a lattice-based proxy signature scheme was proposed. The security of the proxy signature is based on the hardness of average-case SIS (Small Integer Solution) and ISIS (Inhomogeneous Small Integer Solution). It is also existential unforgeability under adaptive chosen-message attack in the random oracle. Compared with the schemes based on factoring or discrete log, the public and secret keys of our scheme are larger, but it requires only linear operation on small integers.

Key words:lattice; random oracle;proxy signature;preimage sampling



为高效、安全地实现数字签名的委托，1996年，Mambo等[1]提出了代理签名的概念.此后，代理签名体制得到了广泛、深入的研究，出现了许多基于大整数分解和离散对数问题的代理签名方案，并且，这种签名机制已被广泛地应用到网格计算、电子交易、移动通信和移动代理等环境.然而，若量子计算机得到应用，基于数论假设的大整数分解问题和离散对数问题都可在多项式时间内得到解决[2]，大量基于数论假设的代理签名方案将不再安全.因此，设计能抵抗量子攻击的代理签名方案成为该领域需解决的问题.近年来，基于格构造新型密码系统因具有较高的渐近效率、运算简单（通常只需要线性运算）、能抵抗量子攻击和存在最坏情况下的随机实例等特点，成为公钥密码领域的研究热点，并取得了一系列的研究成果[3-7].本文基于格中平均情况下SIS和ISIS问题的困难性假设，利用带原像采样的单向陷门函数和盆景树下格的扩展及格基的随机化方法，基于格构造了一个高效、安全的代理签名方案.

1 预备知识

1.1 符号说明

本文中，R表示实数集，Z表示整数集.用加粗的小写字母表示列向量，例如x，x的第i个元素表示成xi.矩阵用加粗的大写字母表示，例如X，X的第i列向量表示成xi.向量x的长度用欧几里德范数‖x‖表示，‖X‖=maxi‖xi‖.一个n维格表示成Λ=L(B)=Bc:c∈Zk,B∈Rn×k，B是格的基，基中k列向量b1,…,bk∈Rn是线性独立的，k为Λ的秩.格Λ中的最短距离λ1(Λ)指的是格中最短非零向量的长度，即λ1(Λ)=min0≠x∈Λ‖x‖.Λ的对偶格Λ*定义为：

Λ*=x∈span(Λ):v∈Λ,∈Z，span(Λ)表示格Λ张成的空间.设A∈Zn×mq，则由A定义下面2个重要的格：

Λ(A,q)=y∈Zm:y=As mod q，s∈Zn,

Λ⊥(A,q)=e∈Zm:Ae=0 mod q.

对于任意包含k个线性独立向量的集合S=s1,…,sk∈Rm，=1,…,k代表它的格莱姆施密特正交向量集，即1=s1，对每一个i=2,…,k，i是si的投影，该投影与span(s1,…,si－1)正交.

文中的安全参数为n.若f(n)=O(g(n)•log cn)，则表示成f(n)=(g(n))，c为一常数.poly(n)代表一个未确定的多项式阶函数f(n)=O(nc).

1.2 格上的困难问题

定义1 判定性的最短距离问题GapSVPr(Shortest Vector Problem)：给定一对输入(B,d)，B是格Λ的基，d∈R，回答λ1(L(B))≤d成立或λ1(L(B))>γ(n)d不成立.

定义2最短独立向量问题SIVP(Shortest Independent Vectors Problem)：输入格Λ的基B，输出n个线性独立的向量SL(B)，使得‖S‖≤γ(n)λ1(L(B)).

定义1和定义2中，γ(n)是逼近因子，它是n的函数.当γ(n)取1时，在最坏情况(worst-case)下是NP困难问题；当γ(n)为n的多项式时，在最坏情况下是密码学上的困难问题[8].

定义3 小整数解问题（SIS）：给定整数q，矩阵A∈Zn×mq，实数β，找到非零向量e∈Zm，使得Ae=0mod q，并且‖e‖≤β.

定义4非均匀的小整数解问题（ISIS）：给定整数q，矩阵A∈Zn×mq，实数β，找到非零向量e∈Zm，使得Ae=umod q，并且‖e‖≤β.

定义3和定义4中，若A，u为均匀随机选取的，则称SISq,m,β和ISISq,m,β为平均情况问题（average-case problem）.定理1说明了平均情况的SISq,m,β和ISISq,m,β也是NP困难问题.

定理1[9] 对于一个多项式有界的m，β=poly(n)和任意素数q=βω(nlog n)，平均情况问题SISq,m,β和ISISq,m,β与最坏情况问题GapSVPr和SIVP同样困难，其中，γ(n)=β(n).ω(nlog n)为超级对数，即ω(nlog n)比nlog n随着n增长得更快.

1.3格上的高斯分布

对于任意s>0，定义以向量c为中心，参数为s的高斯分布为：

x∈Rn,ρs,c=exp (－π‖x－c‖2/s2).（1）

格上的离散高斯分布为：

x∈Λ,DΛ,s,c(x)=ρs,c(x)ρs,c(Λ).（2）

式（1），式（2）中，若s，c分别是1和0，在书写时则可省略.离散高斯分布是一个条件分布函数，是由对格中的元素按高斯分布取样所获得的分布.

高斯分布格点范围的大小主要由s来决定，当s的取值满足一定条件时，则在离散高斯分布中采样输出格点的分布及长度会有一些比较好的性质，下面的定义给出与s相关的平滑参数的定义.

定义5[9] 平滑参数(The smoothing parameter).设任意一个n维格Λ和ε>0，定义平滑参数ηε(Λ)为最小的s>0，使得ρ1/s(Λ*＼{0})≤ε.

当s≥ηε(Λ)时，定理2给出了对离散高斯分布中的向量进行采样时获得向量概率的最大上界.

定理 2[3] 对于任意秩为k的n维格Λ，c∈Rn，正数ε

DΛ,s,c(x)≤1+ε1－ε•2－k.

特别地，DΛ,s,c(x)的最小熵为k－1.

1.4 采样算法和原像采样单向陷门函数

文献[3]给出了运行时间约为格基长度的O(n2)的采样算法SampleD(B,s,c)，通过该采样算法获得的向量满足下面的定理.

定理 3[3] 对于任意格Λ的基B∈Zn×k，实数s≥‖B‖ω(log n)和c∈Rn，Sample D(B,s,c）的输出分布与DΛ,s,c(x)在统计上是不可区分的.其运行时间约为(B,s,c)长度的O(n2).

定理4描述若以格的离散高斯分布上采样所得的格点作为输入，则其与随机均匀选取的矩阵向量积在该矩阵所生成的向量空间上也是均匀分布的.

定理 4[3]设n和q为正整数且q为素数，令m≥2nlg q，对于所有的A∈Zn×mq，s≥ω(log m)和e←DZm,s，则以压倒性的概率，u=Aemod q在Znq上是统计均匀分布的.

基于平均情况问题SIS和ISIS，文献[3]构造了一个单向陷门函数，在描述该函数之前，我们给出下面定理.

定理 5[10] 给定任意素数q=poly(n)和任意m≥5nlg q，存在一个概率多项式算法，输入1n，输出矩阵A∈Zn×mq和一个满秩的集合SΛ⊥(A,q)，A在Zn×mq上是统计均匀分布的，并且‖S‖≤L=m2.5.

在文献[3]中，Gentry等人将L优化到m1+ε.在s≥Lω(log m)时，基于平均情况问题SIS和ISIS的单向陷门函数，简单描述如下[3]：

1）按定理5生成（A,S).其中，A为公钥，S为私钥.

2）函数fA定义为fA(e)=Ae(modq)，定义域为Dn=e∈Zm:‖e‖≤sm，值域为Rn=Znq.e的输入分布满足DZm,s.

3）单向陷门求逆算法SampleISIS(A,S，s，u）求得f－1A(u)如下：先计算t∈Zm，然后利用高斯采样算法用私钥S采样出v←DΛ⊥,s,－t，输出e=v+t.e即为u在给定定义域的原像.

定理6[3]算法SampleISIS(A,S，s，u）若是单向的，则平均情况ISISq,m,sm是困难的.而且若fA(e)=Ae(modq)是抗原像采样碰撞攻击的，则平均情况SISq,m,2sm是困难的.

1.5 格的扩展和格基的随机化操作

在2010年的欧密会上，David Cash等[11]把盆景树的思想引入到格中，给出了对格进行扩展（使其秩增加）和对基进行随机化操作的具体方法.下面给出本文中要用到的有关定理和定义.

定理 7[12] 每一个格ΛZm都可用埃尔米特插值标准形式(Hermite normal form)唯一地表示出来，它可用给定格的任意基B高效地计算出来，写成HNF(B).

定理 8[11]存在一个确定性的多项式算法ToBasis(S,B)，给定满秩格的子集SΛ=L(B)，输出一个基T并使得‖i‖≤‖i‖.

定理 9[11]设SZm×m为格Λ⊥(A)的任意基，其中，A∈Zn×mq生成全部的Znq，设∈Zn× q为任意的，则存在一个确定性的多项式算法ExtBasis(S,=A‖)，输出Λ⊥()的基Zm+，使得‖‖=‖S‖，而且，该定理对于任意改变顺序的都成立.

定理10[11]存在一个概率多项式算法RandBasis(S,s)，对于任意n维整数格Λ的基S和参数s≥‖‖ω(logn)，输出Λ的基SR，且‖SR‖≤sm.对于同一个格的不同基S0,S1，设s≥max ‖0‖,‖1‖ω(logn)，则RandBasis(S0,s)的输出和RandBasis(S1,s)的输出不可区分.

定理10说明了SR和S相互独立，即由SR得不到任何S的特定信息，通过该定理，可有效地实现格基的委托，即把原来的基随机化之后，得到新的基，且从新的基无法推导出原来的基.该定理主要用到定理7和定理8的结果.

2 基于格的代理签名方案

所描述的代理签名方案中，各参数的取值范围为： q=poly(n)，m≥5nlg q，s=Lω(logm)，sδ=sm+，s′=Lω(log (m+)，eδ∈Zm+q且‖eδ‖≤sδm+， e′∈Zm+q且‖e′‖≤s′m+，L=m2.5.显然，上述参数可使定理1成立，即确保平均情况下SIS和ISIS问题是困难的，同时也满足定理5的要求，有效地生成单向陷门函数.方案中用到的H()：{0,1}*→Zm+q是一个抗碰撞的杂凑函数.

2.1 方案描述

定义6基于格的代理签名方案(LatticeProSig)包括系统密钥生成（SigKeyGen）、代理密钥生成（ProSigkeyGen）、代理签名(ProSig)和签名验证(Ver)4个算法，具体描述如下.

SigKeyGen(1n)：原始签名者按定理5描述的方法生成(Α′,S′)，A′∈Zn×mq，S′Λ⊥(A′,q).Α′为该签名者的公钥，S′为其私钥.同样，代理签名者生成公私钥对(Α″,S″)，A″∈Zn×(m+)q，S″Λ⊥(A″,q).

ProSigKeyGen(A′,S′,)：原始签名者随机选取∈Zn×q，用算法ExtBasis(S′,Aδ=A′‖)生成Αδ,S)，其中，S是格Λ⊥(Aδ)的基；然后，用算法RandBasis(S,s)生成Sδ，Sδ即为代理密钥.

ProSig(M,Aδ,Sδ,A″,S″)：对于消息M∈{0,1}*，代理签名者先计算u=H(M)，用SampleISIS(Aδ,Sδ,s,u）求得eδ，然后用SampleISIS(A″,S″,s,u）采样算法求得e′.输出(M,A,,A′,eδ,e′).

Ver(M,A,,A′,eδ,e′）：收到签名后，验证者进行下面操作：

1) 验证eδ,e′是否在所定义的范围内，若不是，则拒绝，否则，转2);

2) 计算u=H(M)，验证u=(A′‖)eδ是否成立，若不成立，则拒绝，否则，转3);

3)验证u=A″e′是否成立，若成立，接受，否则，拒绝.

2.2安全性证明

定理11 若平均情况的SISq,m,2s′m+是困难的，则代理签名方案LatticeProSig在适应性选择消息攻击下是不可伪造的.

对该定理的证明分为3个部分：首先证明代理密钥不泄露原始签名者私钥的任何信息，而且，不知道原始签名者私钥，任何人无法伪造代理密钥；其次证明任何不知道代理密钥的第3方无法伪造代理签名；最后证明不知道代理签名的私钥者无法冒充该代理人伪造代理签名.

证 先证明第1部分：在用算法RandBasis(S，s)生成Sδ时，根据定理10，这是一个随机化的操作，生成的Sδ与S相互独立，从Sδ得不到任何关于S的特定信息，从而，无法从Sδ求出S，进一步，也无法求出S′.相反，因为A′和都是均匀随机选取的，所以A′‖也是均匀随机的，在给定A′‖时，假设一个敌手在不知道原始签名者的私钥S′时，能伪造代理密钥Sδ，则他可通过采样算法SampleD(S,sδ,0)获取eδ，使得(A′‖)eδ=0(mod q)，这样，他就解决了在‖eδ‖≤β=sδm+下的平均情况SISq,m+,β问题，这与定理1矛盾.因此，在不知道原始签名者的私钥时，敌手无法伪造代理密钥.第1部分得证.

第2部分是证明H(M)=(A′‖)eδ的安全性，我们将基于随机预言机模型证明它能抗击适应性选择消息攻击.证明方法与文献[3]提出的证明方法类似，证明如下：

假设存在一个敌手AI能伪造代理签名，则存在一个多项式时间算法SI能找到关于H()的一对碰撞.

H()询问：对AI每一个不同的M∈0,1*，SI先查找本地存储是否有(M,eδ)，若有，则返回H(M)=(A‖)eδ，否则用采样算法SampleD(S,sδ,0)随机获取eδ，计算H(M)=(A‖)eδ，并将其返回给AI，并保留(M,eδ).

签名询问：当AI询问M的签名时，SI查表(M,eδ)，并将eδ做为M的签名返回给AI.

最终，AI将伪造出一对有效的签名(M*,eM)，因为AI在伪造签名时必须要对M*进行H()询问，从而，SI在本地保留(M*,e*δ），根据定理4，eδ←SampleD(S,sδ,0)有均匀输出的特性，根据定理2，在随机均匀地给定H()的情况下，e*δ发生的概率最大值为2－(m+)(1+ε/（1－ε）)，对于足够大的m+和足够小的ε，eM=e*δ的概率可以忽略，所以有eM≠e*δ.从而，SI找到了eM≠e*δ，使得(A‖)e*m=(A‖)em*，即找到e=e*m－em*≠0，使得(A‖)e=0，这与SISq,m,2s′m+是困难的相矛盾.第2部分得证.

第3部分是证明u=A″e′的安全性.这部分证明与第2部分证明类似，在这里不做详细描述.

证毕.

若同一个原始签名者要选择多个代理人，可选择不同的（列数相同），并分别生成不同的代理密钥，定理12说明这并不影响代理签名的安全性.

定理12 同一个原始签名人的不同代理者无法从自己的代理密钥推导出其他代理者的密钥.

证 设代理者P1的代理密钥为Sδ1Λ⊥(A′‖1,q)(A‖1∈Zn×(m+)q,‖Sδ1‖≤L)，选择任意的R∈Zn×q），假设P1能推导出SδRΛ⊥(A′‖R,q), ‖SδR‖≤L，现在固定A′‖R中的R，将A′分成两部分，即A′=A1‖A2（A2与R列数相同），将A2用任意其他矩阵L∈Zn×q替代，P1同样能推导出SRΛ⊥(A1‖L‖R,q)，若干轮后，P1可获得任意的SΛ⊥(AR,q)（AR∈Zn×(m+)q, ‖S‖≤L），这就意味着P1可用SampleD(S,s,0)获得eR，使得AReR=0 modq, ‖e‖≤sm+，这与定理1矛盾.

证毕.

由以上证明可知，完全可将代理者信息用杂凑函数计算后陷入到中而并不影响签名的安全性.

2.3 效率分析

该代理签名方案的效率主要取决于代理签名和签名验证部分的效率，密钥的长度约为O(n2)，采样算法所需运行的时间约为输入参数长度的O(n2)，验证eδ，e′范围所需的时间为O(n).此外，还需要做2个杂凑函数的运算和2个向量的线性运算即可.在效率上，与基于数论的代理签名方案相比，其缺点是密钥长度比效大，但不需要模指数运算，其计算效率显然更高.

3 结束语

基于格的密码体制在最近几年有了较快的发展，构造基于格的签名体制主要依赖于平均情况SIS问题的困难性假设，而盆景树下格的扩展和格基的随机化方法在构造具有某些特殊属性的签名体制方面有着重要的应用.本文利用带原像采样的单向陷门函数和盆景树下格的扩展和格基的随机化方法，构建了一个基于格的代理签名方案，并基于随机预言模型，证明该方案在选择消息攻击下是可证安全的.与传统的基于数论的代理签名方案相比，该方案的密钥空间较大，但运算简单（只需线性运算），能抵抗量子攻击.

参考文献

［1］ MAMBO M, USUDA K, OKAMOTO E. Proxy signatures for delegating signing operation[C]//Proc 3rd ACM Conference on Computer and Communications Security. New York: ACM, 1996：48-57.

[2] 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.

[3] GENTRY C,PEIKERT C,VAIKUNTANATHAN V. Trapdoors for hard lattices and new cryptographic constructions[C]//Proc 40th ACM Symp on Theory of Computing (STOC). New York: ACM, 2008：197-206.

[4] REGEV O. On lattices, learning with errors, random linear codes, and cryptography[J]. Journal of the ACM, 2009, 56(6):1-40.

[5] PEIKERT C. Public-key cryptosystems from the worst-case shortest vector problem[C]//Proc 41st ACM Symp on Theory of Computing (STOC). New York: ACM, 2009：333-342.

[6] AGRAWAL S,BONEH D,BOYEN X. Efficient lattice (H)IBE in the standard model[C]//Advances in Cryptology-Eurocrypt 2010. Berlin: Springer Verlag, 2010: 553-572.

[7] LYUBASHEVSKY V,PEIKERT C,REGEV O. On ideal lattices and learning with errors over rings[C]//Advances in Cryptology-Eurocrypt 2010. Berlin: Springer Verlag, 2010: 1-23.

[8] LENSTRA A K,LENSTRA H W,LOV′ASZ L. Factoring polynomials with rational coefficients[J]. Math Ann,1982, 261(4):515-534.

[9] MICCIANCIO D, REGEV O. Worst-case to average-case reductions based on gaussian measures[J]. SIAM J Comput, 2007, 37(1):267-302.

[10]AITAI M. Generating hard instances of the short basis problem[C]// ICALP 1999. Berlin: Springer Verlag, 1999:1-9.

[11]CASH D, HOFHEINZ D, KILTZ E,et al. Bonsai trees, or how to delegate a lattice basis [C]// Advances in Cryptology-EUROCRYPT 2010. Berlin: Springer Verlag,2010:523-552.

[12]MICCIANCIO D,WARINSCHI B. A linear space algorithm for computing the Hermite normal form[C]// Proceedings of the 2001 International Symposium on Symbolic and Algebraic Computation(ISSAC). Berlin: Springer Verlag, 2001:231-236.

推荐访问:签名 方案 代理