格上基于身份的可問責代理重加密方案

摘要：針對目前基于格的代理重加密方案中存在密鑰濫用和數字證書管理等問題，引入問責機制，提出一種新的基于身份的可問責代理重加密方案。該方案采用用戶身份ID計算生成矩陣作為公鑰，并使用原像采樣算法提取私鑰，解決了數字證書管理的問題；使用雙方用戶公鑰計算生成重密鑰，提高了加/解密時的計算效率；使用代理商公私鑰參與重加密運算，完成問責算法，有效地抑制了代理商和被授權者共謀的行為。安全性分析表明方案滿足選擇明文攻擊安全；在效率方面，方案的計算復雜度和密文開銷較小。

關鍵詞：代理重加密； 格密碼； 帶錯誤學習問題； 可問責性

中圖分類號：TP309文獻標志碼：A

文章編號：1001-3695（2022）08-042-2484-06

doi：10.19734/j.issn.1001-3695.2021.12.0693

Identity-based accountable proxy re-encryption scheme from lattice

Meng Hui， Ren Lina， Li Ying

（School of Software， Henan Polytechnic University， Jiaozuo Henan 454003， China）

Abstract：Aiming at the problems of key abuse and digital certificate management in the current lattice-based proxy re-encryption scheme， this paper proposed a new identity-based accountable proxy re-encryption scheme by introducing the accountability algorithm. This scheme used the user ID to calculate matrix as the public key and used the pre-image sampling algorithm to extract the private key， which solved the problem of digital certificate management. It used the public keys of both users to calculate and generate the re-encryption key， which improved the computational efficiency of encryption and decryption. It used the proxy’s public and private keys to participate in the re-encryption calculation， completed the accountability algorithm， and inhibited the collusion of the proxy and the delegate. The security analysis shows that the scheme satisfies the chosen-plaintext attack security. In terms of efficiency， the scheme has less computational complexity and ciphertext overhead.

Key words：proxy re-encryption; lattice code; learning with error; accountability

0引言

目前，云存儲和云端數據共享在網絡數據存儲與計算中占據核心地位，用戶將大量的數據存儲在網絡云盤中，減輕自己存儲設備的負擔，同時，更利于用戶之間共享數據。在復雜的網絡環境中，用戶為了保護數據隱私需要將數據加密后再上傳至云服務器存儲或共享，但是數據發送者需要實時查看是否有用戶訪問數據，并將要訪問的數據下載后轉發給數據接收方。代理重加密解決了傳統云計算環境中數據擁有者需要實時在線的問題，減輕了用戶頻繁訪問云端密文數據的負擔，增強了數據的可靠性和機密性。1998年，Blaze等人［1］首次提出了代理重加密（proxy re-encryption，PRE）的概念，在公鑰加密系統中加入代理商的角色，并由代理商使用重密鑰完成密文轉換。2007年，Green等人［2］第一次提出了基于身份的代理重加密（IB-PRE）方案，方案中公鑰直接使用用戶身份ID，公鑰基礎設施中的證書管理問題得以解決，該方案滿足多跳性和非交互性。然而，隨著量子計算機的發展，傳統數論難題的安全性受到威脅。2010年，Xagawa［3］首次提出了格上的代理重加密方案，該方案不僅能夠抵抗量子攻擊還降低了計算復雜度。2014年，Singh等人［4］將身份基和代理重加密融合，提出了一個可以加密多比特信息的PRE方案，提高了運算效率，且該方案滿足匿名性、多跳性。2021年，湯永利等人［5］利用RLWE（ring learning with errors）難題構造了一個PRE方案，有效縮短了密文、密鑰尺寸，提高了加/解密的效率。但是，以上幾種方案都具有雙向性，不能抵抗合謀攻擊，且存在密鑰泄露等安全問題。2016年，Kim等人［6］提出了第一個基于最壞情況的格上難題且滿足單向性的代理重加密方案，方案中的被授權者無法感知代理商的存在，即使用重密鑰加密的密文和使用被授權方公鑰加密的密文是不能被區分的。2020年，Wang等人［7］指出了Kim方案中重加密密文無法解密或解密錯誤率高的問題，提出了一個新的滿足單向性的代理重加密方案，經證明方案滿足選擇明文攻擊（chosen-plaintext attack，CPA）安全。2021年，Dutta等人［8］提出第一個針對選擇性和自適應身份的抗合謀單向IB-PRE的具體構造，所提結構具有非交互性和非傳遞性，不滿足多跳性。

2013年，Wang等人［9］提出了一個新的原語PRE+，與傳統PRE的不同點在于解密權的委托者不同。傳統PRE解密權限的委托者是密文接收方，而PRE+解密權限的委托者是密文發送者，即加密者將解密權委托給被授權者。且重密鑰生成算法中的輸入元素不同，傳統PRE由密文接收方的私鑰與被授權者的私鑰或公鑰生成重密鑰，而PRE+是由兩者的公鑰生成重密鑰。2020年，Singh等人［10］提出了單向的PRE和PRE+方案，PRE+能夠提高加/解密時的計算效率，適用于細粒度授權和不可轉讓授權，在安全云計算和組播等方面應用廣泛。被授權者和代理商的合謀攻擊雖然不會暴露授權者的長期密鑰，但是，他們可能合謀并為不受委托方信任的惡意用戶提供新的重密鑰。另外，由于代理重加密的固有功能可能會使PRE方案存在重密鑰濫用問題，即代理商和被授權者合謀獲得授權者的解密能力，并將其保存在任何載體上，如解密設備。為了緩解這個問題，2006年，Ateniese等人［11］提出不可轉讓的概念，當Bob和代理商合謀分發Alice的解密能力時，Bob必須公開其解密能力作為代價。2019年，Guo等人［12］使用不可區分性混淆和K-不可偽造認證構造了不可轉讓的代理重加密方案。不可轉讓性對惡意用戶有一定的威懾作用，但是當Bob的密鑰遠沒有數據擁有者的密鑰有價值時，Bob可能會為了更大的利益而公開自己的解密能力。此時代理商可以從中分發Alice的解密能力，卻不用付出任何代價，甚至否認自己的惡意行為。2021年，Guo等人［13］為了解決上述問題提出了可問責的代理重加密（accountable proxy re-encryption，APRE）方案，并引入一個判斷算法來判斷代理商是否不承認自己分發授權者解密能力的行為?？蓡栘煷碇丶用苣Ｐ腿鐖D1所示。

為了解決公鑰加密中的數字證書管理和密鑰濫用等問題，基于文獻［13］中的問責算法構造一個新的格上基于身份的可問責代理重加密方案。利用用戶身份ID計算生成一個矩陣作為公鑰，取代傳統公鑰加密體制中將用戶身份和公鑰聯系起來的數字證書，使用原像采樣算法提取私鑰，并且令代理商公私鑰參與重密鑰和重加密的計算，最后使用一個公開的審判算法判斷惡意代理是否在否認其分發授權者解密能力的行為。與文獻［13］不同的是，本文方案基于帶錯誤學習（learning with error，LWE）困難假設，使用用戶身份作為公鑰并使用授權者公鑰參與重密鑰的運算。安全分析表明，本文方案在標準模型下達到適應性選擇身份的選擇明文攻擊安全下的不可區分性（IND-aID-CPA）。效率分析則說明本文方案在存儲空間、性能和復雜度上的優勢。

1預備知識

1.1格

設B={b1，b2，…，bn}是由Euclid Math TwoRApm中n個向量組成的矩陣，且這些向量是線性無關的，則這n個向量的所有整系數的線性組合所構成的集合為一個m維格Λ，即

Λ=Euclid Math OneLAp（B）={y∈Euclid Math TwoRApm，s.t.s∈Euclid Math TwoZApn，y=Bs=∑ni=1sibi}

其中：b1，b2，…，bn是格Λ的一組基，當m=n時，稱格Λ是滿秩格。

定義1設q為素數，矩陣A∈Euclid Math TwoZApn×mq，定義兩個m維滿秩整數格：

Λ⊥q（A）={e∈Euclid Math TwoZApm，s.t.Ae=0（mod q）}

Λq（A）={y∈Euclid Math TwoZApm，s.t.s∈Euclid Math TwoZApnq，ATs=y（mod q）}

格上的陷門函數在格密碼學中有著廣泛的應用，陷門基是格的一個短基，方案中使用陷門生成算法產生的陷門基作為主私鑰。

引理1［14］陷門生成算法。整數q≥3，m=「6nlog q。存在一個概率多項式時間（probabilistic polynomial-time，PPT）算法TrapGen（q，n）生成矩陣A∈Euclid Math TwoZApn×mq和Λ⊥q（A）的一組基T∈Euclid Math TwoZApm×mq，其中A在Euclid Math TwoZApn×mq上的分布與均勻分布是不可區分的，且‖‖≤Ο（nlog q）和‖T‖≤Ο（nlog q）以絕對的優勢成立。

1.2離散高斯分布

高斯分布常用于格上困難問題的研究，本節將對離散高斯分布和其相關引理進行詳細介紹。

對于s∈Euclid Math TwoRAp+，c∈Euclid Math TwoRApm，定義m維格Λ上的離散高斯分布為

DΛ，s，c（x）=ρs，c（x）ρs，c（Λ）=ρs，c（x）∑x∈Λρs，c（x）

文獻［14］中介紹了原像采樣算法，其中包含的SamplePre算法負責使用陷門基TA求解給定像值u對應的原像值x。

引理2［14］SamplePre（A，TA，σ，u）已知格Λ⊥q（A）上一個陷門基TA，實數σ≥‖A‖ω（log n），對于任意向量u∈Euclid Math TwoZApnq，存在一個PPT算法SamplePre（A，TA，σ，u），在統計量接近DΛuq（A），σ，c（x）的分布中抽取一個向量x∈Λuq（A），滿足Ax=u（mod q）。

引理3［15］設正整數n、q，其中q為素數，m≥2nlog2q。那么對于A∈Euclid Math TwoZApn×mq，σ≥ω（log2m），e←DEuclid Math TwoZApm，σ，u=Aemod q的分布與Euclid Math TwoZApnq上的均勻分布的統計量相近。

1.3格上困難問題

定義2［16］小整數解問題SIS。給定素數qgt;0，隨機選擇矩陣B∈Euclid Math TwoZApn×mq，找到一個非零向量u∈Euclid Math TwoZApmq，使Bu=0 mod q，并且滿足‖u‖≤δ，其中，常數δgt;0。

文獻［17］給出從最壞情況困難到SIS的歸約，證明SIS問題在某些參數下是足夠困難的。

定理1［17］設整數n≥1，m=poly（n）和實數β≥β∞≥1，令Z*={z∈Euclid Math TwoZApm：‖z‖2≤β，‖z‖∞≤β∞}并且q≥βnδ，常數δgt;0。則求解解集為Z*＼{0}的SISm，n，q，δ問題至少與在n維格上將最壞情況下的格問題逼近到max{1，β·β∞/q}·（βn）一樣困難。

定義3［18］帶錯誤學習問題LWE。給定正整數n和q，選擇均勻隨機的矩陣A∈Euclid Math TwoZApn×mq和向量s∈Euclid Math TwoZApnq，向量e←χm服從錯誤分布。LWE困難問題就是給定（A，ATs+e），以不可忽略的概率尋找s。

定義4［4］LWEq，χ判定問題DLWE。設正整數n、m以及素數q，χm是Euclid Math TwoZApq上的高斯分布。LWE的判定性問題是指通過隨機給出一系列來自分布As，χ的獨立抽樣或者來自Euclid Math TwoZApnq×Euclid Math TwoZApq的均勻隨機抽樣，判斷抽樣是否來自分布As，χ的問題。

文獻［18］中給出了LWE和DLWE的關系以及從最短向量問題（SVP）到LWE的歸約，證明LWE對于某些參數是足夠困難的。

定理2［18］n、q為正整數，實數α∈（0，1），滿足αqgt;2n。若LWE問題能被一個有效的算法解決，那么近似決策性最短向量問題（Gap-SVP）和最短獨立向量問題（SIVP）的最壞情況問題也能夠被一個量子算法以（n/α）的時間復雜度解決。

2可問責代理重加密定義及安全模型

2.1可問責代理重加密的定義

下面介紹身份基可問責代理重加密定義，安全參數為λ。

1）初始化Setup（λ）輸入安全參數λ，輸出公共參數params和主私鑰msk；

2）私鑰提取Extract（params，msk，id）輸入params、msk和用戶id，輸出用戶私鑰SK；

3）加密Enc（params，idi，m）輸入idi和明文m，輸出二級密文Ci；

4）重密鑰生成ReKeyGen（params，idi，idj，idp）以公共參數params和雙方用戶及代理商的身份id作為輸入，輸出重密鑰rki→j；

5）重加密ReEnc（params，rki→j，SKp，Ci）輸入rki→j、代理商私鑰SKp和Ci，輸出一級密文Cj；

6）二級密文解密Dec2（params，SKi，Ci）輸入SKi和二級密文Ci，算法解密恢復出明文m；

7）一級密文解密Dec1（params，SKj，Cj）輸入SKj和一級密文Cj，輸出明文m；

8）問責算法JudgeDi，μ（params，idi，idp）通過黑盒訪問解密設備Di，μ，idi和idp作為輸入，該算法輸出“Proxy”或“Delegator”，輸出結果即為惡意解密設備的生成者。

正確性：方案滿足以下兩個條件，即可正確恢復明文。

Dec2（params，SKi，Enc（params，idi，m））=m；

Dec1（params，SKj，ReEnc（params，rki→j，SKP，Enc（params，idi，m）））=m

2.2可問責代理重加密的安全模型

2.2.1CPA安全

本節將介紹基于IND-aID-CPA游戲的可問責代理重加密安全模型［19］，設安全參數為λ，游戲是由敵手Euclid Math OneAAp和下列預言機組成，過程如下：

初始化階段：挑戰者Euclid Math OneCAp將Setup（λ）輸出的公共參數params發送給敵手Euclid Math OneAAp。

階段1：敵手Euclid Math OneAAp發出問詢，挑戰者Euclid Math OneCAp作出回答：

私鑰生成預言機OSK：使用Extract（params，msk，idi）生成用戶私鑰SKi并存儲，當敵手Euclid Math OneAAp輸入idi時，若用戶i為惡意用戶，則挑戰者Euclid Math OneCAp發送SKi給敵手Euclid Math OneAAp;否則，發送⊥。

重密鑰生成預言機Ork：敵手Euclid Math OneAAp輸入（idi，idj，idp），得到ReKeyGen生成的重密鑰rki→j。

重加密預言機Ore：如果用戶j是不誠實的，則敵手Euclid Math OneAAp輸入（rki→j，SKp，Ci），并輸出⊥；否則，輸出重加密后的密文Cj=ReEnc（ReKeyGen（idi，idj，idp），SKp，Ci）。

挑戰預言機OC：敵手Euclid Math OneAAp輸入一個目標用戶和兩個消息m0、m1。預言機隨機選擇b∈{0，1}，返回挑戰者密文C*=Enc（id*，mb）。

猜測：輸入b′∈{0，1}，如果b′=b，則挑戰者Euclid Math OneCAp輸出1;否則輸出0。

定義5IND-CPA安全。定義敵手Euclid Math OneAAp的優勢為

ADVIND-CPAPRE，Euclid Math OneAAp（n）=|Pr［ExpIND-CPAPRE，Euclid Math OneAAp（n）=1］－12|

當ADVIND-CPAPRE，Euclid Math OneAAp（n）是可忽略的，稱方案是IND-CPA安全的。

2.2.2惡意代理安全

若敵手輸出的解密設備使審判者相信誠實的授權者有罪，則敵手贏得游戲。實驗過程如下［13］：

Experiment ExpmpPRE，Euclid Math OneAAp（n）

params←Setup（λ）

SKp←Extract（params，idp）

Di，μ←AOSK，Ork（params，idp，SKp）

where μ is a non-negligible probability value;

if JudgeDi，μ（id*，idp）=Delegator

return 1;

else return 0.

定義6惡意代理安全。敵手的優勢被定義為

ADVmpPRE，Euclid Math OneAAp（n）=|Pr［ExpmpPRE，Euclid Math OneAAp（n）=1］|

當所有PPT敵手Euclid Math OneAAp的優勢ADVmpPRE，Euclid Math OneAAp（n）是可忽略的，方案滿足惡意代理安全。

2.2.3惡意授權者安全

根據下面實驗，當解密設備Di，μ使審判者相信誠實的代理商有罪，則敵手贏得游戲。

Experiment ExpmdPRE，Euclid Math OneAAp（n）

params←Setup（λ）

SKp←Extract（params，idp）

Di，μ←AOSK，Ork（params，idP）

where μ is a non-negligible probability value;

if JudgeDi，μ（id*，idp）=Proxy

return 1;

else return 0.

定義7惡意授權者安全。敵手Euclid Math OneAAp的優勢被定義為

ADVmdPRE，Euclid Math OneAAp（n）=|Pr［ExpmdPRE，Euclid Math OneAAp（n）=1］|

當所有PPT敵手Euclid Math OneAAp的優勢ADVmdPRE，Euclid Math OneAAp（n）是可忽略的，稱方案是惡意授權者安全的。如果PRE方案同時滿足惡意代理安全和惡意授權者安全，則稱這個方案滿足可問責性。

3代理重加密方案

3.1方案構造

本文基于問責算法與LWE困難問題，結合代理重加密與基于身份的加密體制，提出格上基于身份的可問責代理重加密方案，方案具體構造如下：

a）初始化Setup（λ）。λ為安全參數，隨機矩陣A∈Euclid Math TwoZApn×mq和陷門基矩陣T∈Euclid Math TwoZApm×mq由陷門生成算法TrapGen（q，n）生成，‖‖≤O（nlogq），陷門函數fA（x）=Ax mod q（f：Euclid Math TwoZApm→Euclid Math TwoZApnq）。隨機選擇m+1個矩陣U0，U1，…，Um∈Euclid Math TwoZApn×mq，且線性無關，則主密鑰為mpk=（A，U0，U1，…，Um），主私鑰msk=T，公共參數params=（m，n，q，mpk）。

b）私鑰提取Extract（params，msk，id）。輸入公共參數params，主私鑰msk和用戶/代理身份id={id1，id2，…，idm}∈ {0，1}，計算U=U0+∑mi=1idiUi=（u1，u2，…，um），使用原像采樣算法產生一個向量xi∈Euclid Math TwoZApmq，使其滿足ui=Axi mod q，‖xi‖≤σm。令X=（x1，x2，…，xm），則AX=U mod q，用戶/代理私鑰SK=X。

c）加密Enc（params，idi，m）。輸入用戶i的身份idi和明文m∈{0，1}m，隨機選擇向量s∈Euclid Math TwoZApnq，e←χm；計算C1=UTis+mq2」+e，y=ATs+e，輸出二級密文Ci=（C1，y）。

d）重密鑰生成ReKeyGen（mpk，s，idi，idj，idp）。輸入隨機向量s、用戶身份idi和idj以及代理商身份idp，選擇e1←χm，由用戶i計算重密鑰rki→j=（UTj－UTi+UTp）s+e1。

e）重加密ReEnc（params，rki→j，SKp，Ci）。輸入重密鑰rki→j，代理商私鑰SKp和二級密文Ci，選擇e2←χm，計算C′1=C1+rki→j－SKTpy+e2，輸出一級密文Cj=（C′1，y）。

f）二級密文解密Dec2（params，SKi，Ci）。輸入SKi和二級密文Ci，計算m=C1－SKTiy（modq）；令m=（m1，m2，…，mm），如果mi與q2」相比更接近0，則mi=0；否則，mi=1；輸出m=（m1，m2，…，mm）。

g）一級解密Dec1（params，SKj，Cj）。輸入SKj和一級密文Cj，計算m=C′1－SKTjy（mod q）；令m=（m1，m2，…，mm），如果mi與q2」相比更接近0，則mi=0；否則，mi=1；輸出m=（m1，m2，…，mm）。

h）問責算法JudgeDi，μ（params，idi，idp）。提供一個解密設備Di，μ作為預言機：

（a）重復下面的實驗n=λ/μ次。選擇均勻隨機向量s∈Euclid Math TwoZApnq和明文m，并且計算C1=（UTi+UTp）s+mq2」+e，y=ATs+e，密文C=（C1，y）；運行解密設備Di，μ，并將C作為Di，μ的輸入，輸出m′；

（b）如果m′=m，輸出“Proxy”并退出；否則輸出“Delegator”。

3.2正確性

1）二級密文解密Dec2（params，SKi，Ci）

m=C1－SKTiy（mod q）=UTis+mq2」+e－

XTi（ATs+e）（mod q）=UTis+mq2」+e－UTis－XTie（mod q）=

e－XTie+mq2」（mod q）

因為e和SKTi是從高斯分布的集合ψs中選擇的，所以在s=αq時，（e－XTie）lt;q4」，成功恢復m。

2）一級密文解密Dec1（params，SKj，Cj）

C′1=C1+rki→j－SKTPy+e2=

UTis+mq2」+e+（UTj－UTi+UTp）s+e1－XTpy+e2=

UTjs+e+e1－XTpe+e2+mq2」

m=C′1－C′2－SKTjy（mod q）=

UTjs+e+e1－XTpe+e2+mq2」－XTj（ATs+e）（mod q）=

e+e1－XTje－XTpe+e2+mq2」（mod q）

因為e、e1、e2、SKTj、SKTP是從高斯分布的集合ψs中選擇的，所以在s=αq時，（e+e1－XTje－XTpe+e2）lt;q4」，成功恢復m。

3.3多跳性

代理者執行第一次重加密：

C2=C1+rk1→2－SKTpy+e2

代理者執行第二次重加密：

C3=C2+rk2→3－SKTpy+e2=

C1+rk1→2+rk2→3－2SKTpy+2e2

代理者執行第N-1次重加密：

CN=CN－1+rkN－1→N－SKTpy+e2=

CN－2+rkN－2→N－1+rkN－1→N－2SKTpy+2e2=…=

C1+∑N－1i=1rki→i+1－（N－1）SKTpy+（N－1）e2=

C1+∑N－1i=1（（UTi+1－UTi+UTp）s+e1）－（N－1）XTpy+（N－1）e2=

UT1s+mq2」+e+（-UT1+UTN）s+（N－1）e1－（N－1）XTpe+（N－1）e2=

mq2」+e+UTNs+（N－1）e1－（N－1）XTpe+（N－1）e2

完成N-1次重加密后，使用用戶N的私鑰SKN完成解密：

m=CN－SKTNy（mod q）=mq2」+e+UTNs+

（N－1）e1－（N－1）XTpe+（N－1）e2－XTN（ATs+e）（mod q）=

mq2」+e+（N－1）e1－（N－1）XTpe+（N－1）e2－XTNe（mod q）

當（e+（N－1）e1－（N－1）XTpe+（N－1）e2－XTNe）lt;q4」時，成功恢復m。

4安全性與效率分析

4.1CPA安全

定理3令λ為安全參數，對于任意明文m∈{0，1}，若LWE問題在多項式時間是不可解的，則該方案滿足IND-aID-CPA安全。即敵手Euclid Math OneAAp在多項式時間t內成功攻破方案的優勢ADVIND-CPAPRE，Euclid Math OneAAp（t）≤negl（λ）。

證明通過證明下列游戲的不可區分性來證明PPT敵手Euclid Math OneAAp成功攻破方案的優勢是可忽略的。

游戲1原始的IND-aID-CPA方案。在挑戰階段，當挑戰者Euclid Math OneCAp收到（i*，m0，m1）后，挑選其中一個明文mb，計算挑戰密文C*=（C1，y）給敵手Euclid Math OneAAp，其中C1=UTis+mbq2」+e，y=ATs+e。最后，敵手Euclid Math OneAAp猜測b′，若猜測成功，則Euclid Math OneCAp輸出1，否則輸出0。

游戲2在游戲2中矩陣A∈Euclid Math TwoZApn×mq與矩陣U0，U1，…，Um∈Euclid Math TwoZApn×mq的生成方式與游戲1不同。在游戲2中，挑戰者Euclid Math OneCAp模擬真實的方案，并回答敵手Euclid Math OneAAp的各種問詢。首先挑戰者模擬真實方案如下：

初始階段：挑戰者Euclid Math OneCAp選擇一個隨機矩陣A∈Euclid Math TwoZApn×mq，根據以下步驟生成U0，U1，…，Um∈Euclid Math TwoZApn×mq：

a）挑戰者Euclid Math OneCAp隨機選擇服從高斯分布Dσ/（m+1），0的m+1個矩陣X0，X1，…，Xm；

b）計算AXk=Ukmod q，k=0，1，…，m；

c）若生成的矩陣Uk是線性相關的，則重新選擇生成Xk。

挑戰者Euclid Math OneCAp將公共參數A∈Euclid Math TwoZApn×mq和U0，U1，…，Um∈Euclid Math TwoZApn×mq發送給敵手Euclid Math OneAAp。

階段1：敵手Euclid Math OneAAp可以進行下面一系列的問詢過程，挑戰者回答敵手Euclid Math OneAAp下列問詢：

（a）代理密鑰問詢。代理商的私鑰Xp∈Euclid Math TwoZApm×mq是由挑戰者Euclid Math OneCAp均勻隨機選擇的小范數矩陣，計算AXp=Up，將代理商的私鑰對SKp發送給Euclid Math OneAAp。

（b）密鑰提取問詢。敵手Euclid Math OneAAp發送用戶身份id給挑戰者Euclid Math OneCAp，Euclid Math OneCAp計算X=X0+∑mi=1idiXi，所以AX=U=U0+∑mi=1idiUi（mod q）。最后，Euclid Math OneCAp將X=X0+∑mi=1idiXi發送給Euclid Math OneAAp作為用戶私鑰。

（c）重加密密鑰問詢：敵手Euclid Math OneAAp發送身份集（idi，idj，idp）給挑戰者Euclid Math OneCAp，挑戰者Euclid Math OneCAp按照上面的步驟計算生成Ui、Uj和Up；然后，使用計算好的公鑰計算生成重密鑰rki→j=（UTj－UTi+UTp）s+e1，并發送給Euclid Math OneAAp。

階段2（挑戰階段）：當挑戰者Euclid Math OneCAp收到來自敵手Euclid Math OneAAp的id*、m0、m1。挑戰者隨機選擇b∈{0，1}，計算C=UTid*s+mbq2」+e，y=ATs+e，并發送C*=（C，y）給敵手。最后敵手Euclid Math OneCAp猜測b′，如果b′=b，則挑戰者Euclid Math OneCAp輸出1，否則輸出0。

游戲3在游戲2中，通過加密算法計算生成挑戰密文C*。在游戲3中，直接從Euclid Math TwoZApmq×Euclid Math TwoZApmq中隨機選擇C*。顯然，敵手Euclid Math OneAAp在游戲3中可獲得的優勢為0。

通過將問題規約到LWE難題來證明兩個游戲的不可區分性。若敵手Euclid Math OneAAp能夠區分兩個游戲的優勢為ε，則使用下面的算法B能夠攻破LWE困難問題［12］。

算法B收到了隨機實例（ai，yi）∈Euclid Math TwoZApnq×Euclid Math TwoZApq，其中yi=aTis+ei，A=（a1，a2，…，am），y=（y1，y2，…，ym）。計算

C*=XTy+mq2」=XT（ATs+e）+mq2」=

UTs+e+mq2」

若敵手Euclid Math OneAAp成功猜測出m，則算法B輸出1，否則輸出0。

如果y選取的是均勻隨機的向量，則C*也是均勻隨機的，敵手Euclid Math OneAAp以不超過1/2的概率成功猜測出m。

若y是由y=ATs+e產生的，則C*也是均勻分布的。此時敵手Euclid Math OneAAp有（1+ε）/2的優勢猜測出m，算法B同樣有（1+ε）/2的概率輸出1。即算法B有ε/2的優勢解決LWE問題。但是，LWE為格上難題，算法B不能求解出LWE困難問題，所以ε/2的優勢是可忽略的。

顯然，游戲2和3是不可區分的。因此，敵手Euclid Math OneAAp在游戲2中可以取得優勢也為0。同樣地，對于任意PPT敵手Euclid Math OneAAp來說，游戲1和2也是不可區分的。由于矩陣A是隨機的，且Ui服從高斯分布，根據定理3，AXi=Uimod q上的分布與Euclid Math TwoZApn×mq上的均勻分布在統計量上是接近的，故無法區分游戲1和2。因此，敵手Euclid Math OneAAp在游戲1中獲得的優勢也為0。

綜上所述，在標準模型下，APRE方案滿足IND-aID-CPA安全性。

4.2可問責性

為了證明方案的可問責性，本文將證明方案滿足惡意代理安全和惡意授權者安全。

4.2.1惡意代理安全

定理4在LWE困難問題下，若敵手Euclid Math OneAAp在多項式時間t內成功誣陷授權者的優勢ADVmpPRE，Euclid Math OneAAp（t）≤negl（λ），則方案滿足惡意代理安全，即敵手Euclid Math OneAAp輸出一個解密算法，使審判算法輸出“Delegator”的優勢是可忽略的。

證明為了證明方案是惡意代理安全的，本文提出以下兩個實驗，通過證明兩個實驗的不可區分性和在實驗Exp1中敵手Euclid Math OneAAp的優勢是可忽略的完成惡意代理安全的證明。

實驗Exp0原始惡意代理安全實驗。敵手Euclid Math OneAAp輸出一個能夠以不可忽略的概率μ獲得明文的解密設備D*，μ，挑戰者Euclid Math OneCAp用n個不規則明文作為輸入運行解密設備D*，μ。不規則密文為C1=（UTi+UTp）s+mq2」+e，y=ATs+e，其中s←Euclid Math TwoZApnq。

實驗Exp1原始惡意代理安全對比實驗。與Exp0的不同在于不規則密文，Exp1中密文為C1=UTis+mq2」+e，y=ATs+e，其中s←Euclid Math TwoZApnq。

接下來使用引理4和引理5證明以上兩個實驗在計算上的不可區分性，且在實驗Exp1中敵手成功誣陷授權者的概率可忽略。

引理4基于LWE困難問題假設下，Exp1與Exp0在計算上是不可區分的。

按照游戲2中的步驟生成U0，U1，…，Um，可知AXi=Ui mod q的分布與Euclid Math TwoZApn×mq上均勻分布的統計量相近。

敵手Euclid Math OneAAp輸出一個解密設備Di，μ，挑戰者Euclid Math OneCAp運行審判算法JudgeDi，μ：

a）重復以下實驗n=λ/μ次。均勻隨機地選擇向量s∈Euclid Math TwoZApnq，r∈Euclid Math TwoZApnq和明文m，計算C1=UTis+r+mq2」+e，y=ATs+e，密文C=（C1，y）；運行解密設備Di，μ，并將C作為Di，μ的輸入，輸出m′。

b）如果m′=m，輸出“Proxy”并退出；否則輸出“Delegator”。

對于上述審判算法，若r=e，則C1=（UTi+UTp）s+mq2」+2e，此時Euclid Math OneCAp成功模擬實驗Exp0；若r=-XTpy，則C1=UTis+mq2」+（e－XTpe），此時Euclid Math OneCAp成功模擬實驗Exp1；由于e和Xp均服從高斯分布，故對于Euclid Math OneAAp是不可區分的。即實驗Exp1與Exp0在計算上是不可區分的。

引理5在Exp1中，敵手Euclid Math OneAAp輸出一個解密設備，使得審判算法輸出“Delegator”的優勢可以忽略。

在一次實驗中，由于Exp1解密設備的輸入密文C1=（UTi+UTp）s+mq2」+e，y=ATs+e為普通密文，所以Di，μ將以μ的概率返回明文m′=m，則敵手Euclid Math OneAAp在Exp1中的優勢為（1－μ）n=（1－μ）λ/μ≤1/eλ，故敵手的優勢是可忽略的。

4.2.2惡意授權者安全

定理5在LWE困難假設下，若敵手Euclid Math OneAAp在多項式時間t內成功誣陷代理商的優勢ADVmdPRE，Euclid Math OneAAp（t）≤negl（λ），則方案滿足惡意代理安全，即敵手Euclid Math OneAAp輸出一個解密算法，使審判算法輸出“Proxy”的優勢是可忽略的。

證明為了證明方案是惡意授權者安全的，提出以下兩個實驗，通過證明兩個實驗的不可區分性和在實驗Exp1中敵手Euclid Math OneAAp的優勢是可忽略的完成惡意授權者安全的證明。

實驗Exp0原始惡意授權者安全實驗。當敵手Euclid Math OneAAp輸出一個能夠以不可忽略的概率μ獲得明文的解密設備Di，μ，挑戰者Euclid Math OneCAp用n個不規則明文作為輸入運行解密設備Di，μ。不規則密文為C1=（UTi+UTp）s+mq2」+e，y=ATs+e，其中s←Euclid Math TwoZApnq。

實驗Exp1原始惡意授權者安全對比實驗。與Exp0不同的是審判算法的輸入密文不同。均勻隨機地選擇矩陣R∈Euclid Math TwoZApn×mq，密文為C1=（UTi+RT）s+mq2」+e，y=ATs+e，其中s←Euclid Math TwoZApnq。

接下來使用引理6和引理7證明以上兩個實驗在計算上的不可區分性，且在實驗Exp1中敵手成功誣陷代理商的概率可忽略。

引理6基于LWE困難問題假設下，Exp1與Exp0在計算上是不可區分的。

使用游戲2中的方式生成U0，U1，…，Um，可知AXi=Ui mod q的分布與Euclid Math TwoZApn×mq上的均勻分布在統計量上相近，故得證。

引理7在Exp1中敵手輸出一個解密設備，使審判算法輸出“Proxy”的優勢是可忽略的。

解密設備Di，μ的輸入密文為C1=（UTi+RT）s+mq2」+e，y=ATs+e。由于R是均勻隨機的，Di，μ輸出m′=m的概率為1/|M|=1/2m。根據二級解密算法可知，解密結果為RTs+e－XTie+mq2」。因為R是均勻隨機的，無法恢復出明文m；且（1/|M|）nlt;1/2m，可知敵手Euclid Math OneAAp在Exp1的優勢是可忽略的。

4.3效率分析

文獻［13］中提出的可問責代理重加密基于DBDH困難假設，計算復雜度較高且存在證書管理問題。文獻［20］中提出了格上基于身份的PRE方案，該方案可以加密多比特信息，但是方案是交互式的，被授權者需要提供自己的私鑰來生成重密鑰，容易造成密鑰泄露的問題。文獻［21］中提出單跳的格上PRE方案，使用陷門生成私鑰。本文完成了可問責性和抗合謀攻擊的設計；具有單向性和多跳性，密文擴展性良好；能夠抵抗量子攻擊。表1給出了文獻［13，20］與本方案的存儲空間和性能上的對比。其中，|G|是群G中元素的個數，|GT|表示G中元素的位長，log q表示log2q。表2選擇文獻［20，21］與本方案的三個格上代理重加密方案進行計算和通信復雜度對比，其中，密文開銷指1 bit明文對應的密文大小，MMM為矩陣間乘法，MMA為矩陣間加法，VMM為向量矩陣乘法，VCM為常數向量乘法，VVM為向量間加法，EGT為群GT中的冪運算，EG為群G中的冪運算。

結合兩個表格的比較結果，本文方案在私鑰尺寸上優于文獻［21］，并且相較于其他方案滿足單向性和可問責性；計算復雜度低于文獻［20］，且密鑰開銷與文獻［13，21］相比較低。因此，本文方案具有較為良好的安全性和較高的效率。

5結束語

本文提出了一個格上基于身份的可問責代理重加密方案。在方案中，用戶的身份被計算為一個矩陣作為公鑰，提高了私鑰提取的效率；重密鑰由用戶公鑰計算生成，具有非交互性；使用公共問責算法抑制惡意代理商濫用重密鑰的行為。該方案具有單向性和多跳性等性質。安全分析表明，方案滿足標準模型下的IND-aID-CPA安全；效率分析則說明了方案在存儲空間和性能方案較有優勢。但是本文方案在計算效率上還有一定的優化空間，構造更加高效的格上可問責的代理重加密的方案也是未來的研究方向。

參考文獻：

[1]Blaze M， Bleumer G， Strauss M， et al. Divertible protocols and atomic proxy cryptography［M］//Theory and Application of Cryp-tographic Techniques.1998：127-144.

［2]Green M， Ateniese G. Identity-based proxy re-encryption［M］//Applied Cryptography and Network Security.2007：288-306.

［3]Xagawa K. Cryptography with lattices［D］.Tokyo：Tokyo Institute of Technology，2010.

［4]Singh K， Rangan C P， Banerjee A K. Lattice-based identity based unidirectional proxy re-encryption scheme［C］//Proc of International Conference on Security， Privacy， and Applied Cryptography Engineering.2014：76-91.

［5]湯永利，劉琦，張曉航，等.格上基于RLWE難題的身份基代理重加密方案［J］.計算機應用研究，2021，38（4）：1199-1202.（Tang Yongli， Liu Qi， Zhang Xiaohang， et al. Identity-based proxy re-encryption scheme based on RLWE problem［J］.Application Research of Computers，2021，38（4）：1199-1202.）

［6]Kim K S， Jeong I R. Collusion-resistant unidirectional proxy re-encryption scheme from lattices［J］.Journal of Communications and Networks，2016，18（1）：1-7.

［7]Wang Xuyang， Hu Aiqun， Fang H. Improved collusion-resistant unidirectional proxy re-encryption scheme from lattice［J］.IET Information Security，2020，18（1）：342-351.

［8]Dutta P， Susilo W， Duong D H， et al. Collusion-resistant identity-based proxy re-encryption： lattice-based constructions in standard model［J］.Theoretical Computer Science，2021，871：16-29.

［9]Wang Xu’an， Ge Yunlong， Yang Xiaoyuan. PRE+： dual of proxy re-encryption and its application［J］.International Journal of Web and Grid Services，2018，14（1）：44-69.

［10]Singh K， Rangan C P， Agrawal R， et al. Provably secure lattice based identity based unidirectional PRE and PRE+ schemes［J］.Journal of Information Security and Applications，2020，54（3/4）：102569.

［11]Ateniese G， Fu K， Green M， et al. Improved proxy re-encryption schemes with applications to secure distributed storage［J］.ACM Trans on Information and System Security，2006，9（1）：1-30.

［12]Guo Hui， Zhang Zhenfeng， Xu Jing， et al. Non-transferable proxy re-encryption［J］.The Computer Journal，2019，62（4）：490-506.

［13]Guo Hui， Zhang Zhenfeng， Xu Jing， et al. Accountable proxy re-encryption for secure data sharing［J］.IEEE Trans on Dependable and Secure Computing，2021，18（1）：145-159.

［14]Ajtai M. Generating hard instances of lattice problems［C］//Proc of the 28th ACM Symposium on Theory of Computing.New York：ACM Press，1996：99-108.

［15]Gentry C， Peikert C， Vaikuntanathan V. How to use a short basis： trapdoors for hard lattices and new cryptographic constructions［C］//Proc of the 40th ACM Symposium on Theory of Computing.2008：197-206.

［16]王鳳和，胡予濮，賈艷艷.標準模型下的格基數字簽名方案［J］.西安電子科技大學學報，2012，39（4）：57-61，119.（Wang Fenghe， Hu Yupu， Jia Yanyan. Lattice-based signature scheme in the standard model［J］.Journal of Xidian University，2012，39（4）：57-61，119.）

［17]Micciancio， D， Peikert C. Hardness of SIS and LWE with small parameters［C］//Proc of the 33rd Annual International Cryptology Conference.2013：21-39.

［18]Regev O. On lattices， learning with errors， random linear codes， and cryptography［C］//Proc of the 37th Annual ACM Symposium on Theory of Computing.New York：ACM Press，2005：84-93.

［19]Wang Xuyang， Hu Aiqun， Hao Fang. Feasibility analysis of lattice-based proxy re-encryption［C］//Proc of the 17th International Confe-rence on Cryptography，Security and Privacy.2017：12-16.

［20]Hou Jinqiu， Jiang Mingming， Guo Yuyan， et al. Efficient identity-based multi-bit proxy re-encryption over lattice in the standard model［C］//Proc of International Conference on Frontiers in Cyber Secu-rity.Berlin：Springer，2019：329-334.

［21]Kirshanova E. Proxy re-encryption from lattices［C］//Proc of the 17th International Conference on Public-Key Cryptography.2014：77-94.

收稿日期：2021-12-01；

修回日期：2022-01-14

基金項目：國家自然科學基金資助項目（61802117）；河南省高校科技創新團隊項目（20IRTSTHN013）；河南理工大學博士基金資助項目（B2013-037）

作者簡介：孟慧（1981-），女（通信作者），河南焦作人，副教授，碩導，博士，主要研究方向為網絡信息安全（menghui@hpu.edu.cn）；任利娜（1998-），女，河南濮陽人，碩士研究生，主要研究方向為網絡與信息安全；李英（1998-），女，河南南陽人，碩士研究生，主要研究方向為網絡與信息安全.