標準模型下格上基于身份的門限解密方案

吳立強 楊曉元,2 張敏情

1(武警部隊網絡與信息安全保密重點實驗室(武警工程大學) 西安 710086)2(網絡信息安全教育部重點實驗室(西安電子科技大學) 西安 710071)

門限解密體制是將秘密共享方法和加密算法有效結合.在(t，N)門限解密體制中，N個解密服務器共享解密私鑰，當對密文進行解密時，至少需要t個服務器共同參與并返回相應的解密份額，才能正確恢復出密文所對應的明文.然而，少于t個或更少的服務器無法獲取關于明文的任何信息.門限解密體制能夠降低或避免因個體完全掌握解密密鑰而導致的濫用權限、密鑰丟失，或某個服務器被攻擊者完全控制而造成系統癱瘓等安全風險，使系統的容錯率和安全性得到較大提高.

傳統公鑰加密體制必須明確公鑰與其擁有主體的對應關系.1984年，Shamir創造性地引入了基于身份密碼學(identity-based encryption, IBE)，在該體制中，公鑰直接就是其擁有者的身份信息，如手機號碼、Email等，這種公鑰密碼體制天然地確定了公鑰與實體之間的綁定關系，無需借助可信第三方，因此簡化了繁瑣的證書管理環節，具有較強的實用性.

將基于身份的思想引入到門限解密環境中，某個身份所對應私鑰的持有者不再是某個單一個體，而可能是多個實體.比如某個公司的總經理，當他不能處理以公司名義加密的文件時，他可以選擇將解密私鑰分割并分發給公司的3個副經理，當且僅當其中的2個副經理合作才能夠解密公司的文件，而任何1個副經理是無法獨自解密的.這樣的機制，一方面限制了某個副經理獨自解密的過大權限，另一方面即使在某一個副經理缺席的情況下，仍然能夠正常處理公司業務.

在基于身份的門限解密系統中，非交互性和可驗證性是2個重要屬性.非交互性是指解密服務器在解密過程中不需要相互進行數據交換.可驗證性是指可公開驗證密文的合法性.如果一個基于身份的門限解密方案滿足上述2個性質，那么每一個解密服務器只需要使用自己的私鑰份額即可完成解密，而無需通過某種交互機制來驗證密文份額合法性，從而使方案更為簡潔和高效.

本文通過借鑒利用雙線性映射構造基于身份門限解密的方法，采用格上陷門產生函數生成系統主密鑰，采用左右基擴展技術為用戶生成私鑰，私鑰本身是身份所對應的陷門.在秘密分割時，沒有對用戶私鑰進行直接分割，而是采用拉格朗日方法對一個公共向量進行分割，得到每個解密服務器的特征向量.通過用戶擁有的私有陷門，對特征向量進行原像抽樣，得到私鑰份額，有效隱藏了用戶完整私鑰，從而使其更為安全.在解密份額的驗證中，采用離散對數問題的難解性，保證其可公開驗證性.在解密份額組合時，通過公共向量拆分合并和解密份額拆分合并之間運算的同態性，保證方案解密的正確性.在標準模型下，將該方案的安全性規約為判定性LWE困難假設，證明了其能夠滿足IND-sID-CPA安全.同現存的格上基于身份的門限加密方案相比，本文是對滿足均勻分布的向量進行分割，安全性更高，同時證明過程在標準模型下完成.

1 相關工作

門限密碼體制起源于著名密碼學家Shamir和Blakley提出的(t,N)門限秘密共享方法[1-2].前者采用多項式插值的方法設計了門限秘密共享方案，而后者則使用了有限幾何方法.Boneh等人[3]最早將門限思想引入到了基于身份的加密中.其初衷是解決密鑰管理中心PGK完全掌握系統主私鑰，從而造成權限過大的問題，主要方法是將主PKG的系統主密鑰采用秘密分割方法分發給了N個分PKG，每個分PKG為用戶生成部分私鑰份額，至少需要t個分PKG產生的私鑰份額，才能構成用戶的完整私鑰，完成解密功能，因此該機制也稱為分布式PKG.2006年，Boneh等人[4]擴展了這種思想，構造了基于身份的(t,N)門限加密體制(threshold iden-tity-based encryption, TIBE).之后，考慮到分PKG也可以執行解密的功能，因而解密操作由原來的用戶端轉移到了分PKG上，但是這種機制存在2個弊端：1)要求分PKG必須實時在線處理解密請求;2)如果可用的PKG數量不足t個，就無法完成解密.

因此，Baekand和Zheng認為[5]：在基于身份密碼學中，對用戶私鑰進行分割比對系統主密鑰進行分割更為合適，每個解密服務器擁有用戶部分私鑰，可直接解密基于身份的密文，得到解密份額，合并這些解密份額即可恢復出明文.利用這種思路，他們提出了基于身份的門限解密方案(identity-based thre-shold decryption, IBTD)，并基于雙線性對，構造了一個選擇密文攻擊安全的基于身份門限解密方案，同時將其擴展為了一個可仲裁的身份加密方案.文獻[6-7]分別構造了選擇明文攻擊安全的IBTD方案.

上述IBTD方案都是基于雙線性映射實現.量子計算具有天然的并行性，其超強的計算能力，可用于密碼破譯.特別是 Shor量子算法，可對目前廣泛使用的、基于經典困難問題構造的公鑰密碼方案進行有效攻擊，嚴重威脅其安全性.在目前已知的抗量子攻擊候選密碼體制中，基于格上困難問題設計的密碼體制[8]，不但能夠抵抗Shor算法攻擊，而且具有最困難實例與一般實例等價、高效易實現等優勢，是后量子密碼中最典型的代表，已經成為當前密碼學領域研究的熱點.

在利用格上困難問題，構造門限加解密方面，已有部分成果.Bendlin等人[9]利用Regev加密系統[10]，構造了第一個格上門限公鑰加密方案，其安全性能夠規約到格上困難問題的最難實例.Xie等人[11]利用有損陷門函數，給出了一種高效門限加密方案的構造方法，并利用格工具進行了實例化.Singh等人[12]提出了一個高效的TPKE 方案，其滿足可重拆分屬性，即如果拆分算法輸出腐化私鑰份額的數量小于t，則私鑰的拆分能進行任意多項式次.

上述這些格上TPKE都是非基于身份環境下的.2014年，Singh等人[13]將格上門限解密方案[12]擴展到了基于身份環境中，構造了格上第1個基于身份的門限解密方案.在該方案中，用戶身份所對應的私鑰滿足正態分布，直接對于該私鑰進行分割，每個參與者獲得一個私鑰份額，當需要解密時，采用私鑰份額進行解密得到解密份額，合并即可恢復出明文.文獻[14]在標準模型下，基于LWE困難問題，采用Shamir門限秘密共享的方法，構造了一種標準模型下選擇身份安全的模糊身份加密方案(fuzzy identity based encryption, FIBE)，即當用戶公鑰屬性集與加密公鑰屬性集的交集等于或大于規定的門限值時，可正常解密.文獻[15]基于格上困難問題提出了一種基于身份的門限加密方案，同時利用通用轉化方法，得到了一種帶關鍵字的密文搜索加密方案.

當前，格與雙線性是設計密碼方案的兩大重要工具，雙線性對映射群具有靈活代數結構，已經存在很多成熟的關鍵技術、安全模型、證明方法，而格密碼學主要依賴于線性運算及巧妙的陷門設計，且具有抗量子攻擊的性能，因此，將格這一新興的密碼學工具與成熟的雙線性密碼方案構造方法相結合，可以有效推動格密碼學的發展.本文工作就是基于這樣的思路展開.

2 預備知識

定義[j]={1,2,…,j}，表示整數.假設a,b,c表示列向量，用A,B,C表示矩陣.對矩陣A和B，符號[A|B]代表他們橫向聯結，[A;B]表示縱向聯結.表示從N個不同元素中取出t個元素的組合數.

2.1 格和LWE假設

定義1. 整數格.設B=[b1,b2,…,bm]∈n×m是一個矩陣，其列向量b1,b2,…,bm∈n線性無關，B生成的n維滿秩格為

L(B)={y∈ns.t. ?s∈m,

對于素數q，A∈和u∈格定義為

Λq(A)={e∈ms.t. ?s∈滿足ATs=e(modq)};

定義3. LWE問題[10].包括計算性LWE問題和判定性LWE問題.

計算性LWE問題：選取一個公開參數n>1,一個模數q≥2，定義噪聲概率分布為ψs=D，秘密選取均勻分布的向量s∈隨機選取均勻分布的向量A∈和輸出樣本(A,ATs+e)∈如果存在一個算法，能夠利用給定的若干個樣本以很大的概率恢復出s∈那么該算法能夠解決計算性LWE問題.

判定性LWE問題：存在一個敵手A和LWE預言機O，該預言機包含2個抽樣算法OS(根據LWE分布輸出樣本(A,ATs+e)∈其中隨 機選擇矩陣A∈選擇服從分布的e∈選擇服從均勻分布的s∈實際上，同樣可以被證明是安全的)和O$(從均勻分布U(中輸出一個隨機樣本)，如果A可以解決判定性LWE問題當且僅當優勢

Adv(A)=|Pr[AOS=1]-Pr[AO$=1]|

是不可忽略的.

下面的定理將LWE困難假設規約到了格上經典困難問題.

2.2 相關的函數和數學工具

1) 陷門產生函數

2) 抽樣算法

引理1[16]. 假設q>2，整數m>n，矩陣A∈，TA是格的一個陷門，且那么，對于c∈m和u∈

② 對于任意的u∈存在多項式時間內的隨機原像抽樣算法SamplePre(A,TA,u,σ)，能夠返回一個統計上服從分布的向量

3) 左采樣基算法

在HIBE方案中[16]，左采樣基算法使用一個低維格的陷門生成一個更高維數格的陷門，從而實現格基授權.具體方法是利用矩陣A的陷門TA進行多次采樣，形成一個擴展矩陣的短基.根據引理1中第④條，這些短基是滿秩的且尺寸較短，可以作為陷門，為更高維數的矩陣進行抽樣.

算法1. 左抽樣基算法SampleBasisLeft(A0,A1+H(id)B,TA,σ).

輸出：身份Fi d=(A0|A1+H(id)B)的陷門Ti d～D，滿足Fi d·Ti d=0.

① 隨機選取統計服從D分布的e1∈m；

② 計算u1=(A1+H(id)B)·e1；

③e2=SamplePre(A0,TA,-u1,σ)∈m×n；

④ 設置e=(e2,e1)，重復上述過程，直到得到2m個線性無關向量；

⑤ 將上述2m個向量組合成Ti d∈2m×2m.

4) 身份編碼

定義4. 假設q是素數，n是一個整數，定義身份編碼函數H:差分滿秩編碼函數，它具有2個性質[16]：

① 對于所有不同的身份g1,g2∈矩陣H(g1)-H(g2)∈是滿秩的;

②H的計算能夠在多項式時間內完成.

5) Shamir的(t,N)門限方案

使用Shamir的(t,N)門限方案分享一個秘密S的過程為：

① 隨機選擇t-1個系數a1,a2,…,at-1∈q.

② 構造一個t-1階多項式函數：

f(x)=S+a1x+a2x2+…+at-1xt-1.

③ 定義用戶的編號為1,2,…,N，對于1≤i≤N，計算每個份額Si=f(i)，并發送Si給第i個用戶.

④ 當用戶的有效份額數達到門限值t時，函數f(x)可以被重構:

其中，Mj表示Lagrange系數：

那么，秘密S=f(0)，秘密被恢復.

Shamir門限方案具有一些優良性質:

① 完善性.對于每個秘密S，當份額數量大于或者等于t個，有且僅有唯一的一個t-1次多項式滿足條件；而少于t個份額得不到關于S的任何有用信息.

② 同態性.

Ⅰ.如果對所有的秘密份額Si(1≤i≤N)都相加或者相乘一個常數，那么新的秘密相當于原來秘密S與這個常數相加或者相乘.

Ⅱ.如果存在2個秘密值S和T，選擇的多項式是分別是f(x)和g(x)，相應的份額分別為f(1),f(2),…,f(N)和g(1),g(2),…,g(N).定義一個新的秘密份額為h(j)=f(j)+g(j), 1≤j≤N，那么這些新份額可重構出秘密f(0)+g(0)=S+T.

6) 離散對數問題

定義5. 離散對數(discrete logarithm, DL)假設. 循環群G1的階是素數p，G1的生成元是g.離散對數(DL)問題是指，給定二元組(g,ga)，求出a的值，其中a∈該問題在密碼學的典型離散對數群上是困難問題，設敵手為A，則:

2.3 相關定義和安全模型

1) TIBE的定義

定義6. 一個基于身份的門限解密IBTD方案包含7個算法：

① 系統初始化算法Setup.輸入安全參數λ，密鑰生成中心PKG輸出公共的系統參數pp，以及主私鑰msk.

② 密鑰生成算法KeyGen.輸入一個用戶身份id，以及PKG私鑰msk，輸出用戶私鑰Si d.

③ 私鑰分割算法DisKey.輸入一個身份id和對應私鑰Si d，解密服務器的個數N，以及門限參數t.該算法生成id對應的N個私鑰份額TSKi d,i(1≤i≤N).同時，為了能夠驗證各個解密服務器輸出的解密份額是否有效，還應當生成與秘密份額TSKi d,i相對應的驗證信息TVKi d,i.注意，TSKi d,i被秘密交給對應的第i個解密服務器，而TVKi d,i(1≤i≤N)公開.

④ 加密算法Enc.輸入一個用戶的身份id和待加密的明文M，輸出密文C.

⑤ 部分解密算法SubDec.輸入一個密文C，解密服務器i的私鑰份額TSKi d,i和TVKi d,i，輸出一個解密份額θi.

⑥ 份額驗證算法ShareVery.輸入一個密文C，解密服務器i的解密份額θi，以及驗證密鑰TVKi d,i，驗證θi是否為有效的解密份額，如果無效，則算法輸出“⊥”.否則，驗證通過.

⑦ 聯合算法Combine.輸入至少t個解密份額{θi,C},i∈S,S∈{1,2,…,N},|S|≥t.首先檢測θi的有效性，如果無效，返回“⊥”.否則聯合t個有效解密份額，輸出解密結果M.

定義7. IBTD方案的IND-sID-CPA(Indist-inguishability of ciphertexts under a selective-identity chosen-plaintext attack)安全性.其是根據攻擊者A和挑戰者C之間的游戲定義的.

初始化.攻擊者A輸出準備要攻擊的身份id*和一個腐化的解密服務器集合S∈{1,2,…,t-1}.

設置.挑戰者C運算Setup(λ)，將獲取的公開參數給攻擊者，自己保留系統主私鑰.

第1階段詢問：

① 私鑰詢問，攻擊者A詢問身份id(id≠id*)所對于的私鑰Si d，挑戰者C運行KeyGen算法并將結果Si d返回給A.

② 私鑰份額詢問，當被詢問用戶id的第i個解密份額時，C運行ShareKeyGen(id,Si d,N,t)算法獲取私鑰份額TSKi d,i(1≤i≤N)，和相應的門限驗證密鑰TVKi d,i，如果(id≠id*)或者(id=id*,i∈S)，那么挑戰者返回相應份額給攻擊者，否則輸出“⊥”.

挑戰階段.攻擊者A輸出2個等長的消息M0,M1(M0≠M1)，挑戰者隨機選擇一個b∈{0,1},并計算挑戰密文C*=Encrypt(id,Mb)，將其發送給A.

第2階段詢問.與第1階段相同.

猜測.攻擊者A給出一個對b值的猜測b′∈{0,1}，如果b′=b那么攻擊者獲勝.

攻擊者A在上述游戲中的優勢為

①S和S′在身份id*和TVKi d*下都是合法份額;

②S和S′中解密份額來自t個不同解密服務器;

③Combine(TVKi d*,id*,S,C)≠Combine(TVKi d*,id*,S′,C);

3 方案描述

1) 系統設置Setup(λ)

輸入安全參數λ，設置n∈，q=ploy(n)，m=O(nlogq).

① 根據TrapGen算法，PKG生成隨機均勻分布的矩陣A0∈和陷門

② 選擇2個均勻分布的矩陣A1∈和B∈,選擇一個均勻分布的向量u∈

③ 選擇身份編碼函數H:

④ 定義映射函數φ:{0,1}m+1×{0,1}*→q，其輸入為密文C和密鑰KA，其輸出為之間的隨機值.

⑤ 選擇一個素數p使得離散對數問題在以g為生成元的循環群p上是困難的.

2) 私鑰提取Extract(msk,pp,id)

輸入用戶id∈和系統主密鑰利用身份編碼函數計算H(id)∈則id對應公鑰為Fi d=(A0|A1+H(id)B).使用左基采樣算法計算Fi d對應的陷門Ti d∈滿足Fi d·Ti d=0，且Ti d服從噪聲分布

返回私鑰Ti d給用戶id.

3) 私鑰分割算法DisKey(id,Ti d,N,t)

給定解密服務器數量N、門限值t和公共參數pp，標記u=(u1,u2,…,un)∈

① 隨機選擇n個多項式li(x)←q[x] (1≤i≤n) 滿足最高次數等于t-1且li(0)=ui.對于1≤i≤N，第i個解密服務器的特征向量為ui d,i=(l1(i),l2(i),…,ln(i)).

② 對于1≤i≤N，利用陷門Ti d，采用SamplePre(Fi d,Ti d,ui d,i,2σ)算法抽取出ei d,i∈滿足Fi d·ei d,i=ui d,i，那么第i個服務器擁有的用戶id部分私鑰份額為TSKi d,i=ei d,i，并將其表示為向量ei d,i=(ei d,i,1,ei d,i,2,…,ei d,i,2m)，驗證份額為TVKi d,i=(gei d,i,1,gei d,i,2,…,gei d,i,2m).

所有解密服務器對于用戶id的門限驗證密鑰為TVKi d=(TVKi d,1,TVKi d,2,…,TVKi d,N)，其可以公開.

4) 加密算法Enc(id,M)

① 計算id的公鑰Fi d=(A0|A1+H(id)B)；

② 隨機選擇均勻分布的s∈

③ 選擇均勻分布的矩陣R∈其系數隨機取自{-1,1};隨機選取噪聲分布x∈ψs和噪聲計算

5) 部分解密算法SubDec(TSKi d,i,C=(c1,c2))

利用私鑰份額TSKi d,i，計算出密文C所對應的解密份額，過程如下.

6) 份額驗證算法ShareVery(TVKi d,i,θi,C)

利用驗證密鑰TVKi d,i，驗證解密份額θi是否為密文C的合法解密份額.

7) 組合算法Combine(TVKi d,C,θ1,θ2,…,θt)

t個解密服務器，構成集合S，他們的解密份額分別為θ1,θ2,…,θt，利用這些份額可以恢復出密文C所對于的明文信息，過程如下.

① 對于每一個解密份額θi(1≤i≤t)，如果ShareVery(TVKi d,i,θi,C)驗證失敗，輸出 “⊥”，并退出.

輸出消息M′.

4 方案分析

4.1 正確性

定理3. 對于任意的實數s>0,T>0和x∈n，有

定理4. 選擇合適的參數，在新的IBTD方案中，解密份額能夠通過驗證，且解密算法能夠正確還原出消息.

證明.

1) 驗證算法的正確性.

2) 解密結果的正確性.

來自服務器i的部分解密份額為Mi=di+xi.根據解密份額合成算法, 在獲取t個這樣的份額后，根據拉格朗日運算的同態性質，計算

要解密正確，只需要

要解密正確，只需要noise的3部分之和不超過

4.2 安全性證明

先介紹安全性證明過程中需要使用的引理2和定理5.

引理2. 假設mn>(n+1)logq+ω(logn),其中q是一個素數，矩陣A∈是一個m×m方陣，其值隨機取自{-1,1},那么(A,AR)的分布在統計上與分布(A,B)不可區分.

定理5. 在二維平面上給定t個點(x1,y1),(x2,y2),…,(xt,yt)，其中xi的值各不相同，那么存在且唯一存在最高次數為t-1的多項式f，對于所有的點(xi,yi)(1≤i≤t)，滿足f(xi)=yi.

定理6. 安全性.如果LWE問題是困難的，那么上述基于格的IBTD方案可以滿足IND-sID-CPA安全性.

證明. 證明過程分2步：證明密文滿足語義安全和證明解密一致性.

語義安全性證明.先構造一系列游戲，第一個游戲是真實的IND-sID-CPA攻擊，而最后一個游戲是攻擊者無法獲勝的；然后基于一些格上的困難性假設，證明相鄰游戲之間在多項式時間內不可區分.

Game0.攻擊者A和挑戰者C之間真實的IND-sID-CPA游戲，設攻擊者A輸出準備要攻擊的身份id*和一個已經腐化的解密服務器集合S∈{1,2,…,t-1}.挑戰者運算Setup算法，將獲取的公開參數給攻擊者A，自己保留系統主私鑰msk.且如下回答攻擊者的詢問.

1) 私鑰詢問，攻擊者A詢問身份id(id≠id*)所對應的私鑰Ti d，挑戰者運行KeyGen算法并將結果Ti d返回給挑戰者.

2) 私鑰份額詢問，當被詢問用戶id的第i個解密份額時，挑戰者運行ShareKeyGen(id,Ti d,N,t)算法獲取門限份額密鑰TSKi d,i(1≤i≤N)，和相應的門限驗證密鑰TVKi d,i(1≤i≤N)，如果(id≠id*)或者(id=id*,i∈S)，那么挑戰者返回相應的份額給攻擊者，否則輸出“⊥”.

Game1. 在Game0中，挑戰者公開的系統參數A1取自均勻分布，Game1中環多項式A1不再是隨機選取，而是通過A1=A0R*-H(id*)B計算得到，R*為加密階段選取的隨機向量，其余參數的選取與Game0相同.

Game0到Game1：對多項式時間內的攻擊者A而言，Game0和Game1概率不可區分，使用引理2可以證明.

Game2. 對Game1中參數進行如下修改，A0在q上隨機均勻選取，不含陷門.利用陷門函數產生含有陷門TB的B∈那么，用戶id對應的身份矩陣為Fi d=(A0|A0R*+(H(id)-H(id*))B).挑戰者擁有的系統主密鑰為TB.其在挑戰階段如此回答詢問.

1) 私鑰詢問，攻擊者詢問身份id(id≠id*)所對應的私鑰Ti d，挑戰者運行右采樣基算法Ti d←SampleBasisRight(A0,B,R*,TB,2σ)(具體算法參見文獻[16]，將結果Ti d返回給挑戰者.

Game1到Game2:從攻擊者A角度來看，私鑰份額生成過程是不可見的，A獲得的私鑰ei d,i在統計上仍然服從分布D，且滿足Fi d·ei d,i=ui d,i.所以攻擊者A在Game1中得到的優勢與Game2中的優勢相當.

Game3. 挑戰密文為隨機選取且互相獨立的向量C=(c1,c2)∈U(q)，其余設置與Game2中相同.

Game2到Game3：假設攻擊者A有不可忽略的優勢來區分Game2和Game3，那么可以如下構造仿真者S來解決判定性LWE問題.

假設存在一個LWE采樣預言機O，其隨機從O$或Os中選取一些采樣作為輸出，仿真者S通過與攻擊者A進行交互后判斷這些采樣取自Os或O$.

實例化：C向預言機O詢問并接收m+1個LWE采樣，標記為{(w1,v1),(w2,v2),…,(wm+1,vm+1)}.

攻擊目標：設攻擊者A輸出準備要攻擊的身份id*和一個已經腐化的解密服務器的集合S∈{1,2,…,t-1}.

S構造如下系統參數：

1)A0=(w1,w2,…,wm)T；

2)u=(wm+1)；

3) 其余系統參數設置與Game2中相同.

第1階段詢問.與Game2中定義的詢問相同.

挑戰.當攻擊者A給仿真者S發送加密消息M∈{0,1}時，仿真者S如下構造挑戰密文:

3) 仿真者S從{0,1}中隨機選取β，如果β=0，密文C*=(c1,c2)∈q構造方法如上，否則隨機選取均勻分布的矩陣C*∈U(q)，將C*發送給攻擊者A.

第2階段詢問.和第1階段詢問一樣，帶有一些限制.

猜測.詢問過后，攻擊者A給出一個猜想β′∈{0,1}，這里β′=1意味著攻擊者A正在與Game2交互，仿真者S回答LWE挑戰的猜測δ′=β′，這里δ′=1意味著上述實例(wi,vi)(1≤i≤m+1)服從LWE分布，否則δ′=0表示實例服從隨機均勻分布.

以上完成了對仿真者S的描述，可以看出如果A能夠以不可忽略的優勢區分Game2和Game3，那么仿真者S能夠以絕對的優勢解決判定性LWE問題.

通過以上4個等價游戲，將方案的安全性歸約為判定性LWE困難假設.根據定理1，方案達到了語義安全.

這就與定理5產生了矛盾.

證畢.

4.3 效率比較

目前，基于格上困難問題構造的門限解密方案主要有文獻[13,15]，這2個方案都是基于LWE困難問題構造的，且都滿足非交互性，但是從構造方法、安全性和效率方面有所差異.將這些類似方案進行比較，具體如表1所示.可公開驗證性是指解密份額是否滿足可公開驗證性；密鑰份額是指每個解密服務器獲得的密鑰份額，其長度單位為logq位，密文長度是指加密1位明文后生成的密文長度，單位為logq位；計算量中的乘法運算指的是q上2個整數相乘，采用Mul表示；指數運算是指離散對數群上生成元的指數計算，采用Exp表示.Hash表示一次Hash運算，Sign表示一次簽名運算.

Table 1 The Comparison to Related Works表1 相關工作比較

5 總 結

本文利用格上陷門產生函數、左右采樣基、Shamir秘密分享等技術構造了一種IND-sID-CPA安全的IBTD方案，并基于離散對數困難問題來實現可公開驗證性.同現存格上基于身份的門限加密方案相比，本文是對滿足均勻分布的向量進行分割，通過私鑰份額和解密份額之間的同態性來保證方案的正確性，同時方案的證明過程在標準模型下完成.