云存儲是未來信息存儲的一種理想方式，它提供方便易用的外包存儲空間，以緩解爆炸增長的信息對存儲空間的海量需求，然而，數據的存儲存在著安全與隱私泄露等問題，致使云存儲服務的推廣與普及存在困難。針對用戶各數據的安全需求，我們提出了一高效的線性同態(tài)加密方案( IHES)，其安全性基于多項式環(huán)上差錯學習(R-IWE)問題的困難性。

一、基礎知識

1、格

格是n維空間中一類具有周期性結構離散點的集合，具體描述如下：

定義1己知，n個線性無關的向量b1，…，bn∈Rm，則格定義為:

其中，b1，…，bn稱為格的一組基，秩為n。

下面以判定形式給出最壞情形下近似最短向量問題（GapSVPr）。

定義2（GapSVP ）已知(B，d)為GapSVPr的輸入，其中B為-n維格的基，deR。

如果λ1(L(B))≤d，則為YES，如果λ1(L(B))>y(n)d，則為NO，其中λ1(L(B))為格/(B)的最小距離。

2、?LWE問題

對于整數q>2，誤差分布z∈Zq，，z∈z，隨機選擇向量S∈Zn。定義兩個Zn xZ。上的分布：1）（a，ars+x），其中以為z：中隨機均勻選取，x服從形分布.)）Z×z上的均勻分
布。以上分布不可區(qū)分。

對適合的模數g及誤差分布甲口，利用傳統(tǒng)（多項式概率時間）規(guī)約，Peikert證明了LWEq.\ya至少跟求解最壞情形下近似GapSVP問題是一樣困難的。

定理1令a=a(n)∈(o，1)為一實數，且。則存在從解決最壞情形下GapSVPc，y問題到LWE問題的概率多項式
時間規(guī)約。

3、R-LWE問題

令f(x)=f+I∈Z[x]，其中安全參數n為2的整數冪，并使得f(x)在有理數域上不可約，r=Z[x]／<f(x)>為模f (x)的整多項式環(huán)，模數q=Imod 2n（由以的多項式界定）為一足夠大的素數，而且q= Rl=zrq／<f(x)>為模f (x)和g的整多項式環(huán)。Rq中的元素由次數低于n的多項式表示，其系數在{0，l，…，q-l）取得。

類似于LWE問題，R-LWE問題可描述如下：設s=s(x)∈R為一隨機均勻的的環(huán)元素（保密）。定義兩個Rq×Rq上的分布：

1）(n，b=axs+e)∈Rq×Rq，其中隨機均勻的選擇a∈Rq，P為取自于尺上某一分布中“較小”的隨機誤差項；

2）（a，c），a，c為Rq上隨機均勻選擇的環(huán)元素。則以上分布不可分。

證明了在理想格問題的困難性假設下R-LWE問題是困難的（見定理2）。

定理2假設對于多項式時間量子算法求解R中理想格上最壞情形近似最短向量(SVP)問題是困難的，則對多項式時間（甚至量子）攻擊者而言，從R-LWE分布中的任意多項式次取樣都是偽隨機的。

二、云存儲隱私保護策略

云存儲中用戶數據不再被用戶本地擁有，且被分布式地存儲在不可控的云端，各用戶數據具有無邊界性，因此需要有方法讓用戶確信：他們的數據只能被自身所訪問，即使云服務
提供商也不具備用戶數據的訪問權限，即數據的機密性保障。為此，本文采用同態(tài)加密方案配置云存儲隱私保障策略，如圖1所示：

可信的管理機構運行Setup(A)算法，生成用戶公鑰pk發(fā)送至各服務器，生成用戶私鑰sk發(fā)送至用戶。用戶向云端存儲數據m，首先將m拆分成mi，…，mi，執(zhí)行Encrypt(pk，id, mi)算法得到ci，并將密文ci分布式存儲在不同的服務器上。當云端接收到來自該用戶的數據請求，則云端執(zhí)行Circuit(pk，id，fc，((ai，ci))；算法將數據密文合成之后傳送聚合密文c至用戶。用戶在接收到標識為i的密文數據c后，執(zhí)行Decrypt算法能成功地獲取所需數據m。

由此，數據以密文的形式分布式存儲在云端各服務器上，云服務提供商或攻擊者從物理上擁有數據依然無法訪問數據。

三、基于R．LWE的同態(tài)加密方案

1、同態(tài)加密的定義
定義3基于公鑰密碼體制的安全同態(tài)加密方案由一組概率多項式時間(PPT)算法(Setup，Encrypt，Circuit, Decrypt)組成：

Setup(l“，1‘)：輸入安全參數兒及最大用戶數Z，輸出用戶私鑰sk和公鑰pk；

Encrypt(id，pk，mj)：給定數據標識id，用戶公鑰pk與明文mj，輸出密文cj；

：輸入數據標識id，密文CI，…，c，及相應權值ai，…，ai，輸出運算結果
Decrypt(id，sk，c)：己知數據標識id，用戶私鑰sk與密文CCi，，輸出明文

2/線性同態(tài)加密方案
基于R-LWE問題，本文提出的LHES如下：

Setup(l”，15)：輸入安全參數n=2k(k∈Z)，最大用戶數Z及正整數p<g=lmod(2n)，g為素數。隨機選取s∈r4= Zq [x]/<f(x)>(x)=f+1∈zM）作為私鑰，公鑰為(a，b=axs+pe)，其中a到r4是均勻隨機選取的，誤差項e從誤差分布／cr。中獨立選取；

Encrypt(id，pk，他mi)：給定數據標識id及用戶公鑰（a，b），為了加密-n比特的明文消息mi∈{0,1)”c Rp，均勻隨機選取ti∈R4輸出密文(c；D，Cj2’)=a×ti+pei(1)，a×ti+pei(2)+ mi），其中g’（j=1，2）從分布y中獨立選取，其中r4中多項式加法為普通多項式相加，乘法為普通多項式相乘模xn+1;

：輸入數據標識id，權值為ai，…，ai的密文(clu)，cl'2’)…，，(cf'D，c2'2’)，輸出密文；
Decrypt(id，sk，c)：收到數據標識id，用戶私鑰sk及密文(q，C2)后，計算(C2 -cl×s)mod p可得明文。

結論1上述LHES方案是正確的。

證明：對密文進行解密運算，設密文為：

因此，上述LHES是正確的。

結論2本文中加密方案是線性同態(tài)的。
證明：己知消息及權值，則消息；對應的密文為。另一方面，由上述加密方案中算法Circuit知對密文
的操作為，由解密算法Decrypt知對應的明文為，顯然密文對
應的明文也是。因此，本文中加密方案是線性同態(tài)的。

四、方案的性能分析

1、安全性分析

定義4己知安全參數為n，如果任意PPT敵手A的贏得下面游戲的優(yōu)勢是可以忽略的，則稱同態(tài)加密方案(Setup，Encrypt，Circuit，Decrypt)是CPA安全的。

游戲規(guī)則如下：

Setup：挑戰(zhàn)者運行Setup(l”)獲取密鑰(sk，pk)，并將公鑰pk發(fā)送至敵手A；

Queries:A隨機選擇(id，mi)并發(fā)送至挑戰(zhàn)者，其中id為消息他的標識，挑戰(zhàn)者計算:

把ci發(fā)送至A；

Challenge：詢問結束后，A隨機定義兩組不同的明文mo1…，，moi和m11…，，m1i，并發(fā)送至挑戰(zhàn)者，唯一的條件是m0J與m1j(j=1，…，2)未被詢問過。挑戰(zhàn)者隨機選取b∈{O，1}并計算cj=Encrypt(id, pk，mbi)（j=1…，，l），最后挑戰(zhàn)者將密文聚合:

再發(fā)送至A：

Output：A輸出b的猜測值b'。
如果b'=b，則稱敵手A贏得游戲，其概率記為Pr(b'=b），敵手的優(yōu)勢定義為:

結論3本文中LHES是CPA安全的。

證明：敵手在詢問結束后收到聚合密文c，并不知道其對應的密文CI，C2，…，CI即使知道密文，也不能進行解密得到相應的易，因為密文C1，C2，…，CI是由偽隨機R-LWE分布中的f組樣本組成，密文中隱藏著消息mbj（j=1，…，l）及公鑰。如果挑戰(zhàn)者沒有對消息moj或mij(j =1，…，l)進行回應，敵手仍能正確猜測出易，則表明敵手可以成功解決R-LWE問題，因此敵手不可能猜出易的值，因此本文中LHES是CPA安全的。

2、效率分析

由于R-LWE問題具有更加簡單的代數結構，而且解密時采用了取模的方法，因此本文提出的LHES是非常高效的，而且具有描述簡單、易于分析等優(yōu)勢。下面就該方案的加密及
解密部分同方案進行比較，效率改進情況如表1所示。

表1中數據表明本文加密方案在效率方面較方案有了很大的改進，尤其是公鑰長度、擴展因子及每加密1比特消息對應的基本運算次數都是普通基于LWE問題的加密方案所無法比擬的。另一方面，由于加密方案具有同態(tài)特征，故根據算法Circuit可將多個消息或密文壓縮為一個，在消息聚合之后使得加解密效率又提高了l倍，從而大大提高信息傳輸效率。

本文采用一普通個人電腦對表一中的兩個方案進行了模擬運算，電腦操作系統(tǒng)為微軟Windows XP 2002專業(yè)版，處理器Core (TM)2 Duo CPU E7400 2.8GHz，內存2.OGB，模擬
過程借助于Shoup's NTL library [14] version 5.5.2，代碼用Visual C++ 6.0編寫。

表2及表3分別給出了兩種加密方案運行時間的模擬結果，通過表中數據可發(fā)現(xiàn)本文中基于R-LWE問題加密方案的運行時間較方案在完全相同的條件下提高了幾個數量級，尤其是密鑰生成時間和加密時間。其中，模數q取滿足兩方案條件的最小整數，的m取為Sn。

圖1和圖2分別給出了兩種加密方案的運行時間隨安全參數n不斷增加的變化趨勢圖，從圖中可發(fā)現(xiàn)本文中LHES方案的運行時間隨安全參數的增加近似線性增長，在相同條件下方案運行時間隨安全參數增加而增長的速度明顯快于本文方案，這一點從表1的分析中也很容易看出。

admin

收藏 海報分享