葉 青 胡明星 湯永利 劉 琨 閆璽璽

(河南理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 河南焦作 454000)(yeqing@hpu.edu.cn)

2017-06-05；

2017-07-28

國家自然科學(xué)基金項(xiàng)目(61300216)；河南省科技廳基礎(chǔ)與前沿技術(shù)研究計(jì)劃項(xiàng)目(142300410147);河南省教育廳自然科學(xué)研究項(xiàng)目(12A520021)；河南省教育廳高等學(xué)校重點(diǎn)科研項(xiàng)目(16A520013) This work was supported by the National Natural Science Foundation of China (61300216), the Foundation and Advanced Technology Research Plan of Henan Provincial Department of Science and Technology (142300410147), the Natural Science Research Project of Henan Provincial Department of Education (12A520021), and the Key Research Project of Henan Provincial Department of Education (16A520013).

湯永利(yltang@hpu.edu.cn)

基于LWE的高效身份基分級加密方案

葉 青 胡明星 湯永利 劉 琨 閆璽璽

(河南理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 河南焦作 454000)(yeqing@hpu.edu.cn)

格上可固定維數(shù)陷門派生的身份基分級加密(hierarchical identity-based encryption, HIBE)體制，因其具有在陷門派生前后格的維數(shù)保持不變的特性而受到廣泛關(guān)注，但這種體制普遍存在陷門派生復(fù)雜度過高的問題.針對這一問題，分別給出隨機(jī)預(yù)言模型和標(biāo)準(zhǔn)模型下的改進(jìn)方案.首先利用MP12陷門函數(shù)的特性提出一種優(yōu)化的q可逆矩陣提取算法，再基于該優(yōu)化算法結(jié)合固定維數(shù)的陷門派生算法和MP12陷門函數(shù)完成方案的建立和陷門派生階段，然后與對偶Regev算法相結(jié)合完成隨機(jī)預(yù)言模型下HIBE方案的構(gòu)造.并且利用二進(jìn)制樹加密系統(tǒng)將該方案改進(jìn)為標(biāo)準(zhǔn)模型下的HIBE方案.兩方案安全性均可歸約至LWE問題的難解性，其中隨機(jī)預(yù)言模型下的方案滿足適應(yīng)性安全，而標(biāo)準(zhǔn)模型下的方案滿足選擇性安全，并給出嚴(yán)格的安全性證明.對比分析表明：在相同的安全性下，隨機(jī)預(yù)言模型下的方案較同類方案在陷門派生復(fù)雜度方面顯著降低，而標(biāo)準(zhǔn)模型下的方案是同類最優(yōu)方案的16，且格的維數(shù)、陷門尺寸和密文擴(kuò)展率等參數(shù)均有所降低，計(jì)算效率明顯優(yōu)化.

格；基于身份的分級加密；陷門派生；容錯(cuò)學(xué)習(xí)；隨機(jī)預(yù)言模型；標(biāo)準(zhǔn)模型

基于身份加密(identity-based encryption, IBE)是一種高級的公鑰加密體制，該體制可使用用戶任意的身份標(biāo)識符(如郵箱地址、手機(jī)號碼等)作為公鑰，相應(yīng)的私鑰由可信第三方私鑰生成中心(key generation center, KGC)利用系統(tǒng)主私鑰生成.基于身份加密的思想首先于1984年由Shamir[1]首次提出，但直到2001年，可實(shí)際應(yīng)用的IBE方案才由Boneh等人[2]提出并定義了IBE的安全模型.此后IBE的研究引起密碼學(xué)者的廣泛關(guān)注，很多IBE的相關(guān)方案被相繼提出[3-6].

基于身份的分級加密(hierarchical identity-based encryption, HIBE)體制是IBE體制的一種推廣.在HIBE體制中，多個(gè)KGC實(shí)體按照有向樹的結(jié)構(gòu)分布.HIBE可以更好地應(yīng)用在大規(guī)模網(wǎng)絡(luò)的應(yīng)用場景中，有效解決IBE體制在大量的用戶請求下無法為每一用戶完成身份信息的有效驗(yàn)證并為之安全傳送私鑰的問題.HIBE體制的特點(diǎn)是體制中每個(gè)子KGC陷門均由它的父KGC指定，該過程稱為陷門派生.應(yīng)當(dāng)注意的是陷門派生是單向的，這意味著每個(gè)子KGC均不能利用它的陷門來恢復(fù)父KGC或同級KGC的陷門.

近幾年，基于格理論構(gòu)造的新型密碼體制因具有較好的漸進(jìn)效率、運(yùn)算簡單、可并行化、抗量子攻擊和存在最壞情況下的隨機(jī)實(shí)例等優(yōu)點(diǎn)，成為后量子密碼時(shí)代的研究熱點(diǎn)，并取得一系列的研究成果[7-11].2008年，Gentry等人[12]于STOC’08上利用格的短基作為陷門構(gòu)造出一種格上原像采樣算法，并提出對偶Regev算法；基于這2個(gè)算法和Ajtai等人[13]提出的陷門生成算法構(gòu)造出格上IBE方案，并且指出在構(gòu)造(H)IBE方案時(shí)應(yīng)采用對偶Regev算法來完成方案的加解密階段，比采用非對偶Regev算法更加合理，隨后基于對偶Regev算法的(H)IBE方案[14-17]被相繼提出.但Gentry等人提出的IBE體制的缺陷是所基于的原像采樣算法和陷門生成算法太過復(fù)雜，算法的運(yùn)行時(shí)間不滿足實(shí)際應(yīng)用；2010年，Cash等人[18]基于Gentry等人的原像采樣算法構(gòu)造出一種格上陷門派生算法，并基于此構(gòu)造出格上首個(gè)HIBE方案，但陷門派生算法的派生陷門的維數(shù)與系統(tǒng)分級的深度呈2次冪增長關(guān)系，這將導(dǎo)致在較高的系統(tǒng)分級中出現(xiàn)格的維數(shù)、陷門尺寸等參數(shù)過大而導(dǎo)致陷門派生的復(fù)雜度過高的問題；2010年，Agrawal等人[19]于EUROCRYPT 2010上對Cash等人的方案進(jìn)行了改進(jìn)，將按照用戶身份向量每1比特分配矩陣的方式改進(jìn)為按系統(tǒng)分級中每一級分配1個(gè)矩陣的方式，從而使格的維數(shù)隨著系統(tǒng)分級深度的增長而僅呈線性增長，但維數(shù)的增長仍然會導(dǎo)致格的維數(shù)、陷門尺寸等參數(shù)的膨脹而導(dǎo)致陷門派生復(fù)雜度過大；2010年，Agrawal等人[20]于CRYPTO 2010上提出一種固定維數(shù)的格上陷門派生技術(shù)，即格的維數(shù)在陷門派生前后保持不變，并基于此構(gòu)造出一種高效的HIBE方案.格的維數(shù)是格上密碼方案的重要參數(shù)與密鑰長度、密文尺寸和密文膨脹率等參數(shù)密切相關(guān)，因此格上固定維數(shù)的陷門派生技術(shù)引起密碼學(xué)領(lǐng)域的廣泛關(guān)注.但該方案和陷門派生算法的構(gòu)造均依賴一種q可逆矩陣的提取算法(SampleR)，而該算法效率取決于原像采樣算法，但Agrawal等人所采用的原像采樣算法由上述的文獻(xiàn)[12]中提出，該算法的輸入是高精度的實(shí)數(shù)且是迭代化運(yùn)算，這將導(dǎo)致SampleR算法的復(fù)雜度過高，進(jìn)而影響陷門派生的效率.

2012年，Micciancio等人[21](Micciancio和Peikert于2012年發(fā)表的文章簡稱MP12)于EUROCRYPT 2012上提出一種新的格上陷門生成算法和與之對應(yīng)的原像采樣算法，相比文獻(xiàn)[17,22]提出的陷門生成算法，該陷門生成過程簡單，復(fù)雜度僅相當(dāng)于2個(gè)隨機(jī)矩陣的1次乘運(yùn)算，且不涉及計(jì)算代價(jià)高的埃爾米特正規(guī)形式(hermite normal form, HNF)和矩陣求逆操作.相比文獻(xiàn)[12]的原像采樣算法，MP12原像采樣算法較簡單高效，且算法支持并行運(yùn)算且輸入項(xiàng)為小整數(shù)，對離線空間的需求較低.另外，Micciancio等人還提出了一種新的陷門派生算法，該算法相比Cash等人的算法較高效，因?yàn)樵撍惴o須進(jìn)行線性無關(guān)檢測，且派生陷門的維數(shù)與系統(tǒng)分級的深度僅呈線性增長的關(guān)系，但維數(shù)增長導(dǎo)致陷門派生低效的問題仍然沒有解決.

為使基于固定維數(shù)派生技術(shù)的HIBE方案更具有實(shí)際應(yīng)用可行性，必須解決其陷門派生復(fù)雜度過高的問題.因此，本文提出一種高效的格上HIBE方案.主要貢獻(xiàn)有：1)利用MP12陷門函數(shù)[21]的特性構(gòu)造出一種優(yōu)化的SampleR算法；2)基于優(yōu)化的SampleR算法結(jié)合固定維數(shù)的陷門派生算法和高效MP12陷門生成算法完成HIBE方案的陷門生成和陷門派生階段，然后與對偶Regev算法有機(jī)結(jié)合完成隨機(jī)預(yù)言模型下的方案構(gòu)造；3)利用Cash等人提出的二進(jìn)制樹加密系統(tǒng)消除隨機(jī)預(yù)言機(jī)假設(shè)，從而改進(jìn)為標(biāo)準(zhǔn)模型下的HIBE方案.采用與同類方案相同的安全模型進(jìn)行嚴(yán)格的安全性證明，證明結(jié)果表明：本文2個(gè)方案的安全性均可歸約至容錯(cuò)學(xué)習(xí)(learning with errors, LWE)問題的難解性，其中隨機(jī)預(yù)言下的HIBE方案滿足IND-aID-CPA安全性，標(biāo)準(zhǔn)模型下的HIBE方案滿足IND-sID-CPA安全性.在效率對比分析中，為更好地體現(xiàn)對比結(jié)果，我們將HIBE陷門派生前的參數(shù)和計(jì)算效率與派生后的分開進(jìn)行對比.對比結(jié)果表明:與相同安全性的方案相比，本文隨機(jī)預(yù)言模型下的方案在陷門派生復(fù)雜度方面顯著降低，而標(biāo)準(zhǔn)模型下的方案是同類最優(yōu)方案的1/6，且格的維數(shù)、陷門尺寸和密文擴(kuò)展率等參數(shù)均有所降低，計(jì)算效率明顯優(yōu)化.

1 預(yù)備知識

1.1格的相關(guān)定義

定義1. 格的定義.設(shè)b1,b2,…,bm是n上m個(gè)線性無關(guān)向量，格Λ定義為所有這些向量的整系數(shù)線性組合，即:

其中,向量組b1,b2,…,bm稱為格的一組基.

定義2.q元格.設(shè)q,n,m∈，A∈n×mq，且u∈nq，定義:

定義3. 離散高斯分布.對任意σ>0，定義以向量c為中心、σ為參數(shù)的格Λ上的離散高斯分布為

其中,y∈Λ，ρσ,c(y)=exp(-π‖y-c‖σ2).

1.2相關(guān)算法和困難問題

本文方案構(gòu)造所基于的MP12陷門生成算法和與之對應(yīng)的MP12原像采樣算法分別由引理1和引理2給出；SampleR算法由引理3給出；固定維數(shù)的陷門派生算法由引理6給出；引理4是引理6的基本算法；對偶Regev算法的具體描述請參閱文獻(xiàn)[12]；隨機(jī)預(yù)言模型下方案的安全性證明基于引理7、引理8和定義4；標(biāo)準(zhǔn)模型下方案的安全性證明基于引理8和定義4；方案的正確性證明基于引理2和引理9.

定義4[7]. 容錯(cuò)學(xué)習(xí)(learning with errors, LWE)問題. 設(shè)n為正整數(shù)，q為素?cái)?shù)，對任意0<α≤1ω()，定義Ψα為中心是0、標(biāo)準(zhǔn)差是α的[0,1)上的正態(tài)分布，對應(yīng)的q上的離散分布為為q上的容錯(cuò)分布，(q,n)-LWE問題實(shí)例由未指明的挑戰(zhàn)預(yù)言機(jī)O構(gòu)成：預(yù)言機(jī)O是帶噪音的偽隨機(jī)預(yù)言機(jī)Os或者是真隨機(jī)的預(yù)言機(jī)O$，2種預(yù)言機(jī)的輸出分別如下：

O$：輸出nq×q上的真隨機(jī)且均勻的采樣值.

是不可忽略的，其中LWE-adv[A]表示A解決(q,n)-LWE問題的優(yōu)勢.

引理4[20]. SampleRwithTrap算法.與引理1參數(shù)相同.設(shè)除了至多q-n部分之外所有的A0∈n×mq，算法SampleRwithTrap輸出一個(gè)m×m矩陣R，具體是從與Dm×m統(tǒng)計(jì)接近的分布上隨機(jī)選取矩陣R的列向量.且算法SampleRwithTrap輸出的A0R-1的陷門矩陣TB滿足：

引理5[20]. 與引理1參數(shù)相同，設(shè)e為m中某向量，向量mq，則|eTy|可看作[0,q-1]中的整數(shù)，滿足|eTy|≤‖e‖qαω()+‖e‖2.

引理6[20]. SampleR算法.與引理1參數(shù)相同，設(shè)T是格m的格基，利用與引理8類似的原像采樣算法隨機(jī)抽取m個(gè)向量ri←Sample(m,T,σR,0)，其中i=1,2,…,m，將ri作為矩陣R的列向量.如果矩陣R是q可逆(矩陣R是q可逆指矩陣Rmodq仍是m×m上的可逆矩陣)的，則輸出R，否則重新抽取ri.

引理7[21]. MP12陷門生成算法.與引理1參數(shù)相同，令H∈n×nq為可逆矩陣，G∈n×wq是構(gòu)造公開的矩陣.選取一個(gè)均勻隨機(jī)矩陣q，存在概率多項(xiàng)式時(shí)間(probabilistic polynomial time, PPT)算法輸出矩陣‖HG-n×mq和陷門矩陣TA0=[a1‖a2‖…‖aw]∈，陷門尺寸s1(TA0)≤×ω()，其中A0在n×mq上是統(tǒng)計(jì)均勻的，TA0是矩陣A0的陷門.

引理8[21]. MP12原像采樣算法.與引理1參數(shù)相同，設(shè)u∈nq為均勻隨機(jī)向量，充分大的高斯參數(shù)σ=O()，ω()表示漸進(jìn)性高于，則存在概率多項(xiàng)式時(shí)間算法MP12Sample(A0,M,TA0,u,σ)，其中，M∈n×wq，輸出向量e∈，且e的分布與統(tǒng)計(jì)不可區(qū)分‖e‖>σ]≤negl(n)，其中).

2 算法設(shè)計(jì)及方案構(gòu)造

2.1符號說明

為表述方便，對文中符號進(jìn)行說明，如表1所示:

Table 1 Notations Description表1 符號說明

2.2優(yōu)化的SampleR算法

本節(jié)構(gòu)造的優(yōu)化SampleR算法的功能與Agrawal等人提出的陷門派生算法中的(見引理6)相同.由于SampleR算法輸出的R矩陣是公開的，且算法的時(shí)間復(fù)雜度主要來自于算法中循環(huán)調(diào)用的原像采樣算法.所以我們考慮采用較高效的MP12原像采樣算法MP12Sample(見引理8).具體方法是利用MP12陷門函數(shù)中構(gòu)造公開的特殊矩陣G和其公開陷門矩陣TG來進(jìn)行SampleR算法中的原像采樣操作.具體優(yōu)化算法如下：

輸入：整數(shù)m=O(nlbq)、用來在陪集Λ⊥(G)高斯采樣的預(yù)言機(jī)OG、其高斯參數(shù)為σG;

2) Fori=1,2,…,mdo:

3) 將ri作為矩陣R的列向量，檢測R是否是q可逆，是則輸出R，否則重新進(jìn)行步驟2.

相比Agrawal等人[20]提出的SampleR算法：首先，在效率上，MP12Sample算法的輸入項(xiàng)是小整數(shù)可支持并行化運(yùn)算而不是輸入項(xiàng)是高精度實(shí)數(shù)的正交化迭代運(yùn)算，且原像采樣過程中利用G矩陣和G矩陣陷門的特殊構(gòu)造，時(shí)間復(fù)雜度相比通常的原像采樣算法的Ω(n2lb2n)可降至O(nlbcn)，其中c是常數(shù).因此，相比Agrawal等人提出復(fù)雜度是Ω(n3lb3nn)的SampleR算法，我們的算法復(fù)雜度是O(n2lbcn).其次，在輸出質(zhì)量(原像采樣算法的輸出質(zhì)量為所采樣向量的范數(shù))上，質(zhì)量好壞與原像采樣大小限制參數(shù)β負(fù)相關(guān).Agrawal等人的HIBE方案采用的是文獻(xiàn)[21]的陷門生成算法和文獻(xiàn)[12]的原像采樣算法，則βAgrawal>45nlgq，而本文βour≈2.3nlgq，相比之下本文有近19倍的提升.

我們的優(yōu)化算法存在的不足是相比Agrawal等人的SampleR算法多了第2步中的②操作，該操作采用高效正向計(jì)算的方式輸出，復(fù)雜度僅等同于執(zhí)行1次Hash算法.

2.3隨機(jī)預(yù)言模型下的HIBE方案

方案具體構(gòu)造如下，其基本參數(shù)包括：均勻隨機(jī)矩陣A0∈n×mq和其陷門R0∈，其中n是安全參數(shù)，d是系統(tǒng)支持的最大分級深度，用戶身份id=(id1‖id2‖…‖id)∈({0,1}*)，其中∈[d]，i∈[1,].令其中.一個(gè)構(gòu)造公開的矩陣G=In?gT∈n×nkq，其中In是n×n單位矩陣，gT=(1,2,22,…,2k-1)∈kq；隨機(jī)預(yù)言機(jī)H:({0,1}*)≤d→m×mq:id|→H(id)～Dm×m.

HIBE-Derive(MPK,SKi d|,id)：輸入主公鑰MPK；輸入SKi d|表示系統(tǒng)分級深度為時(shí)用戶公鑰矩陣Ai d|所對應(yīng)的陷門矩陣，其中n×mq，父用戶身份id=(id1‖id2‖…‖id)，可逆矩陣Ri d|=H(id|1)H(id|2)…H(id)∈m×m；輸入子用戶身份id=(id1‖id2‖…‖id‖id‖…,‖其中d.計(jì)算R=H(id)H(id)…H(id|k)∈m×m并令A(yù)i d=Ai dR-1.調(diào)用引理2的陷門派生算法輸出陷門矩陣SKi d=S′.另外，將參數(shù)Ai d0設(shè)為A0，SKi d|0設(shè)為TA0，HIBE-Derive算法相當(dāng)于IBE方案中的用戶密鑰提取算法IBE-Extract.

2.4標(biāo)準(zhǔn)模型下的HIBE方案

HIBE-Derive(MPK,SKi d|,id)：輸入主公鑰MPK；輸入SKi d|表示系統(tǒng)分級深度為時(shí)用戶公鑰矩陣Ai d|所對應(yīng)的陷門矩陣，其中Ai d=A0(R1,id1)-1(R2,id2)-1…(R)-1∈n×mq，父用戶身份id={0,1}；輸入子用戶身份id=(id1‖id2‖…‖id‖id‖…,‖其中d.令m×m，Ai d=Ai dR∈n×mq.調(diào)用2.3節(jié)的陷門派生算法輸出陷門矩陣SKi d=S′.

3 安全性證明

通常，一個(gè)HIBE方案的安全性需滿足選擇身份攻擊和選擇明文攻擊下的密文不可區(qū)分性(IND-ID-CPA)，根據(jù)安全強(qiáng)度不同，分為適應(yīng)性選擇身份選擇明文攻擊(IND-aID-CPA)和選擇性選擇身份選擇明文攻擊(IND-sID-CPA).本文方案在隨機(jī)預(yù)言模型下滿足IND-aID-CPA安全，在標(biāo)準(zhǔn)模型下滿足IND-sID-CPA安全.

本方案采用Agrawal等人[19]在EEUROCRYPT 2010上提出的格上HIBE方案的INDr-s/aID-CPA安全模型進(jìn)行安全性證明，該安全模型不僅可證明IND-s/aID-CPA安全，還可以保護(hù)接收方的匿名性，且主公鑰的私密性可被其創(chuàng)建的密文保護(hù).基于該安全模型進(jìn)行安全證明的還有2010年Agrawal等人[20]于CRYPTO 2010和2016年Wang等人[24]于FITEE提出的HIBE方案.

正確性. 本文HIBE方案的解密正確性由定理1刻畫.

定理1. 本文HIBE方案的解密是正確的，對任意的id∈ID，(MPK,MSK)←HIBE-Setup(1n,d)，ski d←HIBE-Extract(MPK,R,(id1‖id2‖…‖id)‖id)和消息b∈{0,1}，其中ID為身份空間，有

Pr[Decrypt(MPK,ski d,Encrypt(MPK,id,b))=b]=1-negl(n)成立.

證明. HIBE方案解密算法的輸出為

Table 2 Parameters Setting of HIBE Scheme Under Random Oracle Model

Table3ParametersSettingofHIBESchemeUnderStandardModel

表3 標(biāo)準(zhǔn)模型下HIBE方案的參數(shù)設(shè)置

表2和表3所示的參數(shù)設(shè)定下，本文2.3節(jié)和2.4節(jié)的HIBE方案中的error-term均小于q5，則方案正確性得以保證.

證畢.

安全性. 本文隨機(jī)預(yù)言模型下的HIBE方案的安全性由定理2刻畫.

定理2. 設(shè)A為攻擊2.3節(jié)隨機(jī)預(yù)言模型下HIBE方案的PPT攻擊者，H為隨機(jī)預(yù)言機(jī)H:({0,1}*)≤d→m×mq.令QH為敵手A對可對H詢問的最大次數(shù)，d為系統(tǒng)可支持的最大分級深度,則存在一個(gè)PPT算法B滿足：如果A是一個(gè)具有優(yōu)勢ε的適應(yīng)性攻擊者(INDr-aID-CPA)，那么).

證明. 已知LWE問題是區(qū)分定義4中預(yù)言機(jī)O的輸出是來自偽隨機(jī)預(yù)言機(jī)Os還是真隨機(jī)預(yù)言機(jī)O$.基于A的能力，構(gòu)造一個(gè)優(yōu)勢是ε的DLWE算法B.

B對預(yù)言機(jī)O進(jìn)行詢問并獲取一組實(shí)例(ui,vi)∈nq×q，其中i=1,2,…,m，要求B通過模擬游戲并基于A的能力區(qū)分出實(shí)例來自預(yù)言機(jī)Os或O$.模擬過程如下：

u0∈nq；選取一個(gè)隨機(jī)整數(shù)φ∈[d]并令因A在n×mq上是均勻的，且是模q可逆的，則A0在n×mq上是均勻的.輸出主公鑰MPK=(A0,u0).

模擬隨機(jī)預(yù)言機(jī). 對于適應(yīng)性的攻擊者A，A能夠在任意時(shí)間適應(yīng)性地選擇任意用戶身份id=id1,id2,…,idi提交給隨機(jī)預(yù)言機(jī)H進(jìn)行詢問.假設(shè)A的詢問是唯一的，否則B對相同的輸入返回相同的內(nèi)容且不增加詢問計(jì)數(shù)器Q的值.令i=|id|為用戶身份的深度，對于A的詢問B的回應(yīng)分2種情況：

3) 運(yùn)行2.3節(jié)HIBE方案中的Derive(MPK,TB,id)算法，利用父身份id|j的陷門矩陣TB派生出子身份id的陷門矩陣.如果j=k，直接運(yùn)行引理5中的RandBasis(TB,σk)算法.輸出并發(fā)送id的陷門矩陣至攻擊者A.

挑戰(zhàn)階段.攻擊者A向模擬者B宣布待攻擊的用戶身份id*并輸出一個(gè)消息比特b*∈{0,1}.要求id*不能是攻擊者A已經(jīng)詢問或即將詢問的用戶身份的父身份.令=|id*|，如果存在i∈[]滿足模擬終止.已知如果φ≠，模擬終止.

假設(shè)φ=且對任意的i∈[]有定義將從預(yù)言機(jī)O獲取到的一組實(shí)例中的v1,v2,…,vm∈q設(shè)為并令mq；利用v0盲化消息位得q/2∈q；發(fā)送挑戰(zhàn)密文至攻擊者A.若O是偽隨機(jī)LWE預(yù)言機(jī)，則q/其中s←nq為均勻隨機(jī)選取的向量，q和mq分別為噪音值和噪音向量，則CT*是利用挑戰(zhàn)身份id*對消息位b*的有效加密密文；若O是真隨機(jī)預(yù)言機(jī)，則(v0,v*)在q×mq上是均勻的，那么挑戰(zhàn)密文在q×mq上也是均勻的.

模擬私鑰派生.該階段與挑戰(zhàn)前階段的前的模擬私鑰派生階段相同，攻擊者A可以繼續(xù)選擇用戶身份進(jìn)行私鑰詢問，模擬者B以同樣的方式進(jìn)行回應(yīng).最后，攻擊者A猜測挑戰(zhàn)密文CT*是否是利用挑戰(zhàn)身份id*對消息位b*的有效加密密文，模擬者B輸出A的猜測并結(jié)束模擬.

由以上可知，主公鑰中參數(shù)的分布與實(shí)際系統(tǒng)中陷門派生算法所需的參數(shù)的分布是相同的.且由引理3可知，對隨機(jī)預(yù)言機(jī)H詢問的回應(yīng)與實(shí)際系統(tǒng)是相同的.如果模擬者B不終止模擬，則挑戰(zhàn)密文CT*的分布在(q×mq)上是獨(dú)立隨機(jī)的或與實(shí)際系統(tǒng)相同.因此，如果模擬者B不終止模擬，則B在區(qū)分DLWE問題上的優(yōu)勢與攻擊者A成功攻擊方案的優(yōu)勢相同.對于PPT攻擊者A來說，A在隨機(jī)預(yù)言機(jī)上發(fā)現(xiàn)碰撞的概率是可忽略的，則模擬者B可進(jìn)行而不終止的概率是Pr[d-negl(n).因此，如果攻擊者A的優(yōu)勢是ε，則模擬者B解決LWE問題實(shí)例的優(yōu)勢至少是[ε).

證畢.

安全性.本文標(biāo)準(zhǔn)模型下的HIBE方案的安全性由定理3刻畫.

證明. 假設(shè)攻擊者A在區(qū)分定義4中預(yù)言機(jī)O的輸出的具有不可忽略的優(yōu)勢，我們基于A的能力構(gòu)造一個(gè)LWE算法B.

B對預(yù)言機(jī)O進(jìn)行詢問并獲取一組實(shí)例(ui,vi)∈nq×q，其中i=1,2,…,m，要求B通過模擬游戲并基于A的能力區(qū)分出實(shí)例來自預(yù)言機(jī)Os或O$.模擬過程如下：

系統(tǒng)建立：模擬者B首先利用實(shí)例(ui,vi)∈nq×q生成隨機(jī)矩陣A∈n×mq，矩陣A的第i列是向量ui，i=1,2,…,m，將向量u0作為公共隨機(jī)向量u0∈nq；然后利用2.2節(jié)優(yōu)化的SampleR算法抽取個(gè)隨機(jī)矩陣m×m，令考慮如下d個(gè)矩陣

模擬私鑰派生：模擬者B利用系統(tǒng)建立階段調(diào)用引理4中的SampleRwithTrap生成的陷門矩陣TAi來回應(yīng)攻擊者A的私鑰詢問.要求攻擊者A詢問的用戶身份不能是目標(biāo)身份id*的父身份.模擬者調(diào)用2.4節(jié)HIBE方案中的Derive(MPK,TAi,id)算法，利用攻擊者所查詢身份的父身份的陷門矩陣TAi派生出所查詢身份的陷門矩陣.如果i=d，直接運(yùn)行引理1中的RandBasis(TAi,σd)算法.輸出并發(fā)送id的陷門矩陣至攻擊者A.

挑戰(zhàn)階段.攻擊者A向模擬者B發(fā)送一個(gè)消息比特b*∈{0,1}，B將從預(yù)言機(jī)O獲取到的一組實(shí)例中的v1,…,vm∈q設(shè)為并令v*∈mq；利用v0盲化消息位得q/2∈q；選取一個(gè)隨機(jī)位r←{0,1}，如果r=0，發(fā)送挑戰(zhàn)密文至攻擊者A，如果r=1，選取一個(gè)隨機(jī)的CT*=(c0,c1)∈q×mq發(fā)送給攻擊者.

猜測階段.在攻擊者A完成又一輪的私鑰詢問后，攻擊者A猜測收到的挑戰(zhàn)密文CT*是來自偽隨機(jī)預(yù)言機(jī)Os還是是真隨機(jī)的預(yù)言機(jī)O$.模擬者B輸出A的猜測結(jié)果作為對LWE問題的求解.

證畢.

4 效率分析

本節(jié)對隨機(jī)預(yù)言模型下和標(biāo)準(zhǔn)模型下的HIBE方案分別進(jìn)行效率分析.為更好地體現(xiàn)本文HIBE方案的優(yōu)越性，我們將HIBE陷門派生前的參數(shù)和計(jì)算效率與派生后的分開進(jìn)行對比.為簡單直觀，我們將派生前和派生后的分級深度設(shè)為=1和=2.

4.1隨機(jī)預(yù)言模型下的HIBE方案效率分析

我們選擇2個(gè)隨機(jī)預(yù)言模型下的HIBE方案作為參照對象：Cash等人[18]于EUROCRYPT 2010提出的隨機(jī)預(yù)言模型下適應(yīng)性安全的首個(gè)格上HIBE方案(簡稱CHKP方案)；Agrawal等人[19]于CRYPTO 2010上提出的一種具有較短密文尺寸且可固定維數(shù)派生的隨機(jī)預(yù)言模型下適應(yīng)性安全的HIBE方案(簡稱ABBa方案).設(shè)安全參數(shù)n=284，q=2的24次方.對比結(jié)果如表4和表5所示，其中RO-adaptive表示該方案滿足隨機(jī)預(yù)言模型下INDr-aID-CPA安全性.

Table 4 Efficiency Comparison of HIBE Schemes Before Trapdoor Delegation Under Random Oracle Model表4 隨機(jī)預(yù)言模型下的HIBE方案陷門派生前效率對比

Table 5 Efficiency Comparison of HIBE Schemes After Trapdoor Delegation Under Random Oracle Model表5 隨機(jī)預(yù)言模型下的HIBE方案派生后效率對比

由表4和表5對比可以看出，相比CHKP方案，ABBa方案和本文方案的主要優(yōu)勢在于陷門派生前后格的維數(shù)保持不變，因此效率參數(shù)如陷門尺寸、用戶公私鑰尺寸、明文-密文擴(kuò)展率以及計(jì)算效率上的原像采樣算法的復(fù)雜度均保持不變.但是，基于固定維數(shù)陷門派生技術(shù)的HIBE方案存在的主要缺點(diǎn)是加密復(fù)雜度較大，原因是：當(dāng)加密者向分級深度為的用戶發(fā)送消息時(shí)，需要計(jì)算個(gè)m×m矩陣的連續(xù)乘積.但優(yōu)點(diǎn)是該運(yùn)算對于每個(gè)用戶身份只需進(jìn)行1次，且與發(fā)送的消息是無關(guān)的.

相比同是固定維數(shù)陷門派生的ABBa方案，本文方案的優(yōu)勢在于具有較低的格的維數(shù).原因在于所采用的MP12陷門生成算法(見引理7)輸出的矩陣A∈n×mq的維數(shù)僅為2nlbq時(shí)，矩陣A的分布與均勻分布的統(tǒng)計(jì)距離即可滿足是安全參數(shù)n的可忽略函數(shù).且陷門生成算法所輸出陷門不再是格Λ⊥(A)的格基，而是從特定概率分布隨機(jī)抽取的短向量組成的陷門矩陣，因此陷門矩陣的尺寸相比表中其他方案較小.此外，低維數(shù)和小的陷門尺寸也是用戶公鑰和私鑰尺寸較短的主要原因.

在陷門生成復(fù)雜度上，相比ABBa方案,本文方案具有明顯的優(yōu)勢.原因在于本文方案在陷門生成過程中不存在計(jì)算代價(jià)高的HNF和矩陣求逆操作，陷門生成的復(fù)雜度僅相當(dāng)于2個(gè)隨機(jī)矩陣的1次乘運(yùn)算；在原像采樣復(fù)雜度上，本文方案是ABBa方案的513倍，原因在于原像采樣算法使用小整數(shù)作為輸入項(xiàng)且支持并行化運(yùn)算，而不是使用輸入項(xiàng)是高精度實(shí)數(shù)的正交化迭代運(yùn)算；在陷門派生上，本文方案比其他方案高效的原因在于，陷門派生算法復(fù)雜度主要取決于所調(diào)用的SampleR算法(見引理6)和RandBasis算法(見引理1)，而它們效率的根本都取決于所調(diào)用的原像采樣算法.在2.2節(jié)我們分析所調(diào)用的原像采樣算法的時(shí)間復(fù)雜度相比通常原像采樣算法的Ω(n2lb2n)可降至O(nlbcn)，且基于固定維數(shù)派生陷門算法的HIBE方案的陷門派生復(fù)雜度不會隨系統(tǒng)分級深度的增長而變高.

4.2標(biāo)準(zhǔn)模型下的HIBE方案效率分析

Table 7 Efficiency Comparison of HIBE Schemes After Trapdoor Delegation Under Standard Model表7 標(biāo)準(zhǔn)模型下的HIBE方案派生后效率對比

在陷門派生上，對于固定維數(shù)派生的HIBE方案，由于ABBa和WWL方案均基于ABBa中提出的時(shí)間復(fù)雜度是Ω(n3lb3n)的SampleR算法，本文方案采用2.2節(jié)優(yōu)化后的SampleR算法可將算法時(shí)間復(fù)雜度降至O(n2lbcn)，c為常數(shù)；對于非固定維數(shù)派生的HIBE方案，其時(shí)間復(fù)雜度與格的維數(shù)緊密相關(guān).由表7可以看出，在系統(tǒng)分級深度僅為2時(shí)，本文方案相比ABBb方案已有6倍的提升，且基于固定維數(shù)派生的HIBE方案因?yàn)楦竦木S數(shù)在陷門派生前后不變，因此陷門派生的時(shí)間復(fù)雜度不受系統(tǒng)分級深度的影響.

綜上所述，相比同類方案，本文方案在隨機(jī)預(yù)言模型和標(biāo)準(zhǔn)模型下的陷門派生復(fù)雜度有效降低，且方案的效率參數(shù)和計(jì)算效率整體有所提高.因此，本文方案總體上是較高效的.

5 總 結(jié)

為解決格上基于固定維數(shù)陷門派生技術(shù)的HIBE方案中陷門派生復(fù)雜度過高的問題，本文提出一種高效的q可逆矩陣提取算法，并基于該算法結(jié)合固定維數(shù)的陷門派生算法和MP12陷門函數(shù)分別在隨機(jī)預(yù)言模型和標(biāo)準(zhǔn)模型下給出2種改進(jìn)方案.方案安全性均歸約至LWE問題的難解性，其中基于隨機(jī)預(yù)言模型的HIBE方案的安全性滿足IND-aID-CPA安全，基于標(biāo)準(zhǔn)模型的HIBE方案安全性滿足IND-sID-CPA安全.對比分析表明，格上基于固定維數(shù)派生技術(shù)HIBE方案中陷門派生復(fù)雜度過高的問題得到有效解決，且在其他效率參數(shù)和計(jì)算效率上整體提升.

本文方案的不足在于標(biāo)準(zhǔn)模型下方案安全性僅滿足IND-sID-CPA安全，如何構(gòu)造標(biāo)準(zhǔn)模型下IND-aID-CPA安全的格上HIBE方案是值得進(jìn)一步研究的問題.

[1] Shamir A. Identity-based crypto systems and signature schemes[C] //Proc of CRYPTO 1984. Berlin: Springer, 1984: 47-53

[2] Boneh D, Franklin M. Identity-based encryption from the weil pairing[C] //Proc of CRYPTO 2001. Berlin: Springer, 2001: 213-229

[3] Waters B. Efficient identity-based encryption without random oracles[C] //Proc of EUROCRYPT 2005. Berlin: Springer, 2005: 114-127

[4] Lai Junzuo, Deng R H, Liu Shengli, et al. Identity-based encryption secure against selective opening chosen-ciphertext attack[C] //Proc of EUROCRYPT 2012. Berlin: Springer, 2012: 77-92

[5] Yamada S. Adaptively secure identity-based encryption from lattices with asymptotically shorter public parameters[C] //Proc of EUROCRYPT 2016. Berlin: Springer, 2016: 32-62

[6] Wang Fenghe, Liu Zhenhua, Wang Chunxiao. Full secure identity-based encryption scheme with short public key size over lattices in the standard model[J]. International Journal of Computer Mathematics, 2016, 93(6): 854-863

[7] Regev O. On lattices, learning with errors, random linear codes, and cryptography[J]. Journal of the ACM, 2009, 56(6): 84-93

[8] Nguyen P, Zhang Jiang, Zhang Zhenfeng. Simpler efficient group signatures from lattices[C] //Proc of Public-Key Cryptography. Berlin: Springer, 2015: 401-426

[9] Libert B, Ling San, Nguyen K, et al. Zero-knowledge arguments for lattice-based accumulators: Logarithmic-size ring signatures and group signatures without trapdoors[C] //Proc of EUROCRYPT 2016. Berlin: Springer, 2016: 1-31

[10] Brakerski Z, Perlman R. Lattice-based fully dynamic multi-key FHE with short ciphertexts[C] //Proc of CRYPTO 2016. Berlin: Springer, 2016: 190-213

[11] Zhang Yanhua, Hu Yupu. A new verifiable encrypted signature from lattices[J]. Journal of Computer Research and Development, 2017, 54(2): 305-312 (in Chinese)

(張彥華, 胡予濮. 新的基于格的可驗(yàn)證加密簽名方案[J]. 計(jì)算機(jī)研究與發(fā)展, 2017, 54 (2): 305-312

[12] Gentry C, Peikert C, Vaikuntanathan V. Trapdoors for hard lattices and new cryptographic constructions[C] //Proc of the 40th ACM Symp on Theory of Computing. New York: ACM, 2008: 197-206

[13] Ajtai M. Generating hard instances of the short basis problem[C] //Proc of Int Colloquium on Automata, Languages and Programming. Berlin: Springer, 1999: 1-9

[14] Agrawal S, Boyen X, Vaikuntanathan V, et al. Functional encryption for threshold functions (or fuzzy IBE) from lattices[C] //Proc of Public Key Cryptography. Berlin: Springer, 2012: 280-297

[15] Ducas L, Lyubashevsky V, Prest T. Efficient identity-based encryption over NTRU lattices[C] //Proc of ASIACRYPT 2014. Berlin: Springer, 2014: 22-41

[16] Katsumata S, Yamada S. Partitioning via non-linear polynomial functions: More compact IBEs from ideal lattices and bilinear maps[C] //Proc of ASIACRYPT 2016, Berlin: Springer, 2016: 682-712

[17] Zhang Jiang, Chen Yu, Zhang Zhenfeng. Programmable hash functions from lattices: Short signatures and IBEs with small key sizes[C] //Proc of CRYPTO 2016. Berlin: Springer, 2016: 302-332

[18] Cash D, Hofheinz D, Kiltz E, et al. Bonsai trees, or how to delegate a lattice basis[C] //Proc of EUROCRYPT 2010. Berlin: Springer, 2010: 523-552

[19] Agrawal S, Boneh D, Boyen X. Efficient lattice (H) IBE in the standard model[C] //Proc of EUROCRYPT 2010. Berlin: Springer, 2010: 553-572

[20] Agrawal S, Boneh D, Boyen X. Lattice basis delegation in fixed dimension and shorter-ciphertext hierarchical IBE[C] //Proc of CRYPTO 2010. Berlin: Springer, 2010: 98-115

[21] Micciancio D, Peikert C. Trapdoors for lattices: Simpler, tighter, faster, smaller[C] //Proc of EUROCRYPT 2012. Berlin: Springer, 2012: 700-718

[22] Alwen J, Peikert C. Generating shorter bases for hard random lattices[C] //Proc of the 26th Int Symp on Theoretical Aspects of Computer Science. Berlin: Springer, 2009: 535-553

[23] Micciancio D, Goldwasser S. Complexity of Lattice Problems: A Cryptographic Perspective [G] //The International Series in Engineering and Computer Science: 671. Berlin: Springer, 2002

[24] Wang Fenghe, Wang Chunxiao, Liu Zhenhua. Efficient hierarchical identity based encryption scheme in the standard model over lattices[J]. Frontiers of Information Technology & Electronic Engineering, 2016, 17(8): 781-791

EfficientHierarchicalIdentity-BasedEncryptionSchemefromLearningwithErrors

Ye Qing, Hu Mingxing, Tang Yongli, Liu Kun, and Yan Xixi

(SchoolofComputerScienceandTechnology,HenanPolytechnicUniversity,Jiaozuo,Henan454000)

Hierarchical identity-based encryption (HIBE) in fixed dimension has drawn wide attention because its lattice dimension keeps unchanged upon delegation, but there is a common defect of high complexity in trapdoor delegation stage of these schemes. Aiming at this problem, we propose two improved HIBE schemes under random oracle model and standard model respectively. We first use the MP12 trapdoor function to construct an optimizedq-invertible matrix sample algorithm. Based on this optimized algorithm, combined with trapdoor delegation algorithm in fixed dimension and MP12 trapdoor function, we design system setup and trapdoor delegation stages. And we complete the HIBE scheme under random oracle model in conjunction with Dual-Regev algorithm. And then, we remove the random oracle by employing binary tree encryption system. The security of both proposed schemes strictly reduce to the hardness of learning with errors (LWE) problem, in which the scheme under random oracle model satisfies the adaptive security while the scheme under standard model satisfies selective security. Comparative analysis shows that, under the same security level, the overhead of trapdoor delegation in our scheme under random oracle model is reduced significantly compared with the relevant schemes, while the overhead of our scheme under standard model is reduced nearly 6 times compared with the relevant optimal schemes. Furthermore, the parameters such as lattice dimension, trapdoor size and ciphertext expansion rate etc., all decrease in some degree, and the computational cost is reduced obviously.

lattice; hierarchical identity-based encryption (HIBE); trapdoor delegation; learning with errors (LWE); random oracle model; standard model

TP309

YeQing, born in 1981. Associate professor at Henan Polytechnic University. Received her PhD degree from Beijing University of Posts and Telecommunications. Her main research interests include lattice cryptography and algebra.

HuMingxing, born in 1994. Master candidate in School of Computer Science and Technology, Henan Polytechnic University. His main research interests include information security and lattice cryptography.

TangYongli, born in 1972. Professor at Henan Polytechnic University. Senior member of CCF. Received her PhD degree from Beijing University of Posts and Telecommunications. His main research interests include information security and cryptography.

LiuKun, born in 1978. Associate professor at Henan Polytechnic University. Received her MSc degree from Chongqing University of Posts and Telecommunications. Her main research interests include cryptography and number theory.

YanXixi, born in 1985. Associate professor at Henan Polytechnic University. Received her PhD degree from Beijing University of Posts and Telecommunications. Her main research interests include lattice cryptography and algebra.