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

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

(河南理工大學計算機科學與技術學院 河南焦作 454000)(yeqing@hpu.edu.cn)

2017-06-05；

2017-07-28

國家自然科學基金項目(61300216)；河南省科技廳基礎與前沿技術研究計劃項目(142300410147);河南省教育廳自然科學研究項目(12A520021)；河南省教育廳高等學校重點科研項目(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的高效身份基分級加密方案

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

(河南理工大學計算機科學與技術學院 河南焦作 454000)(yeqing@hpu.edu.cn)

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

格；基于身份的分級加密；陷門派生；容錯學習；隨機預言模型；標準模型

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

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

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

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

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

1 預備知識

1.1格的相關定義

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

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

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

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

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

1.2相關算法和困難問題

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

定義4[7]. 容錯學習(learning with errors, LWE)問題. 設n為正整數，q為素數，對任意0<α≤1ω()，定義Ψα為中心是0、標準差是α的[0,1)上的正態分布，對應的q上的離散分布為為q上的容錯分布，(q,n)-LWE問題實例由未指明的挑戰預言機O構成：預言機O是帶噪音的偽隨機預言機Os或者是真隨機的預言機O$，2種預言機的輸出分別如下：

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

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

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

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

引理6[20]. SampleR算法.與引理1參數相同，設T是格m的格基，利用與引理8類似的原像采樣算法隨機抽取m個向量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參數相同，令H∈n×nq為可逆矩陣，G∈n×wq是構造公開的矩陣.選取一個均勻隨機矩陣q，存在概率多項式時間(probabilistic polynomial time, PPT)算法輸出矩陣‖HG-n×mq和陷門矩陣TA0=[a1‖a2‖…‖aw]∈，陷門尺寸s1(TA0)≤×ω()，其中A0在n×mq上是統計均勻的，TA0是矩陣A0的陷門.

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

2 算法設計及方案構造

2.1符號說明

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

Table 1 Notations Description表1 符號說明

2.2優化的SampleR算法

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

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

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

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

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

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

2.3隨機預言模型下的HIBE方案

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

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

2.4標準模型下的HIBE方案

HIBE-Derive(MPK,SKi d|,id)：輸入主公鑰MPK；輸入SKi d|表示系統分級深度為時用戶公鑰矩陣Ai d|所對應的陷門矩陣，其中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.調用2.3節的陷門派生算法輸出陷門矩陣SKi d=S′.

3 安全性證明

通常，一個HIBE方案的安全性需滿足選擇身份攻擊和選擇明文攻擊下的密文不可區分性(IND-ID-CPA)，根據安全強度不同，分為適應性選擇身份選擇明文攻擊(IND-aID-CPA)和選擇性選擇身份選擇明文攻擊(IND-sID-CPA).本文方案在隨機預言模型下滿足IND-aID-CPA安全，在標準模型下滿足IND-sID-CPA安全.

本方案采用Agrawal等人[19]在EEUROCRYPT 2010上提出的格上HIBE方案的INDr-s/aID-CPA安全模型進行安全性證明，該安全模型不僅可證明IND-s/aID-CPA安全，還可以保護接收方的匿名性，且主公鑰的私密性可被其創建的密文保護.基于該安全模型進行安全證明的還有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 標準模型下HIBE方案的參數設置

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

證畢.

安全性. 本文隨機預言模型下的HIBE方案的安全性由定理2刻畫.

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

證明. 已知LWE問題是區分定義4中預言機O的輸出是來自偽隨機預言機Os還是真隨機預言機O$.基于A的能力，構造一個優勢是ε的DLWE算法B.

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

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

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

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

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

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

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

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

證畢.

安全性.本文標準模型下的HIBE方案的安全性由定理3刻畫.

證明. 假設攻擊者A在區分定義4中預言機O的輸出的具有不可忽略的優勢，我們基于A的能力構造一個LWE算法B.

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

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

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

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

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

證畢.

4 效率分析

本節對隨機預言模型下和標準模型下的HIBE方案分別進行效率分析.為更好地體現本文HIBE方案的優越性，我們將HIBE陷門派生前的參數和計算效率與派生后的分開進行對比.為簡單直觀，我們將派生前和派生后的分級深度設為=1和=2.

4.1隨機預言模型下的HIBE方案效率分析

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

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

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

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

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

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

4.2標準模型下的HIBE方案效率分析

Table 7 Efficiency Comparison of HIBE Schemes After Trapdoor Delegation Under Standard Model表7 標準模型下的HIBE方案派生后效率對比

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

綜上所述，相比同類方案，本文方案在隨機預言模型和標準模型下的陷門派生復雜度有效降低，且方案的效率參數和計算效率整體有所提高.因此，本文方案總體上是較高效的.

5 總 結

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

本文方案的不足在于標準模型下方案安全性僅滿足IND-sID-CPA安全，如何構造標準模型下IND-aID-CPA安全的格上HIBE方案是值得進一步研究的問題.

[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)

(張彥華, 胡予濮. 新的基于格的可驗證加密簽名方案[J]. 計算機研究與發展, 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.