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

一、基礎(chǔ)知識(shí)

1、格

格是n維空間中一類具有周期性結(jié)構(gòu)離散點(diǎn)的集合，具體描述如下：

定義1己知，n個(gè)線性無關(guā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問題

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

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

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

3、R-LWE問題

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

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

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

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

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

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

二、云存儲(chǔ)隱私保護(hù)策略

云存儲(chǔ)中用戶數(shù)據(jù)不再被用戶本地?fù)碛校冶环植际降卮鎯?chǔ)在不可控的云端，各用戶數(shù)據(jù)具有無邊界性，因此需要有方法讓用戶確信：他們的數(shù)據(jù)只能被自身所訪問，即使云服務(wù)
提供商也不具備用戶數(shù)據(jù)的訪問權(quán)限，即數(shù)據(jù)的機(jī)密性保障。為此，本文采用同態(tài)加密方案配置云存儲(chǔ)隱私保障策略，如圖1所示：

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

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

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

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

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

Encrypt(id，pk，mj)：給定數(shù)據(jù)標(biāo)識(shí)id，用戶公鑰pk與明文mj，輸出密文cj；

：輸入數(shù)據(jù)標(biāo)識(shí)id，密文CI，…，c，及相應(yīng)權(quán)值ai，…，ai，輸出運(yùn)算結(jié)果
Decrypt(id，sk，c)：己知數(shù)據(jù)標(biāo)識(shí)id，用戶私鑰sk與密文CCi，，輸出明文

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

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

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

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

結(jié)論1上述LHES方案是正確的。

證明：對(duì)密文進(jìn)行解密運(yùn)算，設(shè)密文為：

因此，上述LHES是正確的。

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

四、方案的性能分析

1、安全性分析

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

游戲規(guī)則如下：

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

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

把ci發(fā)送至A；

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

再發(fā)送至A：

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

結(jié)論3本文中LHES是CPA安全的。

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

2、效率分析

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

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

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

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

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

admin

收藏 海報(bào)分享