格上的異構(gòu)簽密

路秀華，溫巧燕，王勵成

（1. 廊坊師范學(xué)院數(shù)學(xué)與信息科學(xué)學(xué)院 河北 廊坊 065000；2. 北京郵電大學(xué)網(wǎng)絡(luò)與交換技術(shù)國家重點實驗室 北京 海淀區(qū) 100876；3. 北京郵電大學(xué)信息安全中心 北京 海淀區(qū) 100876；4. 廊坊市數(shù)學(xué)生態(tài)模型重點實驗室 河北 廊坊 065000）

格上的異構(gòu)簽密

路秀華1，2，4，溫巧燕2，王勵成3

（1. 廊坊師范學(xué)院數(shù)學(xué)與信息科學(xué)學(xué)院 河北 廊坊 065000；2. 北京郵電大學(xué)網(wǎng)絡(luò)與交換技術(shù)國家重點實驗室 北京 海淀區(qū) 100876；3. 北京郵電大學(xué)信息安全中心 北京 海淀區(qū) 100876；4. 廊坊市數(shù)學(xué)生態(tài)模型重點實驗室 河北 廊坊 065000）

現(xiàn)存的類型1異構(gòu)簽密方案，安全性都基于傳統(tǒng)的數(shù)論假設(shè)，因此無法抵抗量子計算機的攻擊。針對這個問題，以抗量子攻擊的格中困難問題——帶錯學(xué)習(xí)問題和非齊次小整數(shù)解問題為基礎(chǔ)，運用格上簽密方案的構(gòu)造方法，結(jié)合格上固定維數(shù)的格基代理技術(shù)，構(gòu)造了第一個格上的異構(gòu)簽密方案，并證明了該方案的正確性和安全性。該方案實現(xiàn)了異構(gòu)簽密方案的抗量子攻擊屬性，為PKI系統(tǒng)到身份密碼系統(tǒng)的抗量子攻擊的安全信息傳輸提供了理論支撐。

固定維數(shù)； 異構(gòu)簽密； 格基密碼； 格基代理； 量子計算機

1976年，Diffie和Hellman提出了公鑰密碼體制［1］。根據(jù)公鑰認證方法的不同，公鑰密碼體制分為如下3種：基于PKI的公鑰密碼體制（PKC）、基于身份的公鑰密碼體制（IBC）和無證書公鑰密碼體制［2］。

簽密是一個密碼學(xué)原語［3］，它包括了加密和簽名的功能，可以同時實現(xiàn)消息的機密性和認證性，既保證了信息傳輸?shù)陌踩裕痔岣吡藞?zhí)行效率，受到諸多研究者的關(guān)注［4-9］。這些研究成果涉及了3種公鑰密碼體制。

由于公鑰密碼體制的多樣化，通信系統(tǒng)采用的安全技術(shù)也不盡相同。為了解決使用不同安全技術(shù)的通信系統(tǒng)之間的通信問題，文獻［10］提出了異構(gòu)簽密的概念，致力于實現(xiàn)不同通信系統(tǒng)間的安全通信。

本文關(guān)注PKC和IBC之間的簽密方案的構(gòu)造，包括兩種類型：類型1，發(fā)送者使用PKC技術(shù)，接收者使用IBC技術(shù)；類型2，發(fā)送者使用IBC技術(shù)，接收者使用PKC技術(shù)［2］。文獻［11］提出了一個類型2的簽密方案；文獻［12］提出了類型1和類型2的簽密方案。這些方案的安全性都基于傳統(tǒng)的數(shù)論假設(shè)，不能抵抗量子計算機的攻擊。

隨著量子計算機的迅猛發(fā)展，構(gòu)造能夠抵抗量子攻擊的密碼體制，成為一個迫切的課題。基于格理論的公鑰密碼體制，由于其最壞情況的安全性保證和線性運算的快速實現(xiàn)，成為后量子密碼的典型代表。文獻［9］提出了一個基于格的公鑰簽密方案。在此工作的基礎(chǔ)上，本文構(gòu)造了第一個格上的類型1異構(gòu)簽密方案。

1 涉及的格中算法和定義

算法 1 TrapGen［13］

此算法輸入?yún)?shù)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］

帶錯學(xué)習(xí)問題（learning with errors problem， LWE）描述如下：給定二元組其中e服從某個適當(dāng)?shù)母怕史植?，求?/p>

定義 2 ISIS［13］

非齊次小整數(shù)問題（inhomogeneous small integer solution problem， ISIS）描述如下：對于0β＞，和二元組尋找非零的短向量使得

定義 3 GPV簽名［13］

GPV簽名方案如下構(gòu)建：對安全參數(shù)n，q=poly（n），m≥5nlgq，高斯參數(shù)σ＞0，和碰撞穩(wěn)固的hash函數(shù)

1） 密鑰生成：運行算法TrapGen （n，q，m） 生成（A，T）， A為驗證公鑰，T 為簽名私鑰。

2） 簽名算法：輸入簽名私鑰T，消息?∈｛0，1｝l隨機選擇運行算法SamplePre（A，T，H（?，ζ），σ）獲得e∈Zm。輸出（ζ，e）作為消息?的簽名。

在ISIS問題難解性假設(shè)下，GPV簽名在適應(yīng)性選擇消息攻擊下是存在性不可偽造的，也就是EUF-CMA安全的。

2 類型1異構(gòu)簽密的模型［2］

1） 系統(tǒng)設(shè)置：此算法由PKG（private key generator）執(zhí)行。輸入安全參數(shù)n，輸出主密鑰msk和系統(tǒng)參數(shù)params。保密msk，公開params。

2） PKC密鑰生成：PKI系統(tǒng)中的每個用戶執(zhí)行這個算法生成自己的公鑰pk和私鑰sk。

3） IBC密鑰生成：算法由PKG執(zhí)行，輸入是用戶身份id，輸出是身份id的私鑰sk。

4） 簽密算法：算法由消息的發(fā)送者完成，輸入為params，發(fā)送者的私鑰sks，接收者的身份id，消息?，輸出密文C。

5） 解簽密算法：算法由消息的接收者完成，輸入為params，接收者的私鑰skid，發(fā)送者的公鑰pks，密文C，輸出消息?或終止符號⊥。

此外，算法必須滿足正確性，如果C= Signcrypt（sks，id，?）,則有?= Unsigncrypt（skid，pksC。

3 類型1異構(gòu)簽密的安全性定義［2］

定義 4 如果任何多項式有界的敵手A在如下的和挑戰(zhàn)者C的游戲中勝出的概率都是可忽略的，則稱類型1的異構(gòu)簽密方案具有適應(yīng)性選擇密文攻擊下的不可區(qū)分性，即是IND-HSC-CCA2安全的。

1） 初始階段：C運行系統(tǒng)設(shè)置，生成系統(tǒng)參數(shù)params；并運行PKC密鑰生成算法獲得發(fā)送者的公鑰pks和私鑰sks，一并發(fā)送給A。

2） 階段1：A可以執(zhí)行多項式有界次數(shù)的如下查詢，C負責(zé)應(yīng)答。

① IBC密鑰查詢：

A選擇一個身份id發(fā)送給C，C運行IBC密鑰生成算法得到身份id的私鑰skid，返回給A。

② 解簽密查詢：

A選擇一個接收者身份id和一個密文C發(fā)送給C。C運行IBC密鑰生成算法得到身份id的私鑰Unsigncrypt（sk，pk，）C，將運行結(jié)果返回給A。

3） 挑戰(zhàn)階段：階段1由A宣告終止，同時A選擇兩個相同長度的明文?1，?2和接收者身份id0（要求id0未被查詢過密鑰），將其發(fā)送給C 。C 隨機選擇b∈｛0，1｝，計算C0= Signcrypt（sks，id0，?b） ，將其返回給A。

4） 階段2：A繼續(xù)執(zhí)行階段1中的操作，除了不能查詢id0的私鑰，不能對（id0，C0）執(zhí)行解簽密查詢。

5） 猜測階段：A輸出對b的猜測b′。如果b′= b，A贏得游戲。

定義 5 如果任何多項式有界的敵手F在如下的和挑戰(zhàn)者C的游戲中勝出的概率都是可忽略的，則稱類型1的異構(gòu)簽密方案具有適應(yīng)性選擇消息攻擊下的存在不可偽造性，也就是EUF-HSC-CMA安全的。

1） 初始階段：C運行系統(tǒng)設(shè)置，獲得主密鑰msk和系統(tǒng)參數(shù)params。同時運行PKC密鑰生成算法，獲得發(fā)送者的公鑰pks和私鑰sks。C將msk、params和pks發(fā)送給F。

2） 攻擊階段：F執(zhí)行多項式有界次數(shù)的簽密查詢。在簽密查詢中，F(xiàn)選擇一個接收者的身份id和一個消息?給C。C執(zhí)行簽密算法Signcrypt（sks，id，?） ，將其結(jié)果返回給F。

3） 偽造階段：F生成一個接收者身份id0和一個新的密文C0。如果身份id0和密文C0滿足如下條件：

① Unsigncrypt（sk0，pks，C0）返回某個消息?0而不是終止符號⊥；

② F沒有詢問過關(guān)于?0和id0的簽密查詢；則稱F贏得了游戲。

F的優(yōu)勢為他贏得游戲的概率。

4 類型1異構(gòu)簽密方案

1） 系統(tǒng)設(shè)置

輸入安全參數(shù)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）產(chǎn)生（Aid，Tid）其中Aid=AR-1（modq）,Tid為用戶身份id的私鑰。

4） 簽密算法

發(fā)送者S 要發(fā)送消息? ∈｛0，1｝l給身份為id 的接收者，設(shè)發(fā)送者S 的公鑰為As，私鑰為 Ts，則發(fā)送者S如下操作：

5） 解簽密算法

① 利用Tid從中恢復(fù)v和e。

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

5.1 方案的正確性分析

因為矩陣 Tid和向量e都只有足夠小的數(shù)值作為分量

綜上，解簽密算法是正確的。

5.2 方案的安全性分析

定理 1 IND-HSC-CCA2安全性

在LWE問題難解性假設(shè)下，方案作為類型1異構(gòu)簽密體制是IND-HSC-CCA2安全的。

2） 階段1：A可執(zhí)行多項式有界次數(shù)的如下查詢，且默認hash查詢在其他查詢之前，C負責(zé)應(yīng)答。

① Hi（id1）查詢：

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

④ IBC密鑰查詢（idi）：

遍歷 H1列表查找返回 Ti。

遍歷 H1列表查找若執(zhí)行方案的解簽密算法；若 Ti=⊥，遍歷H2和H3列表尋找滿足如果這樣的三元組不存在，返回⊥并終止。如果這樣的三元組存在，而且滿足和返回?i作為解簽密的結(jié)果。否則，返回⊥并終止。

3） 挑戰(zhàn)階段：階段1由A宣告終止，同時A選擇兩個相同長度的明文?1,?2和接收者身份id?，將其發(fā)送給C。如果id?≠id0，返回⊥并終止。否則，C隨機選擇將返回給A。

4） 階段2：A執(zhí)行階段1的操作，除了不能查詢id0的私鑰，不能對（id0，C?）執(zhí)行解簽密查詢。

5） 猜測階段：A輸出對b的猜測b′。

最后，C查詢H3列表尋找它滿足如下條件：存在在列表H2中，且滿足如果這樣的元組存在，C輸出 v?作為LWE問題實例的解。否則，輸出⊥并終止。

設(shè)E是如下事件：A在游戲中查詢了H3（v?，e?）。如果游戲完美地模擬了真實的攻擊，E在游戲中發(fā)生的概率就和它在真實攻擊中發(fā)生的概率是一樣的。

下面考慮游戲不能完美地模擬真實攻擊的情況。這實際上是合法的密文在解簽密查詢中被拒絕的情況。對H3列表中的每一個存在著唯一的與之對應(yīng)，因此拒絕合法密文的概率不超過

此外，id?=id0的概率為所以如果ε是不可忽略的，則ε′也是不可忽略的。這與LWE問題的難解性相矛盾。因此，在LWE問題難解性假設(shè)下，能夠以不可忽略的概率攻擊方案作為類型1異構(gòu)簽密體制的IND-HSCCCA2安全性的敵手A是不存在的。所以，在LWE問題難解性假設(shè)下，方案作為類型1異構(gòu)簽密體制是IND-HSC-CCA2安全的。

定理 2 EUF-HSC-CMA安全性

在ISIS問題難解性假設(shè)下，方案作為類型1異構(gòu)簽密體制是EUF-HSC-CMA安全的。

證明：假設(shè)存在敵手F以不可忽略的優(yōu)勢ε攻擊方案的EUF-HSC-CMA安全性，就會存在挑戰(zhàn)者C，他能夠借助F的攻擊能力來攻擊GPV簽名方案的EUF-CMA安全性。C和F之間的交互如下。

2） 攻擊階段：F可以執(zhí)行多項式有界次數(shù)的簽密查詢，C負責(zé)給出合理的應(yīng)答。在簽密查詢中，F(xiàn)提交一個接收者的身份idj和一個消息?j給C。C對消息?j運行GPV簽名查詢得（ζj，ej）。他隨機選擇和給F。

3） 偽造階段：F提供一個接收者的身份id*和一個新的合法密文返回給C。

C如下操作得到一個新的合法的GPV簽名：

由以上過程可以看出，如果F偽造合法密文的概率ε是不可忽略的，則C偽造合法的GPV簽名的概率也是不可忽略的。而由文獻［13］，在ISIS問題難解性假設(shè)下，GPV簽名是EUF-CMA安全的。因此，能夠以不可忽略的優(yōu)勢攻擊方案的EUF-HSC-CMA安全性的敵手F是不存在的。所以，在ISIS問題難解性假設(shè)下，方案是EUF-HSC-CMA安全的。

6 結(jié) 束 語

結(jié)合格上簽密方案和固定維數(shù)的格基代理技術(shù)，構(gòu)造了第一個格上的類型1異構(gòu)簽密方案，第一次實現(xiàn)了抗量子攻擊的異構(gòu)簽密。方案使用了隨機預(yù)言機模型來完成安全性證明，構(gòu)造標(biāo)準(zhǔn)模型下的量子安全的異構(gòu)簽密，是進一步的研究方向。

本文得到廊坊師范學(xué)院博士基金（LSLB201408）的資助，在此表示感謝。

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

［2］ 李發(fā)根， 廖永建. 數(shù)字簽密原理與技術(shù)［M］. 北京： 科學(xué)出版社， 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

國家自然科學(xué)基金（61402015）；河北省教育廳青年基金（QN2015084）；陜西省教育廳專項科研計劃項目（15JK1022）

路秀華（1979 - ），女，博士生，主要從事基于格的公鑰密碼體制的研究.