一种基于格的高效签密方案的分析与设计

郑晓，王茜，鲁龙

（西华大学计算机与软件工程学院，成都　610039）

一种基于格的高效签密方案的分析与设计

郑晓，王茜，鲁龙

（西华大学计算机与软件工程学院，成都610039）

0　引言

保密性、完整性、认证和不可抵赖性是许多加密应用程序的重要要求，如果需要同时实现这些性质，传统方法是对文件先签名后加密，1997年Zheng［1］提出一种新的加密原语称为签密，同时满足数字签名和秘钥加密两种功能，成本低于传统的先签名后加密的方法。此后，这种签密体制被广泛应用于许多应用领域，如电子商务、移动通信和智能卡等。Zheng给出基于离散对数问题的两个签密方案，他留下一个通过使用任何公钥密码体制，设计其他签密方案 （如Rivest-Shamir-Adleman RSA［2］）的开放问题，Steinfeld-Zheng［3］和Malone-Lee［4］分别用整数分解和RSA提出签密方案，后来基于身份的签密用双线性对也被提出［5～7］。近年来格密码迅速发展，相比基于平均情况下依赖于离散对数和因式分解的其他密码原语，格基密码的安全性是基于最坏情况下格问题困难性的特点，本文提出的方案在学习错误（LWE）假设下，对自适应性选择密文攻击具有不可区分性（IND-CCA2），在非齐次小整数解（ISIS）假设下对自适应选择消息攻击具有强不可伪造性（sUF-CMA）。

1　预备知识

1.1符号说明

本文中，R表示实数集，Z表示整数集，［n］表示｛1，2，…｝，通过定义f（A）=∑x∈Af（x）把实函数f（·）扩展到可数集A上。用加粗的小写字母表示列向量，例如x，x的第i个元素表示成xi，矩阵用加粗的大写字母表示，例如X，X的第i列向量表示成Xi，向量x的长度用欧几里得范数||x||表示，||x||=maxi||xi||。一个n维格表示成｝是线性独立向量，B是格基，∧的对偶格定义成∧*=｛x∈Rn: ∀y∈∧＜x，y＞∈Z｝，由对称性，可看到（∧*）*=∧，B*=（B-1）T，所以B*是∧*的一个基。对于任意包含k个线性独立向量的集合s=｛s1，…，sn｝∈Rn，代表它的格莱姆-施密特正交向量，即=s1对每一个i=2，…n是si的投影，该投影与span（s，…，s）正交，并且‖‖≤‖s‖。

不难得出：∧⊥（A）=q·∧（A）*∧（A）=q·∧⊥（A）*。

格上的高斯分布：对于任意s＞0，定义以向量c为中心，s为参数的高斯分布为：∀x∈Rnρs，c（x）=exp（-π

格上离散高斯分布：

本方案的安全性依赖于LWE和ISIS问题的困难性，为找出这些困难问题，我们需要一些概率分布。

定义两个分布：

Ψα定义为以0为正态随机变量均值，标准偏差为在T上模1的分布。定义为以模q为随机变量在Zq上的离散正态分布，其中X是在Ψα分布中的一个随机变量。

1.2格上的定义

定义1 LWE判定目标问题LWEq，x：给一整数q和一个在Z上的分布χ，LWE判定问题的目标是：上的As，x分布与上的均匀分布之间用不可忽略的概率加以区分。说明如果LWE问题是困难的，那么As，x的分布集合是伪随机的。

定义2 标准的LWE问题：从分布As，x中采样，找到。

命题1［8］表明：对某些模q和高斯错误分布χ，用量子算法解决几个最坏情况下的标准格问题和LWEq，x问题是一样难的。

命题1给α=α（n）∈（0，1），q=q（n）是一素数，使得，如果存在一个解决的有效算法，那么存在一接近最短独立向量问题SIVP和判定性的最短距离（GapSVP）问题有效量子算法。

1.3前向采样函数

2008年，Gentry，Peikert和Vaikuntan-athan［9］定义并创造了前向采样函数，这里仅给出前向采样函数的结构，参考文献［9］前向采样函数的定义，函数用下面的结果给出［10］。

命题2 给定任意素数q=poly（n）和任意m≥5nl-gq，存在一个概率多项式算法，输入1n，输出矩阵A∈和一个满秩的集合s⊂∧⊥（A，q），A在上是统计均匀的，并且‖s‖≤L=m2.5。特别地，集合s能被有效地转化为∧⊥（A）的一个短基T，使得‖‖≤‖‖≤L。

SampleDom（A，s）：B是Zm的标准基，这个算法用在文献［9］中定义的算法SampleD（B，s，0）从分布中采样，SampleD（B，s，c）以格基B，参数s，c∈Rm作为输入，输出一个统计接近于D∧，s，c的采样。

SamplePre（T，u）：这个算法以u∈Rn，陷门T作为输入，输出和SampleDom算法中一样的分布e∈Dn，使得Ae=u mod q。

这个函数是无陷门的单向抗碰撞函数，参考文献［9］表明在均匀输出u∈Rn的fA逆函数，等价于解决ISIS问题。

1.4GPV签名方案

H:｛0，1｝*→Rn是一哈希函数，GPV签名方案包含下面三个算法：

KeyGen（1n）：这个算法运行TrapGen（1n），输出公钥A，私钥T。

Sign（T，m）：给一个消息m签名，签名者随机选一个r←｛0，1｝k，计算δ=SamplePre（T，H（m，r）），m的签名是（r，δ）。

Verify（A，m，（r，δ））：给出m的签名（r，δ），当且仅当如果r∈｛0，1｝k，δ∈Dn，fA（β）=H（m，r），验证者接收这个签名。

2　签密的正式模型

2.1一般签密方案

一般签密方案包含以下三个算法：

密钥生成算法KeyGen（1n）：以安全参数n作为输入，输出发送者的密钥对 （pks，sks），接收者的密钥对（pkr，skr）。

签密算法Signcrypt（m，sks，pkr）：给出消息m，发送者私钥sks，接收者公钥pkr，该算法输出密文σ。

解签密算法Unsigncrypt（σ，pks，skr）：给一密文σ，发送者公钥pks，接收者私钥skr，该算法要么输出明文m，要么输出⊥。这些算法必须满足签密的标准一致性约束，即，如果σ=Signcrypt（m，sks，pkr），那么有m=Unsigncrypt（σ，pks，skr）。

2.2安全性表述

签密方案应满足保密性与认证性，及与之相对应的能抵抗适应性选择密文攻击的不可区分性 （INDCCA2）和适应性选择消息攻击的不可伪造性 （EUFCMA）。我们认为强不可伪造性（sUF）比现存不可伪造性更强。

用挑战者C与敌手A之间的游戏来说明IINDCCA2安全：

Initial：C运行密钥生成算法生成接收者密钥对（pkr*，skr*），C把pkr*传给A，skr*保密。

Phase 1：在解签密询问中，A把由发送者密钥（pks，sks）生成的密文σ发送给C，C运行解签密预言机并返回m=Unsigncrypt（σ，pks，skr*）。

Challenge：A选两等长r消息 m0，m1，把它们及（pks*，sks*）发送给C，C随机从｛0，1｝中选b位，运行签密预言机并返回密文σ*=Signcrypt（mb，sks*，pkr*），C把σ*发送给A作为一挑战密文。

Phase 2：A能用不同发送者的密钥对挑战密文σ*做一次解签密查询。

Guess：A产生一位b'，如果b'=b，赢得游戏。

定义5如果没有概率t多项式时间，至多qu次解签密询问后，敌手A至少有lsc优势，那么签密方案是（lsc，t，qu）-IND-CCA2。

用挑战者C和敌手F之间的游戏来说明sUF-CMA安全：

Initial：C运行密钥生成算法产生发送者密钥对（pks*，sks*），C把pks*发送给F，sks*保密。

Attack：在签名询问中，F把m，（pkr，skr）发送给C，C运行签密预言机并返回 σ=signcrypt（m，sks*，pkr），C 把σ发送给F。

Forgery：F选一个接收者密钥对（pkr*，skr*）并产生一新密文σ*（σ*不是由签密预言机产生的），如果σ*是有效密文，F赢得游戏。

定义6如果没有概率t多项式时间，至多qs次签密询问后，敌手F至多有lsc优势，那么签密方案是（lsc，t，qs）-sUF-CMA。

3　格基签密方案

我们提出一个格基签密方案是基于GPV签名方案的［9］，定义两个哈希函数：H1:｛0，1｝*→Rn，H2:｛0，1｝*→｛0，1｝l，l是消息的长度。我们方案包含下面三个算法：

KeyGen（1n）：该算法运行TrapGen（1n），产生发送者的公私钥 （pks，sks）=（As，Ts），和接收者的公私钥（pkr，skr）=（Ar，Tr）。

Signcrypt（m，sks，pkr）：把一个消息发送给接收者，发送者运行以下步骤：

①r←｛0，1｝*；

②计算δ=SamplePre（Ts，H1（m，r））；

③s∈Znq；

④计算c=m⊕H2（s，δ）；

⑤计算u=ATrs+δ，密文是σ=（c，r，u）。

Unsigncrypt（σ，pks，skr）：当收到一个密文σ=（c，r，u）后，接收者运行以下算法：

①用接收者的私钥Tr从u中计算出s，δ，

②恢复m=c⊕H2（s，δ）

③当且仅当r∈｛0，1｝k，δ∈Dn，fAs（δ）=H1（m，r）都满足时接收此密文。

因为（Ar，u=ATrs+δ）是一短向量δ的LWE实例，计算：

TTuu mod q=TTr（ATr+δ）mod q=（ArTr）Ts+TTrs mod q= TTrδ mod q。

因为Tr和δ仅包含小项目，向量TTrδ的每一项远小于q，因此TTδ mod q=TTrδ所以用（TTr）-1乘 TTrδ得到δ，然后恢复出s。在这个方案中，签名δ被用作u=ATrs+δ的错误项，这个技术是被Gordon，Katz，and Vaikuntanathan［11］创建群签名提出的。

4　方案的安全性证明

定理1在随机预言机模型中，如果敌手A在时间t，qu次解签密询问和qHi次询问预言机Hi（i=1，2）后，以不可忽略优势lsc对抗IND-CCA2安全，那么存在一算法C能在时间t'＜t+（qu+qH）tlwe+qutsig内，以e'≥esc-2的概率解决LWE问题。其中t表示决定（A，u，lwes，δ）是有效LWE实例所需时间，tsig表示决定fAs（δ）=H1（m，r）成立所需时间。

证明：反证法：假设存在一个用不可忽略的概率lsc赢得IND-CCA2游戏的敌手A，创建一个能用概率e'解决LWE问题的算法C，假设C是一个LWE问题的m实例C在IND-CCA2游戏中，敌手A作为一子程序运行，找出s的解来充当敌手A的挑战者。

Phase 1敌手A执行H1，H2的多项式界定数，并且以自适应的方式解签密询问，C分别保留两个模拟哈希预言机H1和H2的两个表L1和L2。

H1询问：对于H1（mi，ri）询问（1≤i≤qH1），C首先验证H1的值是否是之前为（mi，ri）输入定义的值，如果它是，则返回先前定义的值，否则，C随机选择h1i∈Rn，把（mi，ri，h1i）插入表L1，返回h1i到A。

H2询问：对于H2（si，δi）询问（1≤i≤qH2），C首先验证H2的值是否是之前为（si，δi）输入定义的值，如果是，返回先前定义的值，否则C随机选择h2i←｛0，1｝l，把（si，δi，h2i）插入表L2，返回h2i到A。

解签密询问：如果敌手A发送一个由发送者公私钥（pks，sks）生成的密文（c，r，u）给一个解签密询问，C进行如下：C浏览表L2，找（si，δi，h2i），使得u=ATsi+δi以及与之相对应的元素h2i，mi=c⊕h2i使得在表L1中存在一元组（mi，r，hli），如果找不到元组，输出⊥，C进一步验证是否fpk（δi）=hli成立，如果成立，mi返回到A，否则，s返回⊥。

Challenge：phase1阶段后，A选两个等长密文m0，m1，把它们以及发送者公私钥（pks*，sks*）发送给C，C随机选两位串r*←｛0，1｝k，c*←｛0，1｝l，让u*=，C发送挑战密文σ*=（c*，r*，u*）给A。

Phase 2：A用不同发送者的公私钥对挑战密文σ*做解签密询问，除非A请求的哈希值，不然它不知道σ*不是一个有效签密，在那种情况下，LWE的解恰在表L2中，敌手A的模拟观点是否完美不再重要。

Guess：A产生一结果b'，C检查（si，δi，h2i）形式的表L2，C验证是否成立，若成立C输出LWE解 si，否则C输出⊥。

我们现在能确定C成功的概率，让AskH2成为A在模拟期间访问哈希值的事件，有

lsc=|2Pr［b=b'］-1|≤Pr［AskH2］。对（si，δi，h2i）在表L2中每一元组恰有一h1i在预言机H1范围内提供一有效密文，所以有

定理2在随机预言机模型中，如果敌手F在时间t内，进行qs次签密询问和qHi次对预言机Hi（i=1，2）询问，以不可忽略的优势lsc对之前方案的sUF-CMA安全，那么存在算法C在时间t'=t内以概率e'≥esc抵抗GPV签名方案的sUF-CMA安全。

证明：反证法：如果敌手A在上面的方案中能伪造一个签名，那么在GPV签名方案中可以伪造一个签名算法A。

Initial：C给出被攻击签名者的公钥A，让pks*=A，发送pkr*给F。

Attack：F运行H1、H2多项式界定数，以自适应方式签密询问C保留两个模拟预言机H1、H2的表L1、L2：

H1询问：对于H1（mi，ri）询问（1≤i≤qH），C首先验

1证H1的值是否是之前定义的（mi，ri）输入的值，若是，则返回之前定义的值，否则，C设置δi=SampleDom（1n）把（mi，ri，δi，fA（δi））放到L1表，返回fA（δi）到A。

H2询问：对于H2（si，δi）询问（1≤i≤qH2），C首先验证H2的值是否是之前定义的（si，δi）输入的值，若是，则返回之前定义的值，否则，C随机选择h2i←｛0，1｝l，把（si，δi，h2i）放到L2表，返回h2i到A。

签密询问：如果F对一个由接收者公私钥（pkr，skr）生成的消息m进行签密询问，C用自己的签名预言机对消息m做签名询问得到 （r，δ），然后C把（m，r，δ，fA（δ））放到表L1，最后，C随机选s∈Zn，计算c=m⊕H2（s，δ），u=pkTrs+δ，（c，r，u）返回到A。

Forgery:

①从u*中用接收者私钥skr*计算s*，δ*。

②恢复m*=c*⊕H2（s*，δ*）。

③在GPV签名方案中，输出（r*，δ*）作为m*的伪造签名。下面证明正确性：因为σ*=（c*，r*，u*）是有效密文，有fA（δ*）=H1（m*，r*），因此，（r*，δ*）是m*的有效签名，因为在随机语言模型下，GPV签名方案是sUF-CMA安全的，所以我们的方案在随机预言机模型下也是sUFCMA的，因此有e'≥esc，t'=t。

5　结语

在这篇文章中，我们提出一个在随机语言机模型下的有效的格基签密方案，证实我们的方案在LWE假设下是IND-CCA2安全的，在ISIS假设下是sUF-CMA安全的，一次能发送消息长度为L，并且给出Zheng方案的开放问题一个新的解。

［1］Zheng Y.Digital Signcryption or How to Achieve Cost（Signature&Encryption）Cost（Signature）+Cost（Encryption）.In Proceedings Advances in Cryptology-CRYPTO'97，LNCS 1294.Springer-Verlag:Santa Barbara，California，USA，1997：165～179

［2］Rivest RL，Shamir A，Adlema L.A Method for Obtaining Digital Signatures and Public Key Cryptosystems.Communications of the ACM 1978，21（2）:120～126

［3］Steinfeld R，Zheng Y.A Signcryption Scheme Based on Integer Factorization.In Proceedings Information Security ISW 2000，LNCS 1975.Springer-Verlag:Wollongong，NSW，Australia，2000：308～322

［4］Malone-Lee J，Mao W.Two Birds One Stone:Signcryption Using，RSA.In Proceedings Topics in Cryptology-CT-RSA，2003，LNCS 2612.Springer-Verlag:San Francisco，CA，USA，2003：211～225

［5］Boyen X.Multipurpose Identity-Based Signcryption:a Swiss Army Knife for Identity-Based Cryptography.In Proceedings Advances in Cryptology-CRYPTO 2003，LNCS 2729.Springer-Verlag:Santa Barbara，California，USA，2003：383～399

［6］Chen L，Malone-Lee J.Improved Identity-Based Signcryption.In Proceedings Public Key Cryptography-PKC 2005，LNCS 3386. Springer-Verlag:Les Diablerets，Switzerland，2005：362～379

［7］Barreto PSLM，Libert B，McCullagh N，Quisquater J.J.Efficient and Provably-Secure Identity-Based Signatures and Signcryption from Bilinear Maps.In Proceedings Advances in Cryptology-ASIACRYPT，LNCS 3788，Springer-Verlag:Chennai，India，2005：512～523

［8］Regev O.On lattices，Learning with Errors，Random Linear Codes，and Cryptography.Journal of the ACM 2009，56（6），Article

［9］Regev O.on lattice，Learning with Errors，Random Linear Codes.and Cryptography.Journal of the ACM 2009，56（6）Article34

［10］Ajtai M.Generating Hard Instances of the Short Basis Problem.In Proceedings Automata，Languages and Programming-ICALP 1999，LNCS 1644.Springer-Verlag:Prague，Czech Republic，1999：1～9

［11］Gordon SD，Katz J，Vaikuntanathan V.A Group Signature Scheme from Lattice Assumptions.In Proceedings Advances in Cryptology-ASIACRYPT 2010，LNCS 6477.Springer-Verlag:Singapore，2010：395～412

Lattice；Random Oracle；Signcryption

Analysis and Design of an Efficient Lattice-Based Signcryption Scheme

ZHENG Xiao，WANG Qian，LU Long
（Institute of Computer Software Engineering,Xihua University，Chengdu 610039）

1007-1423（2015）08-0003-05

10.3969/j.issn.1007-1423.2015.08.001

郑晓（1984-），女，山东德州人，硕士研究生，研究方向为计算机技术

王茜（1990-），女，湖北宜昌人，硕士研究生，研究方向为计算机技术

鲁龙（1989-），男，山东临沂人，硕士研究生，研究方向为计算机软件与理论

2015-01-29

2015-03-06

签密是同时执行数字签名和公共密钥加密两种功能的一个加密原语，所需成本比通过传统的先签名后加密的方法低。设计一个一次发送长度为L消息的高效签密方案。并证明，该方案在错误学习假设下具有适应性选择密文攻击不可区分性（IND-CCA2），在非均匀小整数解假设下具有适应性选择消息攻击强不可伪造性（SUF-CMA）。与基于数论假设方案相比，该方案具有密钥空间较大，但效率更高。

格；随机预言机；签密

Signcryption is a cryptographic primitive that performs simultaneously both the functions of digital signature and public-key encryption,at a cost significantly lower than that required by the traditional signature-then-encryption approach.Designs an efficient signcryption scheme that can send a message of length L one time.Proves that the proposed scheme has the indistinguishability against adaptive chosen ciphertext attacks under the learning with errors assumption and strong unforgeability against adaptive chosen messages attacks under the inhomogeneous small integer solution assumption inthe random oracle model.Compared with the schemes based on factoring or discrete log,the public and secret keys of the scheme are large,but it requires only linear operation on small integers.