為確保云計(jì)算環(huán)境下用戶數(shù)據(jù)的安全性，利用同態(tài)加密算法對(duì)數(shù)據(jù)和加密函敦的隱私保護(hù)功能，設(shè)計(jì)一種基于整數(shù)多項(xiàng)式環(huán)的全同態(tài)加密算法。該算法包括同態(tài)算法和重加密算法，前者針對(duì)明文數(shù)據(jù)進(jìn)行加密，后者針對(duì)密文數(shù)據(jù)進(jìn)行二次加密。

一、基于整數(shù)環(huán)的全同態(tài)加密算法

1、全同態(tài)加密算法發(fā)展現(xiàn)狀及數(shù)據(jù)保護(hù)特點(diǎn)

全同態(tài)加密算法顛覆了傳統(tǒng)意義下的加密模式（圖1、圖2），它是一種可以對(duì)密文進(jìn)行操作但仍可以恢復(fù)明文的加密算法。算法設(shè)計(jì)的目的是：解決云環(huán)境下數(shù)據(jù)上傳服務(wù)器端，Sever不可信，用戶把私有數(shù)據(jù)加密上傳服務(wù)器端。全同態(tài)加密算法最終實(shí)現(xiàn)：

這樣用戶可以把私有信息經(jīng)過(guò)加密上傳服務(wù)器端，享受云服務(wù)，但是服務(wù)器端并不能獲得用戶數(shù)據(jù)。因此全同態(tài)加密算法可針對(duì)用戶的需求滿足對(duì)加密信息和加密函數(shù)的保護(hù)，使得在整個(gè)傳遞過(guò)程當(dāng)中始終保持加密狀態(tài)。

加密信息的處理如圖3所示，主要是對(duì)私有信息進(jìn)行保護(hù)。Alice有私有的函數(shù)fA和私有的信息XA，Bob把私有信息yB用私有公鑰pkB加密得到E(y)發(fā)送給Alice，Alice用自己的私有函數(shù)fA加密私有信息XA和E(yB)，由于同態(tài)性質(zhì)，函數(shù)fA被隱藏，而B(niǎo)ob獲得E(fA (XA，yB)）。Bob通過(guò)私有的私鑰加密D(E(fA (XA，yB)））=fA (XA，yB)。

加密函數(shù)的處理如圖4所示，主要是對(duì)私有的操作函數(shù)進(jìn)行保護(hù)。Alice有私有的函數(shù)以，并用私有公鑰pkA加密函數(shù)fA發(fā)送給Bob，Bob根據(jù)私有信息XB計(jì)算E(fA )(XB)，由于同態(tài)性質(zhì)，因此隱藏了Bob的信息XB，得到E(fa(b))，并發(fā)送給Alice，Alice用私鑰解密獲得fA(XB)。

2、整數(shù)環(huán)全同態(tài)加密算法分析

由于理想格全同態(tài)加密算法復(fù)雜度高，且密文數(shù)據(jù)擴(kuò)張不能得到解決，因此實(shí)用性不強(qiáng)。根據(jù)已有的理想格和整數(shù)全同態(tài)加密算法，設(shè)計(jì)基于Fp[x]的全同態(tài)加密算法。

同態(tài)算法具體如下：

KeyGen：對(duì)f(x)∈Fp[x]，選擇隨機(jī)的整數(shù)ai，ri∈Z，因此公鑰pk=，對(duì)每個(gè)b，滿足bi =aif(x)+ri，b最大。

Encryption：隨機(jī)選擇一個(gè)整數(shù)子集S∈{1，2，…，，z}，m∈{O，1}，隨機(jī)選擇r∈(_22p，22p)，密文ci= [m+2r+2∑i∈sbi]modbo。

Decryption：m=[cmodx]mod2

同態(tài)性性質(zhì)：

(l)加法：給定公鑰pk，密文Cl、C2，則：

(2)乘法：給定公鑰pk，密文cl、C2，則：

其中，Lxl表示x向下取整；rxn表示x向上取整。

加解密正確性分析：

(l)設(shè)需要加密的明文信息為m=l或m=o，選擇的函數(shù)為Z (x)，選擇n+l個(gè)q和n+l個(gè)l，S={1，2，…，n）。

(2)計(jì)算n+l個(gè)bi，使得bo次數(shù)最高。

(3)加密明文信息朋，得到c=[m+2r+ 2∑i∈Sb]modbo。

(4)不妨設(shè)f取得s集合中的前k個(gè)bi。

(5)密文c可以寫成：

(6)c是滿足多項(xiàng)式形式的數(shù)據(jù)，即c=g(x)x+n。

重加密算法Evaluate具體如下：

Keygen：按照上述算法選擇公鑰pk和私鑰sk，選擇k，其中，尼是滿足計(jì)算安全的大素?cái)?shù)；p是同態(tài)算法中的Fp [x]，定義xp=[2k/p-1/2]，漢明重量為θ的多項(xiàng)式g(x)=∑gixi，θ為2個(gè)a的最大距離，Ci∈z n[o，2k+l)，使得∑iESCi=m(mod2k+J)，Yi=ci/2k，因此可以得出∑i#sci=mod2k+1，新私鑰sk'=< g1，92，…，gn>。

Encryption：

輸入：密文c，新公鑰pk'；

輸出：新密文c’= [c. Yi]mod2 0

Decryption：

輸入：新密文c’；

輸出：

整個(gè)算法的設(shè)計(jì)思路是通過(guò)多項(xiàng)式的次數(shù)、模運(yùn)算、交互運(yùn)算以達(dá)到混亂明文的作用。在設(shè)計(jì)過(guò)程中主要是考慮把問(wèn)題的復(fù)雜性歸結(jié)到離散子集求和問(wèn)題，因此，選擇多項(xiàng)式是該算法的關(guān)鍵環(huán)節(jié)，多項(xiàng)式的選擇可以根據(jù)加密方對(duì)安全的要求程度決定，例如安全程度低可以選擇f(x)=x+1，如果安全程度高可以通過(guò)提升f (x)的次數(shù)來(lái)加強(qiáng)。同態(tài)算法的設(shè)計(jì)還是延續(xù)了理想格方法和整數(shù)方法的特點(diǎn)，使得循環(huán)操作環(huán)節(jié)簡(jiǎn)單，便于實(shí)際應(yīng)用。

性質(zhì)基于整數(shù)環(huán)Fp[x]的全同態(tài)加密算法計(jì)算量是O(Y15)。

證明：在Evaluate運(yùn)算中，需要確定xp、ci、Yi、Encryption和Decryption 5個(gè)部分，輸入的pk={bl，b2，…，bn）有n個(gè)，需要計(jì)算量為n；c=m+2r+∑iES bi ]mod bo，計(jì)算量為n；加密運(yùn)算和解密運(yùn)算需要計(jì)算量為n；每個(gè)重加密運(yùn)算都需要挖次操作，所以，計(jì)算量大約為：在實(shí)際應(yīng)用中，存在匿名同態(tài)協(xié)議和一種半匿名，即相鄰結(jié)點(diǎn)間不是匿名的，非相鄰結(jié)點(diǎn)間是匿名的。另外還存在一個(gè)樂(lè)觀可信第三方(optimistic trusted third party)，用于解決當(dāng)出現(xiàn)非法訪問(wèn)時(shí)去找到那個(gè)非法訪問(wèn)者，該TTP只有在出現(xiàn)問(wèn)題時(shí)才存在，所以不會(huì)影響效率。同態(tài)加密技術(shù)的快速發(fā)展，在云數(shù)據(jù)檢索、投票、垃圾郵件過(guò)濾、信號(hào)分析領(lǐng)域都有著廣泛的應(yīng)用。在安全協(xié)議上，同態(tài)算法都是解決一些關(guān)鍵問(wèn)題的有效方法和手段。

三、算法性能比較

全同態(tài)加密算法的主要優(yōu)勢(shì)是可以針對(duì)密文進(jìn)行操作，仍然可以回復(fù)明文，因此，滿足用戶對(duì)云服務(wù)的基本要求。本文算法與2種全同態(tài)加密算法進(jìn)行比較（表1）：

(1)理想格全同態(tài)加密算法：需要進(jìn)行矩陣運(yùn)算和向量模運(yùn)算（向量的加法和乘法），每加密一個(gè)比特都需要進(jìn)行矩陣和向量運(yùn)算（表示為連續(xù)性不好），公鑰擴(kuò)展O(n7)，每個(gè)Evaluate中計(jì)算門的計(jì)算量為O(n6)。

(2)整數(shù)全同態(tài)加密算法：需要進(jìn)行整數(shù)模運(yùn)算，連續(xù)性好，Evaluate算法中輸入超過(guò)本身算法要求，就不會(huì)實(shí)現(xiàn)全同態(tài)的性質(zhì)，存在攻擊危險(xiǎn)。每個(gè)Evaluate中計(jì)算門的計(jì)算量為O(y13)。

(3)整數(shù)環(huán)全同態(tài)加密算法：主要進(jìn)行多項(xiàng)式運(yùn)算，加密過(guò)程中不需要重新選擇多項(xiàng)式（連續(xù)性好），Evaluate中計(jì)算門的計(jì)算量為O(Y5)，根據(jù)實(shí)際安全的級(jí)別進(jìn)行篩選。

在算法的設(shè)計(jì)環(huán)節(jié)，雖然沒(méi)有保證嚴(yán)格雪崩效應(yīng)，但是把算法的安全性依靠在離散子集求和這個(gè)難解問(wèn)題，因此安全性沒(méi)有受到影響，而且有更好的實(shí)現(xiàn)價(jià)值。今后需要對(duì)降低基于整數(shù)多項(xiàng)式環(huán)的全同態(tài)加密算法的時(shí)空開(kāi)支以及明密文數(shù)據(jù)的擴(kuò)散問(wèn)題進(jìn)行研究。

admin

收藏 海報(bào)分享