格上的异构签密

路秀华，温巧燕，王励成

（1. 廊坊师范学院数学与信息科学学院 河北 廊坊 065000；2. 北京邮电大学网络与交换技术国家重点实验室 北京 海淀区 100876；3. 北京邮电大学信息安全中心 北京 海淀区 100876；4. 廊坊市数学生态模型重点实验室 河北 廊坊 065000）

格上的异构签密

路秀华1，2，4，温巧燕2，王励成3

（1. 廊坊师范学院数学与信息科学学院 河北 廊坊 065000；2. 北京邮电大学网络与交换技术国家重点实验室 北京 海淀区 100876；3. 北京邮电大学信息安全中心 北京 海淀区 100876；4. 廊坊市数学生态模型重点实验室 河北 廊坊 065000）

现存的类型1异构签密方案，安全性都基于传统的数论假设，因此无法抵抗量子计算机的攻击。针对这个问题，以抗量子攻击的格中困难问题——带错学习问题和非齐次小整数解问题为基础，运用格上签密方案的构造方法，结合格上固定维数的格基代理技术，构造了第一个格上的异构签密方案，并证明了该方案的正确性和安全性。该方案实现了异构签密方案的抗量子攻击属性，为PKI系统到身份密码系统的抗量子攻击的安全信息传输提供了理论支撑。

固定维数； 异构签密； 格基密码； 格基代理； 量子计算机

1976年，Diffie和Hellman提出了公钥密码体制［1］。根据公钥认证方法的不同，公钥密码体制分为如下3种：基于PKI的公钥密码体制（PKC）、基于身份的公钥密码体制（IBC）和无证书公钥密码体制［2］。

签密是一个密码学原语［3］，它包括了加密和签名的功能，可以同时实现消息的机密性和认证性，既保证了信息传输的安全性，又提高了执行效率，受到诸多研究者的关注［4-9］。这些研究成果涉及了3种公钥密码体制。

由于公钥密码体制的多样化，通信系统采用的安全技术也不尽相同。为了解决使用不同安全技术的通信系统之间的通信问题，文献［10］提出了异构签密的概念，致力于实现不同通信系统间的安全通信。

本文关注PKC和IBC之间的签密方案的构造，包括两种类型：类型1，发送者使用PKC技术，接收者使用IBC技术；类型2，发送者使用IBC技术，接收者使用PKC技术［2］。文献［11］提出了一个类型2的签密方案；文献［12］提出了类型1和类型2的签密方案。这些方案的安全性都基于传统的数论假设，不能抵抗量子计算机的攻击。

随着量子计算机的迅猛发展，构造能够抵抗量子攻击的密码体制，成为一个迫切的课题。基于格理论的公钥密码体制，由于其最坏情况的安全性保证和线性运算的快速实现，成为后量子密码的典型代表。文献［9］提出了一个基于格的公钥签密方案。在此工作的基础上，本文构造了第一个格上的类型1异构签密方案。

1 涉及的格中算法和定义

算法 1 TrapGen［13］

此算法输入参数n，q，m，输出两个矩阵（A，T），其中A 服从Zn×mq上的均匀分布，T∈Zm×m满足AT = 0（mod q）且T 中的每个列向量具有较小长度。

算法 2 BasisDel［14］

算法 3 SamplePre［13］

算法 4 SampleRwithBasis［14］

BTB= 0（modq）且 TB中的每个列向量具有较小长度。

定义 1 LWE［13］

带错学习问题（learning with errors problem， LWE）描述如下：给定二元组其中e服从某个适当的概率分布，求解

定义 2 ISIS［13］

非齐次小整数问题（inhomogeneous small integer solution problem， ISIS）描述如下：对于0β＞，和二元组寻找非零的短向量使得

定义 3 GPV签名［13］

GPV签名方案如下构建：对安全参数n，q=poly（n），m≥5nlgq，高斯参数σ＞0，和碰撞稳固的hash函数

1） 密钥生成：运行算法TrapGen （n，q，m） 生成（A，T）， A为验证公钥，T 为签名私钥。

2） 签名算法：输入签名私钥T，消息ϖ∈｛0，1｝l随机选择运行算法SamplePre（A，T，H（ϖ，ζ），σ）获得e∈Zm。输出（ζ，e）作为消息ϖ的签名。

在ISIS问题难解性假设下，GPV签名在适应性选择消息攻击下是存在性不可伪造的，也就是EUF-CMA安全的。

2 类型1异构签密的模型［2］

1） 系统设置：此算法由PKG（private key generator）执行。输入安全参数n，输出主密钥msk和系统参数params。保密msk，公开params。

2） PKC密钥生成：PKI系统中的每个用户执行这个算法生成自己的公钥pk和私钥sk。

3） IBC密钥生成：算法由PKG执行，输入是用户身份id，输出是身份id的私钥sk。

4） 签密算法：算法由消息的发送者完成，输入为params，发送者的私钥sks，接收者的身份id，消息ϖ，输出密文C。

5） 解签密算法：算法由消息的接收者完成，输入为params，接收者的私钥skid，发送者的公钥pks，密文C，输出消息ϖ或终止符号⊥。

此外，算法必须满足正确性，如果C= Signcrypt（sks，id，ϖ）,则有ϖ= Unsigncrypt（skid，pksC。

3 类型1异构签密的安全性定义［2］

定义 4 如果任何多项式有界的敌手A在如下的和挑战者C的游戏中胜出的概率都是可忽略的，则称类型1的异构签密方案具有适应性选择密文攻击下的不可区分性，即是IND-HSC-CCA2安全的。

1） 初始阶段：C运行系统设置，生成系统参数params；并运行PKC密钥生成算法获得发送者的公钥pks和私钥sks，一并发送给A。

2） 阶段1：A可以执行多项式有界次数的如下查询，C负责应答。

① IBC密钥查询：

A选择一个身份id发送给C，C运行IBC密钥生成算法得到身份id的私钥skid，返回给A。

② 解签密查询：

A选择一个接收者身份id和一个密文C发送给C。C运行IBC密钥生成算法得到身份id的私钥Unsigncrypt（sk，pk，）C，将运行结果返回给A。

3） 挑战阶段：阶段1由A宣告终止，同时A选择两个相同长度的明文ϖ1，ϖ2和接收者身份id0（要求id0未被查询过密钥），将其发送给C 。C 随机选择b∈｛0，1｝，计算C0= Signcrypt（sks，id0，ϖb） ，将其返回给A。

4） 阶段2：A继续执行阶段1中的操作，除了不能查询id0的私钥，不能对（id0，C0）执行解签密查询。

5） 猜测阶段：A输出对b的猜测b′。如果b′= b，A赢得游戏。

定义 5 如果任何多项式有界的敌手F在如下的和挑战者C的游戏中胜出的概率都是可忽略的，则称类型1的异构签密方案具有适应性选择消息攻击下的存在不可伪造性，也就是EUF-HSC-CMA安全的。

1） 初始阶段：C运行系统设置，获得主密钥msk和系统参数params。同时运行PKC密钥生成算法，获得发送者的公钥pks和私钥sks。C将msk、params和pks发送给F。

2） 攻击阶段：F执行多项式有界次数的签密查询。在签密查询中，F选择一个接收者的身份id和一个消息ϖ给C。C执行签密算法Signcrypt（sks，id，ϖ） ，将其结果返回给F。

3） 伪造阶段：F生成一个接收者身份id0和一个新的密文C0。如果身份id0和密文C0满足如下条件：

① Unsigncrypt（sk0，pks，C0）返回某个消息ϖ0而不是终止符号⊥；

② F没有询问过关于ϖ0和id0的签密查询；则称F赢得了游戏。

F的优势为他赢得游戏的概率。

4 类型1异构签密方案

1） 系统设置

输入安全参数n，对q = poly（n），m≥5nlg q ，PKG运行算法TrapGen （n，q，m）生成（A，T）， A为主公钥，T 为主私钥。

2） PKC密钥生成

每个用户S运行算法TrapGen （n，q，m） 生成（As，Ts），A为公钥， Ts为私钥。

3） IBC密钥生成

对用户身份id∈｛0，1｝∗，PKG计算R=H1（id）。

运行算法BasisDel 1 （A，T，R，σ1）产生（Aid，Tid）其中Aid=AR-1（modq）,Tid为用户身份id的私钥。

4） 签密算法

发送者S 要发送消息ϖ ∈｛0，1｝l给身份为id 的接收者，设发送者S 的公钥为As，私钥为 Ts，则发送者S如下操作：

5） 解签密算法

① 利用Tid从中恢复v和e。

5 方案的正确性和安全性分析

5.1 方案的正确性分析

因为矩阵 Tid和向量e都只有足够小的数值作为分量

综上，解签密算法是正确的。

5.2 方案的安全性分析

定理 1 IND-HSC-CCA2安全性

在LWE问题难解性假设下，方案作为类型1异构签密体制是IND-HSC-CCA2安全的。

2） 阶段1：A可执行多项式有界次数的如下查询，且默认hash查询在其他查询之前，C负责应答。

① Hi（id1）查询：

如果是第i0次查询，把存在H1列表中，返回R0。否则，运行算法SampleRwithBasis（A），得Ri和 Ti，把存在H1列表中，返回Ri。

④ IBC密钥查询（idi）：

遍历 H1列表查找返回 Ti。

遍历 H1列表查找若执行方案的解签密算法；若 Ti=⊥，遍历H2和H3列表寻找满足如果这样的三元组不存在，返回⊥并终止。如果这样的三元组存在，而且满足和返回ϖi作为解签密的结果。否则，返回⊥并终止。

3） 挑战阶段：阶段1由A宣告终止，同时A选择两个相同长度的明文ϖ1,ϖ2和接收者身份id∗，将其发送给C。如果id∗≠id0，返回⊥并终止。否则，C随机选择将返回给A。

4） 阶段2：A执行阶段1的操作，除了不能查询id0的私钥，不能对（id0，C∗）执行解签密查询。

5） 猜测阶段：A输出对b的猜测b′。

最后，C查询H3列表寻找它满足如下条件：存在在列表H2中，且满足如果这样的元组存在，C输出 v∗作为LWE问题实例的解。否则，输出⊥并终止。

设E是如下事件：A在游戏中查询了H3（v∗，e∗）。如果游戏完美地模拟了真实的攻击，E在游戏中发生的概率就和它在真实攻击中发生的概率是一样的。

下面考虑游戏不能完美地模拟真实攻击的情况。这实际上是合法的密文在解签密查询中被拒绝的情况。对H3列表中的每一个存在着唯一的与之对应，因此拒绝合法密文的概率不超过

此外，id∗=id0的概率为所以如果ε是不可忽略的，则ε′也是不可忽略的。这与LWE问题的难解性相矛盾。因此，在LWE问题难解性假设下，能够以不可忽略的概率攻击方案作为类型1异构签密体制的IND-HSCCCA2安全性的敌手A是不存在的。所以，在LWE问题难解性假设下，方案作为类型1异构签密体制是IND-HSC-CCA2安全的。

定理 2 EUF-HSC-CMA安全性

在ISIS问题难解性假设下，方案作为类型1异构签密体制是EUF-HSC-CMA安全的。

证明：假设存在敌手F以不可忽略的优势ε攻击方案的EUF-HSC-CMA安全性，就会存在挑战者C，他能够借助F的攻击能力来攻击GPV签名方案的EUF-CMA安全性。C和F之间的交互如下。

2） 攻击阶段：F可以执行多项式有界次数的签密查询，C负责给出合理的应答。在签密查询中，F提交一个接收者的身份idj和一个消息ϖj给C。C对消息ϖj运行GPV签名查询得（ζj，ej）。他随机选择和给F。

3） 伪造阶段：F提供一个接收者的身份id*和一个新的合法密文返回给C。

C如下操作得到一个新的合法的GPV签名：

由以上过程可以看出，如果F伪造合法密文的概率ε是不可忽略的，则C伪造合法的GPV签名的概率也是不可忽略的。而由文献［13］，在ISIS问题难解性假设下，GPV签名是EUF-CMA安全的。因此，能够以不可忽略的优势攻击方案的EUF-HSC-CMA安全性的敌手F是不存在的。所以，在ISIS问题难解性假设下，方案是EUF-HSC-CMA安全的。

6 结 束 语

结合格上签密方案和固定维数的格基代理技术，构造了第一个格上的类型1异构签密方案，第一次实现了抗量子攻击的异构签密。方案使用了随机预言机模型来完成安全性证明，构造标准模型下的量子安全的异构签密，是进一步的研究方向。

本文得到廊坊师范学院博士基金（LSLB201408）的资助，在此表示感谢。

［1］ DIFFIE W， HELLMAN M E. New directions in cryptography［J］. IEEE Transactions on Information Theory，1976， 22（6）： 644-654.

［2］ 李发根， 廖永建. 数字签密原理与技术［M］. 北京： 科学出版社， 2014. LI Fa-gen， LIAO Yong-jian. The principle and technology of digital signcryption［M］. Beijing： Science Press， 2014.

［3］ ZHENG Y. Digital signcryption or how to achieve cost（signature & encryption）<

［4］ YU Y， YANG B， SUN Y， et al. Identity based signcryption scheme without random oracles［J］. Computer Standards & Interfaces， 2009， 31（1）： 56-62.

［5］ YU G， MA X， SHEN Y， et al. Provable secure identity based generalized signcryption scheme［J］. Theoretical Computer Science， 2010， 411（40）： 3614-3624.

［6］ LIU Z， HU Y， ZHANG X， et al. Certificateless signcryption scheme in the standard model［J］. Information Sciences，2010， 180（3）： 452-464.

［7］ LIU W H， XU C X. Certificateless signcryption scheme without bilinear pairing［J］. Journal of Software， 2011， 22（8）：1918-1926.

［8］ WANG F， HU Y， WANG C. Post-quantum secure hybrid signcryption from lattice assumption［J］. Applied Mathematics & Information Sciences， 2012， 6（1）： 23-28.

［9］ LI F， BIN MUHAYA F T， KHAN M K， et al. Lattice-based signcryption［J］. Concurrency and Computation： Practice and Experience， 2013， 25（14）： 2112-2122.

［10］ SUN Y X， LI H. Efficient signcryption between TPKC and IDPKC and its multi-receiver construction［J］. Science China Information Sciences， 2010， 53（3）： 557-566.

［11］ HUANG Q， WONG D S， YANG G. Heterogeneous signcryption with key privacy［J］. The Computer Journal，2011， 54（4）： 525-536.

［12］ LI F， ZHANG H， TAKAGI T. Efficient signcryption for heterogeneous systems［J］. IEEE Systems Journal， 2013，7（3）： 420-429.

［13］ GENTRY C， PEIKERT C， VAIKUNTANATHAN V. Trapdoors for hard lattices and new cryptographic constructions［C］// Proceedings of the fortieth annual ACM symposium on Theory of computing. Victoria： ACM Press，2008： 197-206.

［14］ AGRAWAL S， BONEH D， BOYEN X. Lattice basis delegation in fixed dimension and shorter-ciphertext hierarchical IBE［C］//Advances in Cryptology-CRYPTO 2010. Santa Barbara： Springer Berlin Heidelberg， 2010：98-115.

编 辑 蒋 晓

更 正 启 事

我刊2016年第1期155页中“刘林仙1，2”更正为“刘林仙1”，“LIU Lin-xian1，2”更正为“LIU Lin-xian1”。

特此更正。

本刊编辑部

A Lattice-Based Heterogeneous Signcryption

LU Xiu-hua1，2，4， WEN Qiao-yan2， and WANG Li-cheng3
（1. Faculty of Mathematics and Information Science， Langfang Teachers University Langfang Hebei 065000；2. State Key Laboratory of Networking and Switching Technology， Beijing University of Posts and Telecommunications Haidian Beijing 100876；3. Information Security Center， Beijing University of Posts and Telecommunications Haidian Beijing 100876；4. Laboratory of Mathematical Model for Ecology in Langfang Langfang Heibei 065000）

The existing type 1 heterogeneous signcryption schemes are all based on the traditional number theoretic assumptions， so that they cannot resist a quantum computer attacks. To solve this problem， based on the quantum-resistant lattice hard problems， learning with errors problem and inhomogeneous small integer solution problem， we use the techniques of lattice-based signcryption and lattice basis delegation in fixed dimension， build the first lattice-based heterogeneous signcryption scheme. We also provide its correctness and security analysis. The scheme actualizes the property of quantum resistance， and gives theoretical support for anti-quantum communication from public key infrastructure （PKI） systems to identity-based systems.

fixed dimension； heterogeneous signcryption； lattice-based cryptography； lattice basis delegation； quantum computer

TP309

A

10.3969/j.issn.1001-0548.2016.02.025

2015 - 03 - 05；

2015 - 09 - 25

国家自然科学基金（61402015）；河北省教育厅青年基金（QN2015084）；陕西省教育厅专项科研计划项目（15JK1022）

路秀华（1979 - ），女，博士生，主要从事基于格的公钥密码体制的研究.