NTRU格上無證書加密

陳　虎　　胡予濮(西安電子科技大學(xué)綜合業(yè)務(wù)網(wǎng)理論及關(guān)鍵技術(shù)國家重點(diǎn)實(shí)驗(yàn)室　西安 710071)

?

NTRU格上無證書加密

陳虎*胡予濮
(西安電子科技大學(xué)綜合業(yè)務(wù)網(wǎng)理論及關(guān)鍵技術(shù)國家重點(diǎn)實(shí)驗(yàn)室西安 710071)

摘要：為降低密鑰尺寸，利用陷門抽樣算法在優(yōu)選的NTRU格上抽取部分私鑰并使用多項(xiàng)式環(huán)上帶誤差的學(xué)習(xí)問題計算公鑰等方法來構(gòu)造格上無證書加密方案。它的安全性基于多項(xiàng)式環(huán)上帶誤差學(xué)習(xí)的判定問題和小多項(xiàng)式比判定問題等兩個困難問題假設(shè)。為獲取更好的效率，該文還提出一個無證書并行加密方案。該方案用中國剩余定理分解擴(kuò)大后的明文空間為多個不同素理想之積來實(shí)現(xiàn)并行加密。它還用中國剩余定理分解加密運(yùn)算所在的多項(xiàng)式環(huán)獲取中國剩余基來優(yōu)化算法，使算法只涉及整數(shù)間運(yùn)算。結(jié)果顯示該方案具有計算和通信復(fù)雜度低等特點(diǎn)。

關(guān)鍵詞：無證書密碼系統(tǒng)；格密碼；環(huán)上帶誤差的學(xué)習(xí)問題；判定小多項(xiàng)式比問題

1　引言

格公鑰密碼以具有抗量子計算攻擊和存在從最差到平均情況的安全歸約等特性成為競相研究的熱點(diǎn)。富含新穎獨(dú)特應(yīng)用場景的格密碼方案[1-3]似春筍般涌現(xiàn)，尤其是從格上構(gòu)造出全同態(tài)加密[4-6]以來格密碼更是人們關(guān)注的焦點(diǎn)。然而格密碼獨(dú)特優(yōu)勢[7]仍難掩其空間開銷大的弱點(diǎn)。致力于降低格公鑰密碼尺寸的成果[3，6-9]層出不窮，其中文獻(xiàn)[3，8，9]不約而同地把目光聚焦在NTRU格上尋求突破口。特別是文獻(xiàn)[3]選擇在一類特殊的分圓多項(xiàng)式環(huán)中構(gòu)造具有小尺寸陷門基的NTRU格，這在離散高斯抽樣中具有重要意義。同時借助NTRU格的公開基和陷門基組成矩陣的結(jié)構(gòu)特點(diǎn)極大地壓縮了存儲空間。而文獻(xiàn)[10，11]在降低格密碼存儲空間時另辟蹊徑地采用了在無證書體制[12-14]下構(gòu)造格上的加密方案。遺憾地，他們只單方面地利用無證書體制不涉及證書管理和以身份作為公鑰等優(yōu)勢來降低公鑰尺寸。因?yàn)樗麄冇梦墨I(xiàn)[15]中陷門生成算法導(dǎo)致格的維數(shù)，所以公鑰尺寸仍很大且方案效率不高。

本文在NTRU格上給出了一個無證書加密方案。它以多項(xiàng)式環(huán)上帶誤差學(xué)習(xí)(RLWE)[16]的判定問題和小多項(xiàng)式比(SPR)[17]判定問題為基礎(chǔ)，并在隨機(jī)預(yù)言模型下證明是語義安全的。受文獻(xiàn)[14]的啟發(fā)，加強(qiáng)了攻擊者的能力[13](見第3節(jié))。為縮小用戶公私鑰尺寸，本文采用四輪驅(qū)動的方式來實(shí)現(xiàn)。首先，部分地依托無證書體制的優(yōu)勢，部分地依靠文獻(xiàn)[3]中小尺寸陷門生成方法來降低高斯抽樣中的偏差和部分地憑借NTRU格的公開基和陷門基自身的結(jié)構(gòu)特點(diǎn)進(jìn)一步壓縮了它們的存儲空間。其次，本文中用戶秘密值和公鑰生成算法簡單自然。用戶的秘密值就作為RLWE問題的秘密多項(xiàng)式，公鑰僅為該秘密值下的1個RLWE對。此外，本文還使用中國剩余定理進(jìn)一步強(qiáng)化方案在密文擴(kuò)展比和計算效率等方面的優(yōu)勢并給出方案。

2　背景知識

2.1 符號

2.2 NTRU格及陷門基生成算法

定義 2[3]設(shè)f，g∈R且，由(h，q)所確定的2n維滿秩格稱為NTRU格，記為，其一組公開基按行組成的矩陣為

引理 1[2]設(shè)的列向量生成，T是格的任一組基，對任意的和，有

我們把上述算法應(yīng)用到NTRU格Λh，q上進(jìn)行抽樣，即抽取，其中，輸出，則有

2.3 困難問題假設(shè)

判定RLWE問題假設(shè)就是該問題是不可區(qū)分的，并有從最差到平均情況的規(guī)約。

引理 2[4，5，16]若，n為2的冪，素數(shù)，，誤差分布(其中Λ=?n)，則存在一個從R中理想格的SIVP(Shortest Independent Vectors Problem)或SVP(Shortest Vector Problem)問題到判定RLWE的隨機(jī)化規(guī)約，其中近似因子為。

存在一個從文獻(xiàn)[16]加密方案(Lyubashersky-Peikert-Regev Encryption，記為LPR.E)到我們方案的規(guī)約。LPR.E在判定RLWE問題假設(shè)下是語義安全的(INDistinguishable Chosen-Plaintext Attack，IND-CPA)，具體方案請參考文獻(xiàn)[16]。

定義3[17]判定小多項(xiàng)式比(SPR)問題就是區(qū)分在Rq上的兩種分布：

2.4 中國剩余定理與中國剩余基

中國剩余定理[16](CRT)可實(shí)現(xiàn)明文空間的分解與聚合。它還可構(gòu)造Rq的中國剩余基[18]。因此，它對提高理想格上的方案效率很有幫助。

據(jù)文獻(xiàn)[16]中引理2.12知：

定義 4 據(jù)式(3)中的同構(gòu)映射設(shè)ψ，φ，定義復(fù)合映射CRTp=φ° ψ。

定義 5[18]若滿足：當(dāng)i=j時，ci=；否則，。稱為Rq的一組 。

引理 3[18]cici=ci∈Rq，其中。

引入中國剩余基可更有效地實(shí)現(xiàn)Rq中的運(yùn)算。如，它們在基下的坐標(biāo)分別為，即。據(jù)引理3知：。

3　安全模型

無證書加密方案由系統(tǒng)參數(shù)生成(Setup)，部分私鑰提取(ExtractPPK)，設(shè)置公/私鑰(Setkey)，加密(Enc)和解密(Dec)等5個算法組成[13]。 在無證書系統(tǒng)中，令(主公鑰，主私鑰，身份，公鑰，部分私鑰，私鑰，秘密值)=(MPK，MSK，ID，PK，PPK，SK，SV)且(公開參數(shù)，第1類攻擊者，第2類攻擊者)。AI不能獲知MSK，但可替換任何用戶的PK。AII可擁有MSK，可向AI那樣替換除了目標(biāo)身份之外任何用戶的PK。用攻擊者與挑戰(zhàn)者B交互的游戲來刻畫無證書加密的IND-CPA安全。

問答交互 A可訪問如下的預(yù)言器(包括hash函數(shù)，若必要)但有次數(shù)限制。這些預(yù)言器都由B控制。為提供完美的攻擊環(huán)境，B必須及時記錄與A每次問答中發(fā)生的數(shù)據(jù)。受文獻(xiàn)[14]的啟發(fā)：本文允許攻擊者詢問用戶的秘密值，導(dǎo)致A不必做用戶私鑰詢問(因?yàn)樗耆梢宰约河行У厣?。A可適用性地做生成用戶，部分私鑰，公鑰替換及秘密值等詢問(部分私鑰詢問只對AI有效)。

猜測 A傳猜測值b'∈{0，1}給B。

定義 6 稱無證書加密是自適應(yīng)選擇消息和身份攻擊下語義安全的，若任何概率多項(xiàng)式時間(PPT)算法，在游戲中勝出的優(yōu)勢為negl(n)。

4　方案構(gòu)造

4.1 無證書加密（CertificateLess Encryption，CL.E）

(1)Setup(1λ)：設(shè)λ為安全參數(shù)，n=n(λ)為2的冪，素數(shù)，誤差分布χ，其中。是抗碰撞的哈希函數(shù)。密鑰生成中心(KGC)運(yùn)行，其中σ2=。設(shè)置(MPK，，消息空間R2，公開參數(shù)params =。這里取。

(2)ExtractPPK(ID，params)：用戶注冊并提交身份。KGC執(zhí)行下列程序輸出(e，d)，并安全地傳(e，d)給該用戶。用戶驗(yàn)證所獲的數(shù)據(jù)是否滿足且。 若滿足，則用戶置d為部分私鑰并銷毀e；否則，要求KGC重新生成。

(a)若系統(tǒng)中已存在該ID，則拒絕并退出程序；否則，執(zhí)行(b)。

(3)Setkey(ID，params)：身份為ID的用戶選取秘密值。設(shè)置私鑰。設(shè)置公鑰PK如下：任選，計算，設(shè)置。

把上述方案的明文空間由R2擴(kuò)大到Rp，借助中國剩余定理來實(shí)現(xiàn)下面的并行加密和優(yōu)化算法(加解密不必做運(yùn)算)[16]。

4.2 無證書并行加密

(1)Setup(1λ)：參數(shù)與 4.1節(jié)Setup(1λ)算法中的相同。 不同是這里增加了：為上一組，選擇小素數(shù)p? q，滿足。 令，設(shè)置嵌入(或聚合)明文空間為(或Rp)，CRTp為的同構(gòu)映射。 然后，計算。 設(shè)置，其中。公開參數(shù)這里。

(2)ExtractPPK(ID，params)：類似4.1節(jié)相應(yīng)的算法，用戶注冊并驗(yàn)證KGC發(fā)送是數(shù)據(jù)(e，d)是否滿足和，這里u來自。

(a)若系統(tǒng)中已存在該ID，則拒絕并退出程序；否則，執(zhí)行步驟(b)。

(3)Setkey(ID，params)：身份為ID的用戶選取秘密值s← χ在基下的坐標(biāo)為s，設(shè)置私鑰。設(shè)置公鑰PK如下：

(5)Dec(c，SK，params)：用私鑰SK=(s，d)解密c=(v1，v2，v3)。

5　方案分析

易見，若4.1節(jié)中方案(CL.E)是正確安全的，則4.2節(jié)方案也如此。故只分析CL.E的性質(zhì)。

5.1 正確性

下面的定理給出CL.E方案的正確性的刻畫。

根據(jù)解密公式，定理1不難證明，限于篇幅，證明從略。

5.2 安全性

定理 2設(shè)判定RLWE和判定SPR困難問題假設(shè)成立。在隨機(jī)預(yù)言模型下，若在時間T內(nèi)，以不可忽略的概率ε攻破CL.E，則存在一個PPT算法B以概率，在不大于時間內(nèi)攻破LPR.E的CPA安全性。

證明在攻擊LPR.E的游戲中，設(shè)算法F是挑戰(zhàn)者，B為攻擊者。在攻擊CL.E的游戲中，B是挑戰(zhàn)者，AI為攻擊者。因此據(jù)AI和F去構(gòu)造B。

問答交互 B選擇t←[q1]，初始化空表L按格式添加記錄。B掌控隨機(jī)預(yù)言器H。AI適應(yīng)地做下列詢問且每次詢問都各異。

(1)生成用戶詢問：當(dāng)AI輸入IDi時，B回應(yīng)：

不失一般性，假設(shè)AI下面詢問所涉及的身份已存在。

(2)部分私鑰詢問：當(dāng)AI輸入IDi時，B回應(yīng)。 當(dāng) i≠ t時，按IDi在L中匹配，傳di給AI。當(dāng)i=t時，終止協(xié)議。

(3)公鑰替換詢問：當(dāng)輸入IDi時，AI同時提供新公鑰給B。B據(jù)IDi匹配L，換，為。

(4)秘密值詢問：當(dāng)AI輸入IDi時，B據(jù)IDi索引L并回應(yīng)。若si≠⊥，則傳si給AI；否則，輸出⊥。

挑戰(zhàn) 只要AI宣布結(jié)束詢問，他輸出挑戰(zhàn)身份IDi和挑戰(zhàn)明文給B。B回應(yīng)。

(2)若ID*的公鑰沒有被換，則令并執(zhí)行(4)；否則，執(zhí)行(3)。

獲勝概率據(jù)RLWE假設(shè)和安全模型關(guān)于AI勝負(fù)的規(guī)定，假定AI必定輸出合法的替換公鑰是合理的。 B攻擊LPR.E獲勝概率，其中事件S1：在部分私鑰詢問時，協(xié)議未終止；事件S2：滿足 ID*=IDt；事件S3:AI成功區(qū)分挑戰(zhàn)密文。協(xié)議沒有終止，從而挑戰(zhàn)身份被完美隱藏。其次，從生成用戶詢問數(shù)據(jù)獲取的方法知：回應(yīng)的部分私鑰分布和身份的hash輸出分布與真實(shí)分布是不可區(qū)分的且不依賴于。此外，公鑰替換、秘密值詢問同真實(shí)攻擊，挑戰(zhàn)密文合法。AI可正常發(fā)揮能力，即。 又，所以有。

因此，若AI能在時間 T 內(nèi)以不可忽略的概率ε攻破CL.E，則B可以在不大于時間內(nèi)以概率攻破LPR.E。證畢

定理 3設(shè)判定RLWE和判定SPR困難問題假設(shè)成立。在隨機(jī)預(yù)言模型下，若在時間T內(nèi)，以不可忽略的概率ε攻破CL.E，則存在一個PPT算法B以概率，在不大于時間內(nèi)攻破LPR.E的CPA安全性。

類似定理2的證明，不再贅述。

5.3 參數(shù)選取

(1)判定RLWE問題：據(jù)文獻(xiàn)[4]，要使方案具有2λ的安全性就需要，其中B為誤差分布的界。由引理1知：。再據(jù)引理2有

其次，從方案的正確性考慮。由5.1節(jié)中定理1并經(jīng)簡單地計算知：

把上面所得的結(jié)果代入式(5)中，得

由式(4)和結(jié)論n≥256，限定256≤n≤poly(λ)，即。又因?yàn)椋詽M足式(7)的充分條件：。于是，。 推出。從而。由式(4)，式(7)和n≥256知：

證明略。

5.4 效率

目前可公開獲取的格上無證書加密方案[10，11]是基于標(biāo)準(zhǔn)LWE問題的困難性假設(shè)，而本文方案CL.E是以RLWE問題為基礎(chǔ)。又因?yàn)槲墨I(xiàn)[10]是標(biāo)準(zhǔn)模型下的方案，效率必然低于文獻(xiàn)[11]和本文在隨機(jī)預(yù)言模型下的方案，所以只需在文獻(xiàn)[11]和本文之間作比較。典型地取 。類似5.3節(jié)中的計算，可以得到給定參數(shù)n下，文獻(xiàn)[11]與本文方案的計算結(jié)果如表1所示，從表1可看出，本文方案每個指標(biāo)都占優(yōu)。

表1　效率對比

6　結(jié)論

本文提出一個無證書加密方案。它比文獻(xiàn)[11]中方案有更小的存儲開銷，更低的計算和通信代價。本文方案可根據(jù)效率和安全做權(quán)衡。其一，如文獻(xiàn)[3]那樣把抽取誤差多項(xiàng)式的系數(shù)限制在集{-1，0，1}中，以獲得更好的效率。其二，在生成NTRU格的陷門基時，適當(dāng)放大高斯抽樣偏差抽取f和g來取消小多項(xiàng)式比問題假設(shè)，以獲得更強(qiáng)的安全。

參考文獻(xiàn)

[1]GENTRY C，PEIKERT C，and VAIKUNTANATHAN V.Trapdoors for hard lattices and new cryptographic constructions[C].Proceedings of the 40th ACM Symposium on Theory of Computing(STOC08)，Victoria，Canada，2008:197-206.doi:10.1145/1374376.1374407.

[2]AGRAWAL S，BONEH D，and BOYEN X.Lattice basisdelegation in fixed dimension and shorter-ciphertext hierarchical IBE[J].LNCS，2010，6223:98-115.doi:10.1007 /978-3-642-14623-7_6.

[3]DUCAS L，LYUBASHEVSKY V，and PREST T.Efficient identity-based encryption over NTRU lattices[J].LNCS，2014，8874:22-41.doi:10.1007/978-3-662-45608-8_2.

[4]BRAKERSKI Z，GENTRY C，and VAIKUNTANATHAN V.Fully homomorphic encryption without Bootstrapping[C].Proceedings of the 3rd Innovations in Theoretical Computer Science(ITCS)Conference，Cambridge，Massachusetts，2012:309-325.

[5]LOPEZ-ALT A，TROMER E，and VAIKUNTANATHAN V.On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption[C].Proceedings of the 44th ACM Symposium on Theory of Computing(STOC12)，New York，USA，2012:1219-1234.doi:10.1145/2213977.2214086.

[6]BRAKERSKI Z and VAIKUNTANATHAN V.LatticebasedFHE as secure as PKE[C].Proceedings of the 5rd Innovations in Theoretical Computer Science(ITCS)Conference，Princeton，New Jersey，2014:1-12.

[7]MICCIANCIO D and PEIKERT C.Trapdoor for lattices:simpler，tighter，faster，smaller[J].LNCS，2012，7237:738-755.

[8]JARVIS K and NEVINS M.ETRU:NTRU over the Eisenstein integers[J].Designs，Codes and Cryptography，2015，74(1):219-242.

[9]BI J G and CHENG Q.Lower bounds of shortest vector lengths in random NTRU lattices[J].Theoretical Computer Science，2014，560(2):121-130.doi:10.1007/978-3-642-29952-0_18.

[10]SEPAHI R，STEINFELD R，and PIEPRZYK J.Latticebased certificateless public-key encryption in the standard model[J].International Journal of Information Security，2014，13(4):315-333.doi:10.1007/s10207-013-0215-8.

[11]JIANG Mingming，HU Yupu，LEI Hao，et al.Lattice-based certificateless encryption scheme[J].Frontiers of Computer Science，2014，8(5):828-836.doi:10.1007/s11704-014-3187-6.

[12]AL-RIYAMI S S and PATERSON K G.Certificateless public key cryptography[J].LNCS，2003，2894:452-473.

[13]DENT A.A survey of Certificateless encryption schemes and security models[J].International Journal of Information Security，2008，7(5):347-377.doi:10.1007/s10207-008-0055-0.

[14]陳虎，張福泰，宋如順.可證安全的無證書代理簽名方案[J].軟件學(xué)報，2009，20(3):692-701.doi:10.3724/SP.J.1001.2009.00574.CHEN Hu，ZHANG Futai，and SONG Rushun.Certificateless proxy signature scheme with provable security[J].Journal of Software，2009，20(3):692-701.doi:10.3724/SP.J.1001.2009.00574.

[15]ALWEN J and PEIKERT C.Generating shorter bases for hard random lattices[J].Theory of Computing Systems，2011，48(3):535-553.

[16]LYUBASHEVSKY V，PEIKERT C，and REGEV O.On ideal lattices and learning with errors over rings[J].Journal of the ACM，2013，60(6):43:1-43:35.

[17]STEHLE D and STEINFELD R.Making NTRU as secure as worst-case problems over ideal lattices[J].LNCS，2011，6632:27-47.

[18]LYUBASHEVSKY V，PEIKERT C，and REGEV O.A toolkit for ring-LWE cryptography[J].LNCS，2013，7881:35-54.

[19]LINDNER R and PEIKERT C.Better key sizes(and attacks)for LWE-based encryption[J].LNCS，2011，6558:319-339.doi:10.1007/978-3-642-19074-2_21.

陳虎：男，1975年生，博士生，副教授，研究方向?yàn)楦衩艽a和無證書加密與簽名.

胡予濮：男，1955年生，教授，博士生導(dǎo)師，研究方向?yàn)楦衩艽a和流密碼.

Certificateless Encryption over NTRU Lattices

CHEN HuHU Yupu
(State Key Laboratory of Integrated Service Networks，Xidian University,Xi’an 710071，China)

Abstract:To lower the sizes of keys，a certificateless encryption scheme is put forward by using a trapdoor sampling algorithm over a selected NTRU lattice to extract partial private keys and using Ring Learning With Errors(RLWE)problem to generate public keys.Its security is based on both assumptions of the decisional ring learning with errors problem and the decisional Small Polynomial Ratio(SPR)problem.To further improve efficiency，a certificateless parallel encryption scheme with more efficient algorithms only using arithmetic in integers is also given by respectively using the Chinese Remainder Theorem(CRT)to decompose the enlarged plaintext space into the product of distinct prime ideals and to break down the ring，over which encryption operations work，for obtaining the Chinese Remainder basis.The given results show that the proposed schemes are characterized by low computation complexity and small communication complexity.

Key words:Certificateless cryptosystem; Lattice cryptography; Ring Learning With Errors(RLWE)problem; Decisional Small Polynomial Ratio(SPR)problem

基金項(xiàng)目：國家自然科學(xué)基金(61472309，61173151)，安徽省自然科學(xué)基金(1208085MF108，KJ2012B157)

通信作者：陳虎 chenhuchh@163.com

收稿日期：2015-04-01；改回日期：2015-11-13；網(wǎng)絡(luò)出版：2016-01-04

DOI:10.11999/JEIT150380

中圖分類號：TP309

文獻(xiàn)標(biāo)識碼：A

文章編號：1009-5896(2016)02-0347-07

Foundation Items:The National Natural Science Foundation of China(61472309，61173151)，The Natural Science Foundation of Anhui Province(1208085MF108，KJ2012B157)