多屬性環(huán)境下基于容錯(cuò)學(xué)習(xí)的全同態(tài)加密方案

白 平，張 薇

(1．武警工程大學(xué)密碼工程學(xué)院，西安710086; 2．武警工程大學(xué)信息安全保密重點(diǎn)實(shí)驗(yàn)室，西安710086)(*通信作者電子郵箱bp15771937011@163．com)

0 引言

近年來，隨著云計(jì)算技術(shù)［1］快速發(fā)展，大量用戶將個(gè)人隱私數(shù)據(jù)存放或運(yùn)行在外部云服務(wù)器上，然而，用戶在獲得便利的同時(shí)，數(shù)據(jù)共享、隱私保護(hù)等相關(guān)一系列問題逐漸凸顯出來。至今為止，在實(shí)際應(yīng)用中這些問題依然沒有找到一種高效且實(shí)用的解決辦法，有關(guān)云計(jì)算安全問題依然是密碼學(xué)界的研究熱點(diǎn)。為了能很好地解決上述問題，在密碼學(xué)領(lǐng)域中“全同態(tài)加密”技術(shù)應(yīng)運(yùn)而生。2009年，Gentry［2］提出基于理想格(Ideal Lattice)上的最短向量問題(Shortest Vector Problem，SVP)，構(gòu)造出了第一代能夠真正實(shí)現(xiàn)全同態(tài)加密的體制。此后，對(duì)于全同態(tài)密碼的研究便成為了密碼學(xué)界一個(gè)新的研究熱點(diǎn)［3－6］。

2011 年，Brakerski等［7］提出基于容錯(cuò)學(xué)習(xí)(Learning With Errors，LWE)困難問題的全同態(tài)加密體制，基于LWE問題的公鑰加密體制繼承了格上密碼體制的優(yōu)勢(shì)，且具有簡(jiǎn)單的計(jì)算形式。2013年，Gentry等［8］提出了一種全新的層次型全同態(tài)加密方案(GSW13方案)，這個(gè)方案優(yōu)點(diǎn)在于擺脫了Gentry框架而完全基于LWE問題，去除了運(yùn)算密鑰，利用“近似特征向量”的技術(shù)實(shí)現(xiàn)矩陣同態(tài)加法和矩陣同態(tài)乘法的特性，從而實(shí)現(xiàn)了層次型全同態(tài)。屬性加密最初由Sahai等［9］在2005年提出，是一種具有良好訪問控制特性的加密方式，具有如下3個(gè)優(yōu)良的性質(zhì):1)加密者只需知道明文對(duì)應(yīng)的屬性即可加密，無需了解明文消息的具體內(nèi)容，從而在一定程度上保護(hù)了用戶隱私;2)只有正確掌握屬性信息的用戶才能夠解密，從而保證數(shù)據(jù)的安全性;3)基于屬性加密(Attribute Based Encryption，ABE)機(jī)制支持基于屬性的靈活訪問控制策略，可以實(shí)現(xiàn)屬性的與、或、非和門限操作。在屬性加密系統(tǒng)中，密文不需要以傳統(tǒng)的公鑰密碼體制加密給一個(gè)特定用戶，而是用戶的私鑰和密文與一個(gè)屬性集或?qū)傩陨系牟呗韵嚓P(guān)聯(lián)，當(dāng)且僅當(dāng)用戶的私鑰和密文相匹配時(shí)，用戶才能夠解密得到正確的明文。

本文針對(duì) Gentry、Sahai和 Waters［8］描述的 GSW13 編譯器只能夠在單屬性環(huán)境下工作的不足，通過借鑒“模糊系統(tǒng)”技術(shù)實(shí)現(xiàn)了多屬性環(huán)境下的全同態(tài)加密。實(shí)現(xiàn)多屬性加密主要有以下兩層意義:1)對(duì)于單個(gè)用戶來說，屬性個(gè)數(shù)的增加能夠很好地增強(qiáng)用戶外包數(shù)據(jù)的訪問控制權(quán)限，從而減少用戶外包數(shù)據(jù)泄露的概率。2)對(duì)于多個(gè)用戶來說，能夠在保證各自用戶數(shù)據(jù)不泄露的情況下，實(shí)現(xiàn)在不同的屬性加密情況下，多個(gè)用戶可以共享彼此外包數(shù)據(jù)，從而實(shí)現(xiàn)了數(shù)據(jù)的最大利用率。此外，構(gòu)造的方案可以實(shí)現(xiàn)如下功能:可以將滿足一定屬性要求的ABE方案轉(zhuǎn)換成多屬性環(huán)境下的全同態(tài)加密方案，進(jìn)一步提高了用戶外包數(shù)據(jù)的安全性和實(shí)用性，提升了全同態(tài)加密在云計(jì)算外包過程中的運(yùn)用。

1 預(yù)備知識(shí)

1．1 容錯(cuò)學(xué)習(xí)問題［10］

在正式定義LWE之前，首先介紹幾個(gè)相關(guān)的概率分布:

1)將整數(shù)域Zq上以0為中心為標(biāo)準(zhǔn)差的離散正態(tài)分布稱為“誤差分布”，記為χ。

定義1 設(shè)定模數(shù)q=q(χ)，存在矩陣A和向量v，使得v=As+e，其中A∈Znq，s∈Zq分別在Znq和Zq中依均勻分布隨機(jī)選擇，小變量 e在Znq上服從誤差分布 χ。LWEn，m，q，χ問題可描述為:給出m個(gè)As，χ分布上相互獨(dú)立的變量，求其對(duì)應(yīng)的向量 s。

1．2 基于屬性的同態(tài)加密方案體制模型

一個(gè)基于屬性的同態(tài)加密體制為 ABHE=(Setup，KeyGen，Enc，Dec，Eval)，主要由以下5個(gè)具體算法構(gòu)成:

初始化算法Setup(1λ)。輸入安全參數(shù)λ，輸出公開參數(shù)params和用戶主私鑰MSK。定義一個(gè)環(huán)R、函數(shù)集F和計(jì)算關(guān)系式:R(x，y)，x ∈ {0，1}k，y∈ {0，1}l，其中 k，l為任意參數(shù)。設(shè)定運(yùn)算電路為 Ω:{0，1}t→ {0，1}，電路深度為 L。

私鑰生成算法KeyGen(MSK，y)。由主私鑰MSK和參數(shù)y生成用戶私鑰sky，其中y∈{0，1}l。隨后對(duì)屬性x進(jìn)行哈希運(yùn)算得到用戶公鑰pkx，x∈{0，1}k，將用戶私鑰sky返回給擁有屬性x的用戶。

加密算法 Enc(params，pkx，μ)。輸入公開參數(shù)params、用戶公鑰pkx和明文消息μ，輸出密文c。

解密算法 Dec(sky，c')。若滿足式 R(x，y)=1，則可根據(jù)用戶私鑰sky和密文c'，解密得到明文μ';若R(x，y)≠1，則解密中止，輸出無效符號(hào)⊥。

密文運(yùn)算算法 Eval(params，Ω，c1，c2，…，ct)。由公開參數(shù)params、事先設(shè)定的運(yùn)算電路Ω以及用相同屬性值x加密的一組密文{c1，c2，…，ct}，輸出一個(gè)新密文 c'，即 Ω(c1，c2，…，ct) → c'。

定義2 假設(shè)ξ表示一個(gè)滿足以下3個(gè)屬性的ABE方案:

1)屬性x對(duì)應(yīng)的解密密鑰sky和密文c都是Zm'q上的向量，并且sky的第一個(gè)元素系數(shù)是1。

2)如果c是明文0對(duì)應(yīng)的密文，則〈cx，sky〉是比較小的。

3)對(duì)明文0的加密結(jié)果與Zq上的一般向量不可區(qū)分。

則ξ的模糊系統(tǒng) OSξ可表示為 OSξ=(GenUnivObs，DeriveObs)，其中兩個(gè)概率多項(xiàng)式時(shí)間算法滿足如下定義:

1)GenUnivObs(params，id，μ)。輸入方案 ξ的公共參數(shù)params、屬性信息x和明文μ∈{0，1}，輸出泛模糊信息U∈{0，1}*。

2)DeriveObs(params，U，x')。輸入方案 ξ的公共參數(shù)params，泛模糊信息U∈{0，1}*和一個(gè)屬性信息x'，輸出一對(duì)矩陣

上述定義的模糊系統(tǒng)OSξ滿足以下屬性:

正確性 對(duì)于任意(params，MSK)← ξ．Setup(1λ)，任意屬性信息x，x'，私鑰vx=Powerof2(x．KeyGen(MSK，x)) ∈和 vx'=Powerof2(ξ．KeyGen(msk，x')) ∈ ZNq，明文 μ ∈ {0，1}以及所有的 U ← GenUnivObs(params，x，μ)和(X，Y)←DeriveObs(params，U，x')，均滿足如下的關(guān)系式:其中e為允許范圍內(nèi)極小誤差值。

安全性 在改進(jìn)過的方案ξ的基于X不可區(qū)分的選擇明文攻擊(INDistinguishability-X-Chosen Plain Attack，IND-XCPA)游戲中，所有的概率多項(xiàng)式時(shí)間攻擊者以可忽略的優(yōu)勢(shì)取勝，則稱模糊系統(tǒng)是安全的。改進(jìn)的IND-X-CPA游戲所做的唯一改變是將原來游戲中的挑戰(zhàn)密文更換為U*←GenUnivObs(params，x*，μb)，其中是挑戰(zhàn)者所選的隨機(jī)比特位，x*是攻擊者所選的攻擊屬性，μ0，μ1是由攻擊者所選擇的挑戰(zhàn)明文。

1．3 GSW13方案構(gòu)造過程

2013年，Gentry等［8］提出了一個(gè)新的基于LWE困難假設(shè)的全同態(tài)加密體制(簡(jiǎn)稱GSW13方案)，這個(gè)方案的優(yōu)點(diǎn)在于只需要一些系統(tǒng)基本參數(shù)就能夠?qū)崿F(xiàn)方案的同態(tài)運(yùn)算操作，消除了以往方案中對(duì)解密密鑰的依賴。這一技術(shù)的突破使得構(gòu)造全同態(tài)加密體制邁進(jìn)了一大步，使得在真正意義上實(shí)現(xiàn)全同態(tài)加密成為了可能。具體的算法過程如下:

密鑰生成算法KeyGen(params，λ，L)主要分為如下3個(gè)算法。

1)參數(shù)生成算法Setup(1λ，1L)。選擇一個(gè)模數(shù)q，并且模數(shù)q位數(shù)大小為κ=κ(λ，L)比特，格的大小n由函數(shù)n=n(λ，L)生成，容錯(cuò)學(xué)習(xí)(LWE)問題中的誤差分布記為:χ=χ(λ，L)。選取參數(shù) m=m(λ，L)=O(n lb q)，則令 params=(n，q，χ，m)，l=?lb q」+1，N=(n+1)·l。

2)私鑰生成算法SecretKeyGen(params)。從Znq中選取一個(gè)參數(shù)作為樣本，記為t，輸出私鑰sk=s←(1，－t1，…，－tn)∈Zn+1q。同時(shí)，令v=Powerof2(s)。

3)公鑰生成算法 PublicKeyGen(params，sk)。產(chǎn)生矩陣B ←Zm×nq和向量e←χm。令b=B·t+e，e表示一個(gè)誤差向量，A可表示為由矩陣B和矩陣b的第n+1列所組成的矩陣，即Am×(n+1)=(B，b)。公鑰 pk=A。

加密算法 Encrypt(params，pk，μ)。

選擇明文消息μ∈Zq和由數(shù)字0和1兩種元素組成的矩陣Q，輸出密文矩陣:

C=Flatten(μ·IN+BitDecomp(Q·A)) ∈ ZN×Nq其中IN為N維單位矩陣。

解密算法 Decrypt(params，sk，C)。

記私鑰生成算法SecretKeyGen(params)中得到的向量v的前 l個(gè)元素系數(shù)為 1，2，…，2l－1，從中選取滿足 vl=2l∈(q/4，q/2］的系數(shù)并標(biāo)記為 i，計(jì)算 xi←〈Ci，v〉= μ·vi+e，其中Ci代表密文C的第i行。由于e表示一個(gè)小誤差向量，vi則表示一個(gè)擁有大系數(shù)的N維向量，故可以通過μ'=?xi/vi」來解密求得明文μ'。

下面簡(jiǎn)要介紹一下GSW13方案同態(tài)操作。

GSW13方案的同態(tài)性質(zhì)主要分為以下4個(gè)部分:乘以常量的同態(tài)操作MultConst、加法同態(tài)操作Add、乘法同態(tài)操作Mult和與非門運(yùn)算時(shí)同態(tài)操作NAND。

1)MultConst:

用已知常量α∈Zq同密文矩陣C∈ZN×Nq進(jìn)行相乘運(yùn)算，定義 Mα←Flatten(α·IN)，輸出 Flatten(Mα·C)。

由于e是一個(gè)可忽略不計(jì)的小誤差向量，所以對(duì)于密文矩陣C的常量乘等于明文的常量乘，能夠滿足正確解密的條件。

2)Add(C1，C2):

對(duì)于密文 C1，C2∈ ZN×Nq

可以看出誤差的增長(zhǎng)主要來源來誤差向量e1+e2增長(zhǎng)，這不會(huì)影響解密操作。

3)Mult(C1，C2):

對(duì)于密文 C1，C2∈ ZN×Nq，有:

在乘法同態(tài)的運(yùn)算中可以看出，新的誤差增長(zhǎng)主要來源于密文矩陣C1和明文消息μ2。由于矩陣C1已經(jīng)在加密過程中被限制C1∈{0，1}中，主要的目標(biāo)是要限制明文消息μ2的增長(zhǎng)。為此，可以引入布爾電路，通過與非門將其限制在{0，1}中，從而保證乘法同態(tài)運(yùn)算的正確性。

4)NAND(C1，C2):

對(duì)于密文 C1，C2∈ ZN×Nq，則

對(duì)于與非操作，同態(tài)操作的正確性取決于μ2·e1－C1·e2的大小，只要保持明文μ2在{0，1}范圍內(nèi)，則可保證操作運(yùn)算的正確性。

1．4 扁平技術(shù)

如果C1和C2分別是明文消息 μ1∈{0，1}和μ2∈{0，1} 對(duì)應(yīng)的密文矩陣，即 Cj·v= μj·v+ej(其中 j∈ {0，1}，ej表示極小誤差向量)，兩個(gè)密文矩陣的上界為B。則加法同態(tài)C+=C1+C2以2B為界限，乘法同態(tài)C×=C1·C2以(N+1)B2為界限。為了確保運(yùn)算操作過程中的正確性，使得解密結(jié)果保持在{0，1}范圍內(nèi)。因此需要運(yùn)算其他技術(shù)手段來保持密文矩陣的每一項(xiàng)都足夠小，本文借鑒文獻(xiàn)［11］提出的一種被稱為“扁平技術(shù)”的Flatten操作。

定義a和b是維度大小為k的向量，設(shè)定l=?lb q」+1、N= k · l 和 BitDecomp(a) =(a1，0，…，a1，l－1，…，ak，0，…，ak，l－1)，其中 ai，j是指 ai二進(jìn)制中的第 j位。同時(shí)，令 a'=(a1，0，…，a1，l－1，…，ak，0，…，ak，l－1)，則 BitDecomp 的逆可表示為 BitDecomp－1(a')=假如輸出結(jié)果不在有效的解密范圍{0，1}內(nèi)，則令Flatten(a')=BitDecomp(BitDecomp－1(a'))，其中 a'表示 N 維{0，1} 的向量。BitDecomp(A)，BitDecomp－1(A) 和 Flatten(A) 對(duì)于矩陣A的操作是對(duì)A的每一行進(jìn)行單獨(dú)操作。令Powerof2(b)=(b1，2b1，…，2l－1b1，…，bk，2bk，…，2l－1bk)，其結(jié)果是一個(gè) N 維{0，1} 向量。

具有如下兩個(gè)性質(zhì):

1) 〈BitDecomp(a)，Powerof2(b)〉=〈a，b〉

2)對(duì)于任意N維向量a'，有如下等式:

〈a'，Powerof2(b)〉=〈BitDecomp－1(a')，b〉=

〈Flatten(a')，Powerof2(b')〉

1．5 密文擴(kuò)展算法

為了能夠滿足GSW13方案中所要求的矩陣形式，經(jīng)過不同屬性值加密所得的密文矩陣需要經(jīng)過必要的轉(zhuǎn)換才能符合要求。定義由不同屬性xi(i=1，2，…，υ)加密明文μ得到的密文矩陣為 Ci(i=1，2，…，υ)，用 C^ ∈ ZυN×υNq表示相對(duì)應(yīng)的“擴(kuò)展矩陣”，同時(shí)要求這個(gè)擴(kuò)展矩陣必須滿足如下形式:

對(duì)于:

1)計(jì)算 (Xi+Yj) ← OSξ．DeriveObs(params，U，xi);

2)設(shè)置 C^i，j← Yi;

3)設(shè)置 C^i，j← Flatten(C^i，j+Xi)。

2 應(yīng)用場(chǎng)景分析和系統(tǒng)模型構(gòu)建

2．1 多屬性環(huán)境下全同態(tài)加密方案應(yīng)用場(chǎng)景

考慮這樣一個(gè)具體的應(yīng)用場(chǎng)景:設(shè)想A和B均是某公司的員工，但是A和B不在同一個(gè)地方工作。假如現(xiàn)在公司要求A和B共同來完成一個(gè)項(xiàng)目，A和B為了更加便利地分享彼此的信息，通常會(huì)將各自的數(shù)據(jù)資料加密后存儲(chǔ)在不完全可信的第三方云服務(wù)器E上，其中A和B的數(shù)據(jù)資料是分別使用各自的屬性信息生成的私鑰skxA和skxB進(jìn)行加密的。本文想要實(shí)現(xiàn)這樣一個(gè)目的:允許A和B對(duì)彼此的加密的密文進(jìn)行某些運(yùn)算操作，用C表示運(yùn)算后的密文。根據(jù)以上的描述可知所得的密文C是使用了A和B各自的屬性信息密鑰共同加密的，所以計(jì)算結(jié)果只能由A和B共同解密。具體如圖1所示。

針對(duì)Gentry，Sahai和Waters提出的基于LWE全同態(tài)加密方案中只能在單屬性環(huán)境下工作的局限性的問題，本文主要想解決的問題是突破方案中單個(gè)屬性的限制，構(gòu)造一個(gè)在多屬性環(huán)境下的全同態(tài)方案。設(shè)想這樣一個(gè)實(shí)際的環(huán)境:用戶A使用屬性x1對(duì)明文消息μ1∈{0，1}進(jìn)行加密得到密文矩陣CT1，用戶B使用屬性x2對(duì)明文消息μ2∈{0，1}進(jìn)行加密得到密文矩陣CT2。假如想要實(shí)現(xiàn)2．1節(jié)中所提的目的，那么具體操作步驟如下:第一步是將得到的兩個(gè)密文矩陣CT1和CT2運(yùn)用某種方法進(jìn)行轉(zhuǎn)換;第二步是將轉(zhuǎn)換得到的結(jié)果輸入到運(yùn)算電路Ω中。顯然，可以得到一個(gè)新的密文矩陣C^'，其對(duì)應(yīng)的新明文為 μ'= Ω(μ1，μ2)，根據(jù)GSW13方案的構(gòu)造框架，可以表示為:

其中small表示可忽略的一個(gè)參數(shù)。

在上述具體操作過程中，可以發(fā)現(xiàn)存在的主要問題在于第一步中如何對(duì)不同的密文矩陣進(jìn)行變換?由于加密的屬性信息x1≠x2的原因，產(chǎn)生的密文矩陣Ci(i=1，2)也是不同，故不能直接進(jìn)行加乘運(yùn)算。需要借助其他有效方法進(jìn)行轉(zhuǎn)換，以期滿足同態(tài)的緊湊性條件。本方案的主要思想是通過借助“模糊系統(tǒng)”技術(shù)將不同的密文矩陣轉(zhuǎn)換成相應(yīng)的“擴(kuò)展矩陣”以滿足GSW13構(gòu)造框架中C^'。

圖1 加密方案應(yīng)用場(chǎng)景Fig．1 Application scene of encryption scheme

2．2 多屬性環(huán)境下基于LWE全同態(tài)加密方案的系統(tǒng)模型

本方案主要是在屬性加密方案(ABE)基礎(chǔ)上進(jìn)行擴(kuò)展延伸的，普通的ABE方案通過GSW13編譯器可以轉(zhuǎn)換為單個(gè)屬性環(huán)境下不完全的全同態(tài)加密方案，更進(jìn)一步如果符合定義2所描述的3個(gè)屬性，則可進(jìn)一步轉(zhuǎn)換成單個(gè)屬性環(huán)境下可自舉不完全的全同態(tài)加密方案，本方案的改進(jìn)地方是在可自舉的方案的基礎(chǔ)上繼續(xù)借鑒一種稱為“模糊系統(tǒng)”的技術(shù)，將方案轉(zhuǎn)換為可以在多個(gè)屬性環(huán)境下的不完全的全同態(tài)加密方案。為了直觀了解本方案的構(gòu)造過程，下面用圖2進(jìn)行說明。

圖2 系統(tǒng)模型示意圖Fig．2 Schematic diagram of system model

3 基于LWE的全同態(tài)加密方案

3．1 方案構(gòu)造

基于2．2節(jié)中所提出的系統(tǒng)模型，下面將構(gòu)造一個(gè)方案，目標(biāo)是將屬性符合定義2中要求的ABE方案能夠轉(zhuǎn)化成支持多屬性環(huán)境下的全同態(tài)加密方案。方案ξMAS主要包括以下5個(gè)算法，分別描述如下:

初始化算法 ξMAS．Setup(1λ)。輸入安全參數(shù) λ，輸出公開參數(shù)params和系統(tǒng)主私鑰MSK。選取f∈F，定義用戶屬性集合為 I={x1，x2，…，xυ}，隨機(jī)選取參數(shù) y，要求滿足等式R(xi∈I，y)=1。

私鑰生成算法 ξMAS．KeyGen(MSK，y)。由系統(tǒng)主私鑰MSK和參數(shù)y∈{0，1}*，生成得到用戶的一個(gè)私鑰sky，將此私鑰返回給擁有屬性xi，i∈{1，2，…，υ}并且滿足條件等式R(xi，y)=1 的用戶。

加密算法 ξMAS．Enc(params，xi，μ)。輸入明文 μ 和屬性信息 xi， 運(yùn) 行 加 密 機(jī) 得 到 泛 模 糊 信 息:U ←OSξ．GenUnivObs(params，xi，μ)，輸出密文 CT=(xi，type=0，enc=U)。其中type=0表示“刷新過的”密文。

密文運(yùn)算算法 ξMAS．Eval(Ω，CT1，CT2，…，CTυ)。輸入CTj=(xi，type=0，enc=Uj)，i=1，2，…，υ，不同屬性的集合為 I=(x1，x2，…，xυ)，用=υ表示屬性集合中屬性的數(shù)

解密算法 ξMAS·Dec(vx1，vx2，…，vxk，CT=(x1，x2，…，xυ，type，enc))。輸入密文 CT=(x1，x2，…，xυ，type，enc) 和私鑰序列vx1，vx2，…，vxυ(其中vxi是指屬性xi對(duì)應(yīng)的向量私鑰，其中i∈解密機(jī)通過執(zhí)行以下步驟可以得到泛模糊信息。垂直連接排列列向量vx1，vx2，…，vxυ組成向量v。

1)若type=0，則enc表示泛模糊信息U，計(jì)算(X，Y)←OSξ．DeriveObs(params，xi，U)，并且設(shè)置 C ← X+Y;

2)若type=1，則enc表示C^并且設(shè)置C←C^;

選擇滿足 vi=2i∈ (q/4，q/2］的 i，計(jì)算 di←〈ci，v〉=μ·vi+e，其中 ci是指矩陣 C 的第 i行，輸出 μ'←?di/vi」∈{0，1}，其中μ'表示解密恢復(fù)的明文消息。

3．2 方案正確性分析

為了更好地說明方案的正確性，可以通過實(shí)例進(jìn)行說明:令υ=2，j=1。將兩個(gè)不同的屬性值輸入同一種加密機(jī)(加密機(jī)沒有硬性規(guī)定，只要是同一種即可)中得到密文矩陣分別滿足 CT1·vx1= μ1·vx1+e1和 CT2·vx2= μ2·vx2+e2，其中 vx1=Powerof2(x1)，vx2=Powerof2(x2)。運(yùn)用1．5 節(jié)中的密文擴(kuò)展算法將這兩個(gè)密文矩陣CTi都轉(zhuǎn)換成如下形式:量。在運(yùn)算執(zhí)行之前，必須對(duì)每個(gè)密文矩陣CTi運(yùn)行密文擴(kuò)展算法將其轉(zhuǎn)換成符合要求相對(duì)應(yīng)的υN×υN擴(kuò)展矩陣C^，而后使用運(yùn)算電路Ω對(duì)擴(kuò)展矩陣C^進(jìn)行與非門操作運(yùn)算，產(chǎn)生符合GSW13構(gòu)造框架中所要求的矩陣C^'。假設(shè)每個(gè) C^對(duì)應(yīng)的明文消息是μi∈{0，1}，則 C^'對(duì)應(yīng)的明文消息是C(μ1，μ2，…，μυ)。最后，密文運(yùn)算算法輸出的密文形式為CT'=(x1，x2，…，xυ，type=1，enc=C^')，其中 type=1 表示是一個(gè)運(yùn)算密文。

經(jīng)過轉(zhuǎn)換后的密文形式具有相同的形式，故可以進(jìn)行同態(tài)的加乘運(yùn)算，最后將C^輸入到預(yù)先設(shè)定的運(yùn)算電路中即可。同樣在解密過程中，可以用和加密機(jī)相對(duì)應(yīng)的解密機(jī)進(jìn)行解密，解密機(jī)通過判斷密文中type的值，從而確定所求密文矩陣，最后計(jì)算 di←〈ci，v〉= μ·vi+e和μ'←?di/vi」∈{0，1}，則可以得到明文消息μ'。

4 方案的分析

4．1 安全性分析

該方案構(gòu)造的多屬性環(huán)境下的全同態(tài)加密方案與普通的基于屬性的加密方案相比除了在屬性的數(shù)量上有所增加外，主要區(qū)別是增加了一個(gè)密文運(yùn)算算法 ξMAS．Eval(Ω，CT1，CT2，…，CTυ)。然而，此算法的增加并不會(huì)影響基于屬性加密方案的安全性［12］，故該方案的安全性證明類似于屬性加密方案的安全性證明。在確保方案安全性的基礎(chǔ)上，本文還要在同態(tài)運(yùn)算為與非操作的可行性進(jìn)行證明。

定義3 多項(xiàng)式函數(shù)μ(x):Ν→R，如果對(duì)于任何一個(gè)正多項(xiàng)式poly(n)，有一個(gè)自然數(shù) c，使得對(duì)于所有 x＞c，有μ(x) ＜［1/poly(x)］，則稱函數(shù)μ是可忽略的，記為negl(x)。

初始化 挑戰(zhàn)者B執(zhí)行初始化算法Setup(1λ)，生成公開參數(shù)params，系統(tǒng)主私鑰MSK，將params發(fā)送給敵手A。

階段1 敵手A隨意選擇兩個(gè)長(zhǎng)度相等的明文(μ1，μ2)和一個(gè)挑戰(zhàn)屬性信息x*發(fā)送給挑戰(zhàn)者B，而后敵手A對(duì)不同的屬性信息xi所對(duì)應(yīng)的私鑰進(jìn)行詢問。挑戰(zhàn)者B通過調(diào)用私鑰生成算法KeyGen(MSK，y)得到相應(yīng)的sky，隨后發(fā)送給敵手A。

挑戰(zhàn)過程 敵手A隨意選擇兩個(gè)長(zhǎng)度相等的明文(μ1，μ2)和一個(gè)挑戰(zhàn)屬性信息x*發(fā)送給挑戰(zhàn)者B，其中x*xi，即屬性信息x*不存在于屬性集合I={x1，x2，…，xυ}中。挑戰(zhàn)者B隨機(jī)選取明文下角標(biāo)b∈{0，1}，用屬性信息x*對(duì)μi進(jìn)行加密，得到目標(biāo)密文Enc(params，pkx，μ)→c，并將其發(fā)送給敵手A。

階段2 挑戰(zhàn)者B繼續(xù)給敵手A發(fā)送屬性信息xi的私鑰sky，敵手A適應(yīng)性地選擇挑戰(zhàn)者B的輸入。要求x*I={x1，x2，…，xυ}。

猜測(cè)過程 敵手A猜測(cè)目標(biāo)密文c所對(duì)應(yīng)的明文，輸出相應(yīng)的b'作為敵手A的猜測(cè)結(jié)果。

定義4 B界分布。令B＜q代表一個(gè)整數(shù)，對(duì)于C·v=μ·v+e，如果μ的量級(jí)不大于B，則稱密文C對(duì)于v是B為界的，C的每一項(xiàng)的量級(jí)不大于B，并且‖e‖∞≤B。

定理1 設(shè)L和D均為正整數(shù)，w為誤差因子，如果q＞8w·B(DN+1)L，則方案ξMAS是正確的，并且對(duì)任意υ≤D個(gè)不同的屬性，都可以進(jìn)行深度為L(zhǎng)的與非正確運(yùn)算。

證明 設(shè)υ≤D個(gè)不同的屬性x1，x2，…，xυ參與運(yùn)算，與屬性xi，i∈υ相關(guān)的“刷新過的”新密文為CT=(xi，type=0，enc=U)，由這些新密文轉(zhuǎn)換得到擴(kuò)展矩陣，將v1，v2，…，vυ按照列的形式串聯(lián)組成向量^v，C^表示CT對(duì)應(yīng)的擴(kuò)展矩陣，用對(duì) 應(yīng) 的 屬 性 信 息 x1，x2，…，xυ計(jì) 算 (Xj，Yj) ← OSξ．DeriveObs(params，U，xj)，根據(jù)構(gòu)造過程，C^包含υ × υ個(gè)ZN×Nq上子矩陣，其中N－1行都包含兩個(gè)非零子矩陣，只有第i行包含一個(gè)非零子矩陣。則可得到如下等式:

由于每個(gè)子矩陣都滿足定義4中的B界分布，因此C^·^v=μ·^v+^e的誤差向量^e的系數(shù)是以w·B為界的。在與非運(yùn)算中乘以 υN×υN個(gè)擴(kuò)展矩陣的操作會(huì)產(chǎn)生一個(gè)以B(υN+1)為強(qiáng)界的矩陣。連續(xù)進(jìn)行L次同態(tài)運(yùn)算后，誤差的界限變成w·B(υN+1)L。為了正確解密需要滿足條件w·B(υN+1)L＜ q/8，由 υ≤D。故可知:

w·B(υN+1)L≤ w·B(DN+1)L≤

［8·w·B(DN+1)L］/8≤ q/8

4．2 性能分析

Gentry等［8］提出了基于LWE的全同態(tài)加密方案，本方案是在GSW13方案的基礎(chǔ)上進(jìn)行了改進(jìn)，實(shí)現(xiàn)在多屬性環(huán)境下的全同態(tài)加密。本方案與GSW13方案有相同點(diǎn)和不同點(diǎn)。與GSW13相比，兩個(gè)方案的相同點(diǎn)是方案都是基于LWE困難性假設(shè)進(jìn)行討論的。另外，與GSW13方案相比，主要有以下幾點(diǎn)不同地方:1)本方案在工作環(huán)境方面較GSW13有一定的提高，可以支持在多屬性環(huán)境下的全同態(tài)加密方案，克服了GSW13方案中單個(gè)屬性的局限性。2)在安全性方面，本文除了對(duì)安全性進(jìn)行了必要的證明，同時(shí)對(duì)方案的正確性和進(jìn)行與非門操作時(shí)的可行性進(jìn)行了說明。3)在效率方面，由于將單個(gè)屬性擴(kuò)展到多個(gè)屬性的緣故，整個(gè)方案中增加了一些參數(shù):如運(yùn)算電路可支持的最大屬性值模糊系統(tǒng)中的參數(shù)、矩陣等，導(dǎo)致了效率較GSW13有所下降。由于全同態(tài)加密方案普遍效率比較低，距離真正實(shí)際應(yīng)用還有一定距離，本文在性能分析描述中對(duì)效率沒有作具體的量化，其中效率的高低只是3個(gè)方案的相對(duì)比較。具體對(duì)比如表1。

表1 幾種加密方案性能對(duì)比分析Tab．1 Performance comparison analysis of several encryption schemes

通過表1可以得出，本方案與文獻(xiàn)［8］中Gentry的方案相比，優(yōu)點(diǎn)是能夠支持在多個(gè)屬性環(huán)境下的全同態(tài)加密操作，實(shí)現(xiàn)在保證不同用戶數(shù)據(jù)不被泄露的情況下，使得擁有不同屬性值的多個(gè)用戶共享彼此的隱私信息，實(shí)現(xiàn)了用戶數(shù)據(jù)的最大利用率，從而在一定程度上增強(qiáng)了外包用戶數(shù)據(jù)的可操作性，擴(kuò)展了全同態(tài)加密在云環(huán)境領(lǐng)域中的應(yīng)用范圍。

5 結(jié)語

本文通過將模糊系統(tǒng)技術(shù)引入到GSW13方案中，構(gòu)造了一個(gè)適用于云環(huán)境的多屬性環(huán)境下基于LWE的全同態(tài)加密方案，通過利用模糊系統(tǒng)的特性，主要解決了不同用戶的外包數(shù)據(jù)的共享性問題，提高了用戶外包數(shù)據(jù)的實(shí)用價(jià)值。下一步的工作是探索能夠適用于本方案的具體實(shí)例環(huán)境，構(gòu)造出真正意義能夠?qū)嶋H應(yīng)用的全同態(tài)加密方案。