徐碧晗 鄭 東 任 方

1.西安郵電大學(xué) 通信與信息工程學(xué)院，西安 710121 2.西安郵電大學(xué) 無線網(wǎng)絡(luò)安全技術(shù)國家工程實(shí)驗(yàn)室，西安 710121

◎網(wǎng)絡(luò)、通信與安全◎

基于編碼Hash同態(tài)性的數(shù)據(jù)持有性證明方案

徐碧晗1，2，鄭 東1，2，任 方1，2

1.西安郵電大學(xué) 通信與信息工程學(xué)院，西安 710121 2.西安郵電大學(xué) 無線網(wǎng)絡(luò)安全技術(shù)國家工程實(shí)驗(yàn)室，西安 710121

為了保證用戶在云存儲(chǔ)服務(wù)器中數(shù)據(jù)的完整性，在分析已有數(shù)據(jù)持有性證明方案的基礎(chǔ)上，提出了一種基于編碼Hash同態(tài)性的數(shù)據(jù)持有性證明方案。通過將偽隨機(jī)數(shù)與數(shù)據(jù)塊進(jìn)行“捆綁”作為標(biāo)簽來固定數(shù)據(jù)塊位置，同時(shí)引進(jìn)一種基于編碼的Hash，并利用同態(tài)性來完成數(shù)據(jù)持有性驗(yàn)證。該方案的安全性依賴于譯碼的NP完全問題，可抵抗量子攻擊，較傳統(tǒng)的基于Hash同態(tài)性的數(shù)據(jù)持有性證明方案更難被攻破，同時(shí)通過理論分析，算法時(shí)間開銷比以往方案更快，更有效。

數(shù)據(jù)完整性；數(shù)據(jù)持有性；編碼Hash；同態(tài)性；標(biāo)簽；量子攻擊

1 引言

近幾年，隨著IT設(shè)備計(jì)算量的增加，許多用戶由于存儲(chǔ)資源有限而選擇將數(shù)據(jù)存儲(chǔ)在遠(yuǎn)程云服務(wù)器中。遠(yuǎn)程服務(wù)器存儲(chǔ)數(shù)據(jù)有很多好處，例如可以提供諸多服務(wù)：（1）消除了客戶端存儲(chǔ)開銷和管理方面的壓力；（2）相比客戶端存儲(chǔ)，可以提供高效性和可擴(kuò)展性；（3）用戶可以在任何時(shí)候、任何地方訪問其數(shù)據(jù)。然而，無法確定遠(yuǎn)程云服務(wù)器在有敵手攻擊的情況下或者服務(wù)器自身蓄意攻擊的情況下（例如：服務(wù)器會(huì)刪除用戶不常用的數(shù)據(jù)來減少存儲(chǔ)空間，從而把這些存儲(chǔ)空間賣給其他用戶），云服務(wù)器仍能正確存儲(chǔ)用戶數(shù)據(jù)。所以，為了使用戶放心使用云存儲(chǔ)服務(wù)，通過某種途徑來驗(yàn)證數(shù)據(jù)是否完好地保存在服務(wù)器中是非常有必要的[1-2]，而且這種保證是必須的。然而，通常存儲(chǔ)在云服務(wù)器中的外源數(shù)據(jù)文件是非常大的，所以用戶為了檢查所存儲(chǔ)數(shù)據(jù)的完整性[3]而下載整個(gè)文件是不現(xiàn)實(shí)的，因?yàn)檫@樣做所付出的開銷和帶寬與原來的目的背道而馳。

為了解決這一問題，一些學(xué)者們引入了遠(yuǎn)程數(shù)據(jù)完整性檢測 RIC（Remote Integrity Checking）的概念[4-5]，即檢測一些不可信的存儲(chǔ)服務(wù)端是否能夠避免數(shù)據(jù)的刪除或篡改而正確的保存數(shù)據(jù)。RIC可以分為可證明數(shù)據(jù)持有 PDP（Provable Data Possession）方案[6-7]和可恢復(fù)證明POR（Proof Of Retrievability）方案[8]兩種。遠(yuǎn)程數(shù)據(jù)完整性檢驗(yàn)[9]最初由文獻(xiàn)[4]提出，即應(yīng)用基于RSA的Hash函數(shù)來計(jì)算整個(gè)數(shù)據(jù)的Hash值。如果用戶將數(shù)據(jù)保存到一個(gè)不可信的云服務(wù)器中，PDP方案能夠驗(yàn)證保存在服務(wù)器中數(shù)據(jù)的完整性，但是當(dāng)數(shù)據(jù)被刪除或者篡改時(shí)，PDP方案并不能夠?qū)?shù)據(jù)恢復(fù)，而POR方案不僅能確保外源數(shù)據(jù)的私有性和完整性，還能夠利用糾錯(cuò)碼來恢復(fù)被改變過的數(shù)據(jù)。POR方案的概念在文獻(xiàn)[8]中由Juels和Kaliski首次提出，在之后的研究中，學(xué)者們對POR方案進(jìn)行了諸多改善，但其進(jìn)展緩慢，相比PDP方案，研究力度較弱。自Ateniese等在文獻(xiàn)[6]中對PDP方案進(jìn)行了正式的定義以來，其研究團(tuán)隊(duì)首次提出多副本PDP方案即MR-PDP（Multiple-Replica）方案[10-11]。肖達(dá)等人[12]提出的有關(guān)數(shù)據(jù)完整性驗(yàn)證的文章，指出用戶要求驗(yàn)證的數(shù)據(jù)塊的位置以及個(gè)數(shù)，并發(fā)往服務(wù)器，服務(wù)器計(jì)算這些指定數(shù)據(jù)的Hash值發(fā)送給用戶，用戶將Hash值與校驗(yàn)塊比較是否相等。Ateniese等人[13]提出了可擴(kuò)展數(shù)據(jù)持有性證明SPDP（Scalable Provable Data Possession）方案，相比PDP方案增加了動(dòng)態(tài)數(shù)據(jù)驗(yàn)證。之后由Erway等人[14]提出的動(dòng)態(tài)數(shù)據(jù)持有性證明DPDP（Dynamic Provable Data Possession）方案允許動(dòng)態(tài)數(shù)據(jù)的持有性驗(yàn)證。陳等人[15]利用同態(tài)Hash[16]給出了一種新的數(shù)據(jù)持有性證明方法HH-PDP（Homomorphic Hashing based Provable Data Possession）。隨后李等人[17-18]提出了基于同態(tài)Hash的MR-PDP方案和一種動(dòng)態(tài)數(shù)據(jù)的MR-PDP方案。現(xiàn)有的數(shù)據(jù)持有性證明方案都具備一定的安全性能，盡管如此，基于Shor算法[19]和Grover算法[20]等量子攻擊仍對目前的數(shù)據(jù)持有性證明方案構(gòu)成一定威脅，因此，能夠有效抵抗量子攻擊的數(shù)據(jù)持有性證明方案是很需要的。

黃等人[21]針對文獻(xiàn)[15]中HH-PDP方案存在的問題進(jìn)行了改善，然而該文章仍存在諸多不足。本文在文獻(xiàn)[21]的基礎(chǔ)上，結(jié)合文獻(xiàn)[22-23]中的編碼Hash和文獻(xiàn)[15]中的Hash同態(tài)性引入了一種基于編碼Hash同態(tài)性的數(shù)據(jù)持有性證明方法CHH-PDP（Coding Homomorphic Hashing based Provable Data Possession），該方案的安全性依賴于校驗(yàn)子譯碼SD（Syndrome Decoding）問題，該問題已被證明是NP完全問題，可以有效地抵抗目前已知的量子攻擊，具有更高的安全性，同時(shí)運(yùn)行效率良好，是一種更安全有效的數(shù)據(jù)持有性證明方案。

2 基礎(chǔ)知識(shí)

2.1 數(shù)據(jù)持有性證明

數(shù)據(jù)持有性證明就是驗(yàn)證不可信的云存儲(chǔ)服務(wù)器是否能夠正確地保存數(shù)據(jù)，避免云存儲(chǔ)服務(wù)器提供者非法刪除或篡改數(shù)據(jù)。

用戶將數(shù)據(jù)存儲(chǔ)在云服務(wù)器中，如果沒有相應(yīng)的檢測機(jī)制，當(dāng)所存儲(chǔ)的數(shù)據(jù)丟失或被偽造后，不能確保服務(wù)器能否及時(shí)將情況反映給用戶，所以，用戶需要隨時(shí)知道存儲(chǔ)在云服務(wù)器的數(shù)據(jù)是否完整并且隨時(shí)可用。針對這一問題，學(xué)者們提出數(shù)據(jù)持有性證明，如果這一問題得到有效解決，云服務(wù)器將會(huì)廣泛地被人所接受。用戶將需要存儲(chǔ)的數(shù)據(jù)進(jìn)行一定預(yù)處理之后發(fā)送給云服務(wù)器進(jìn)行存儲(chǔ)，在任何時(shí)候用戶都可以向云服務(wù)器提出挑戰(zhàn)，云服務(wù)器向用戶發(fā)送相關(guān)證據(jù)進(jìn)行應(yīng)答，用戶利用證據(jù)來驗(yàn)證數(shù)據(jù)的完整性。數(shù)據(jù)持有性證明模型圖如圖1所示。

圖1 數(shù)據(jù)持有性證明模型圖

2.2 糾錯(cuò)碼

糾錯(cuò)碼的基本思想是在消息通過一個(gè)有噪信道傳輸前以多余符號(hào)的形式在消息中增加冗余度，這種冗余度是在一定的規(guī)則下添加的。編碼后的消息在傳輸時(shí)可能還會(huì)遭受到信道中噪聲的損害。在接收端，如果錯(cuò)誤數(shù)在該碼的設(shè)計(jì)限度內(nèi)，則原始消息可以從受損的消息中恢復(fù)。對于糾錯(cuò)碼的一些基本信息，下面給出如下幾點(diǎn)定義：

定義1有限域Fq上的一個(gè)( )n,k線性分組碼C是n維線性空間Fnq的一個(gè)k維子空間，F(xiàn)nq中的向量稱為字，而C中的向量稱為碼字，n稱為碼長，k稱為碼的維數(shù)。

定義2一個(gè)( )n,k線性分組碼C的校驗(yàn)矩陣是一個(gè)( )

n-k×n的矩陣H。長為n的向量c是C的一個(gè)碼字的充分必要條件是HcT=0。對于任意的字c，將HcT稱為c的校驗(yàn)子。

定義3線性分組碼的碼字u=(u1,u2,…,un)的Hamming重量ω(u)定義為u與全0碼字0的距離，即ω(u)=d(u ,0)，即非0位的個(gè)數(shù)。

2.3 Hash函數(shù)

典型的Hash函數(shù)是一個(gè)公開的函數(shù)，其作用是將任意長的消息映射成一個(gè)固定長度的摘要。具體構(gòu)造過程是利用一個(gè)壓縮函數(shù)F對給定的任意長消息進(jìn)行多輪循環(huán)運(yùn)算，最終得到的值為該任意長消息的Hash值。

如下給出循環(huán)迭代過程。假設(shè)該壓縮函數(shù)的F輸入為e位，輸出為r位，且r＜e。

（1）首輪需要選擇一個(gè)初始向量v0，長度為r，還需從源數(shù)據(jù)中選(e -r)位，與v0相連，形成長度為e的向量作為函數(shù)F的輸入，輸出r位。

（2）從第二輪開始，將前一輪輸出的r位作為這一輪壓縮函數(shù)F的輸入，其余(e -r)位從源數(shù)據(jù)中選，計(jì)算出新的輸出。

（3）重復(fù)循環(huán)第（2）步，直到源數(shù)據(jù)中所有數(shù)據(jù)都被取完為止。如果在最后一輪中，數(shù)據(jù)剩余位數(shù)少于(e -r)位，則任選若干比特將輸入位填充到(e -r )位，函數(shù)最終的輸出作為消息的Hash值。

具體迭代過程如圖2所示。

圖2 Hash函數(shù)迭代過程

2.4 同態(tài)性

定義4群同態(tài)指的是群中一種保持結(jié)構(gòu)不變的映射，兩個(gè)群之間的映射 f：(A ;? )→(B ;⊙ )，如果滿足B，則映射 f為群同態(tài)映射。

若定義4中A與B中的運(yùn)算是加法，該式描述的是群之間的加法同態(tài)性；若A與B中的運(yùn)算是乘法，則該式描述的是群之間的乘法同態(tài)性。兩個(gè)群之間的同態(tài)映射原理如圖3所示，A與B代表兩個(gè)集合，g1,g2∈A，‘?’代表 A中的運(yùn)算，在集合 A中存在 g1?g2=g′；而g1與g2的函數(shù) f(g1),f(g2)∈B，‘⊙’代表B中的運(yùn)算，即在集合B中存在 f(g1)⊙f(g2)=f(g ′)，而 f(g′)是g′的函數(shù)，滿足 f(g1?g2)=f(g1)⊙f(g2)，這便是集合A與B之間的同態(tài)性映射原理。

圖3 同態(tài)性原理圖

定義5對于具有兩種運(yùn)算的集合之間的映射 f：(A ;?,·)→ (B ;⊙,? )，若滿足以下兩個(gè)等式：

其中g(shù)1,g2∈A，f(g1),f(g2)∈B。則這兩個(gè)集合在這兩種運(yùn)算下具有全同態(tài)性。

定義6群上的Hash函數(shù)h:{0 ,1}?→{0 ,1}r，對于?x1,x2∈{0 ,1}?，都 有 h(x1?x2)=h(x1)⊙h(x2)，其 中“?”是定義在{0 ,1}?上的群運(yùn)算，“⊙”是定義在{0 ,1}r上的群運(yùn)算，則該Hash函數(shù)具有群同態(tài)性，稱為同態(tài)Hash。

2.5 校驗(yàn)子

定義7校驗(yàn)子譯碼SD（Syndrome Decoding）問題：輸入有限域 Fq上的一個(gè)(n-k)×n的矩陣 H，向量s∈Fn-kq，整數(shù)k＞0，是否存在一個(gè)字 x∈Fnq，其重量w(x)≤k，使得 HxT=s。

3 基于編碼的Hash函數(shù)

3.1 編碼Hash的壓縮函數(shù)

編碼Hash函數(shù)的核心部分為壓縮函數(shù)的構(gòu)造，傳統(tǒng)的編碼Hash是基于傳統(tǒng)壓縮函數(shù)構(gòu)造而成的。而利用校驗(yàn)子譯碼問題構(gòu)造出的編碼Hash具有特殊的內(nèi)部結(jié)構(gòu)，DanielAugot等在文獻(xiàn)[22]中提出了編碼Hash，且對該種編碼Hash的內(nèi)部結(jié)構(gòu)進(jìn)行了詳細(xì)的講解，本節(jié)將進(jìn)行介紹，先引入正則字的定義。

定義8一個(gè)長度為n，重量為ω的字，把它平分為ω個(gè)等間距區(qū)間，如果這個(gè)字在每一個(gè)區(qū)間都僅有一個(gè)非0位，那么稱這個(gè)字為( )n,ω正則字。

選擇一個(gè)( )n,k糾錯(cuò)碼，同時(shí)選擇正整數(shù)ω，使得ω可以整除n，將所有長度為n的碼字等分為ω個(gè)塊，每塊有該碼的校驗(yàn)矩陣H是一個(gè)()n-k×n矩陣，同樣將H等分為ω個(gè)子矩陣，H=(H1,H2,…,Hω)，子矩陣表示為Hi。壓縮函數(shù)F定義為：，其中，則F的輸入數(shù)據(jù)x∈Fe2。如下給出壓縮函數(shù)的運(yùn)算過程：

（1）將ebit輸入數(shù)據(jù)x等分為ω個(gè)子塊，即x1,x2,…,

xω，每個(gè)子塊 xi包含

（2）將每個(gè) xi轉(zhuǎn)換為0到之間的整數(shù)xi。

（3）選擇相應(yīng)的子矩陣 Hi的第 xi+1列，表示為

（4）將選好的ω個(gè)列累加，獲得一個(gè)長為r的比特串，就是F的輸出，即計(jì)算

文獻(xiàn)[23]中指出，以上得出的壓縮函數(shù)F的輸出相當(dāng)于計(jì)算一個(gè)長為n，重為ω的正則字的校驗(yàn)子。利用壓縮函數(shù)F可以構(gòu)造出一個(gè)Hash函數(shù)，此時(shí)定義一個(gè)基于編碼的Hash函數(shù)FH：{0 ,1}*→F2r，即對于任意長度的數(shù)據(jù)m，F(xiàn)H(m )都是一個(gè)長為n，重為ω的正則字c的校驗(yàn)子。即：

3.2 編碼Hash的同態(tài)性

上述基于編碼的Hash函數(shù)FH是具有同態(tài)性的，為此，假設(shè)所有(n ,ω )正則字構(gòu)成的集合為G(n,ω)，在這個(gè)集合中定義一種循環(huán)右移函數(shù)RS(c)以及循環(huán)右移運(yùn)算，用“⊕”來表示。其中RS(c)表示字符串c循環(huán)右移s位，如 R4(0 1000000)=(0 0000100)。以下將正則字中非0位默認(rèn)為“1”。

（1）對于重量為w(a)=w(b)=1的正則字a,b，長為n，定義a⊕b=RSa(b)=RSb(a )。Sa 表示 a 中“1”左端“0”個(gè)數(shù)，同理 Sb表示b中“1”左端“0”的個(gè)數(shù)，c=a⊕b，則正則字 c中“1”左端“0”的個(gè)數(shù)為 (S a+Sb) modn。

（2）對于重量為w(a)=w(b)=ω的(n ,ω )正則字a,b。分別將a,b平分為 ω 塊，a=(a1,a2,…,aω)，b=( )b1,b2,…,bω，每塊 ai和 bi中含有位，且僅有一個(gè)“1”。按（1）中的方式將ai與對應(yīng)位置的bi進(jìn)行“⊕”運(yùn)算，則 ai⊕bi=RSai(bi)=RSbi(ai)，其結(jié)果仍是只有一個(gè)“1”的位字符串，且“1”左端有()Sai+Sbimod個(gè)“0”。因此有：

定理1基于編碼的Hash函數(shù)FH是具有同態(tài)性的，假設(shè)所有(n ,ω )正則字構(gòu)成的集合為G(n,ω)，如果該集合G(n,ω)在循環(huán)右移“⊕”運(yùn)算下構(gòu)成一個(gè)群，那么該稱為一個(gè)正則字群。

證明 分別從正則字群所滿足的四個(gè)條件入手。

①封閉性。假設(shè)正則字a,b∈G(n,ω)，分別將 a,b平分為ω塊，每一個(gè)ai與bi分別僅有一個(gè)“1”，ai⊕bi的結(jié)果同樣僅有一個(gè)“1”，故正則字a,b在“⊕”運(yùn)算后仍屬于正則字，滿足封閉性。

②結(jié)合律。先將每一個(gè)(n ,ω )正則字a,b,d分為ω塊，每一塊分別進(jìn)行驗(yàn)證。驗(yàn)證過程如下：

可得(ai⊕bi) ⊕di=ai⊕(bi⊕di) ，所以 (a⊕b)⊕d=a⊕(b⊕d)，滿足結(jié)合律。

③存在單位元。假設(shè)碼字a,e為G(n,ω)中的正則字，每一塊為ai,ei。僅當(dāng)Sei=0時(shí)，ai⊕ei=RSei(ai)=ai，此時(shí)的 ei中“1”左邊沒有“0”，即第一位是“1”，因此，碼字e可以使得a⊕e=e⊕a=a。顯然碼字e是G(n,ω)中的單位元，故存在單位元。

④存在逆元。假設(shè)a是G(n,ω)中的正則字，e是G(n,ω)中的單位元。若想要等式ai⊕bi=ei成立，則必須滿足，總能找到()n,ω 正則字b滿足因此，正則字b可以使得a⊕b=e，則稱b為a的逆元，即b=a-1，故存在逆元。

以上證明說明該(n,ω)正則字集合在“⊕”運(yùn)算下確實(shí)可構(gòu)成一個(gè)正則字群。由于上文中提到該編碼Hash滿足FH(m)=HcT，c為正則字，對于不同的輸入數(shù)據(jù) m1與 m2，F(xiàn)H(m1)=Hc1T，F(xiàn)H(m2)=Hc2T，則下式成立：

云服務(wù)器中存儲(chǔ)數(shù)據(jù)時(shí)需要將數(shù)據(jù)M分為若干塊進(jìn)行存儲(chǔ)，即M=(m1,m2,…,mB)，再將每一個(gè)二進(jìn)制字符串mi作為Hash函數(shù)的輸入來產(chǎn)生標(biāo)簽，最后需要利用同態(tài)性進(jìn)行驗(yàn)證。定義mi之間的一種轉(zhuǎn)換加法運(yùn)算，用“°”來表示，即將mi轉(zhuǎn)換成十進(jìn)制形式相加后取模，最后將其結(jié)果轉(zhuǎn)換為二進(jìn)制形式。如長為k的m1與 m2，轉(zhuǎn)換加法表示為 m′=m1°m2=Bin{(Dec(m1)+Dec(m2))mod2k}，其中 Dec(mi)代表將mi由二進(jìn)制形式轉(zhuǎn)換為十進(jìn)制形式，Bin(mi)代表將mi由十進(jìn)制形式轉(zhuǎn)換為二進(jìn)制形式。類似的很容易證明，mi在“°”算法下構(gòu)成一個(gè)群。

定理2基于編碼的Hash函數(shù)FH：({ 0 ,1}?;°)→({ 0 ,1}r;⊕ )是群之間的一個(gè)同態(tài)Hash。

證明 由于上文推理出FH(m)=HcT，那么對于不同的數(shù)據(jù)塊m1,m2有FH(m1)=Hc1T，F(xiàn)H(m2)=Hc2T。

令 m′=m°m，則 F(m °m)=F(m ′ )=Hc′T，由

12H12H編碼 Hash 的結(jié)構(gòu)可得 出 c′=c1⊕c2，又 FH(m1)⊕F(m )=HcT⊕HcT=H(c ⊕c)T=Hc′T，則 F(m°

H21212H1m2)=FH(m1)⊕FH(m2)。則該Hash函數(shù)具有群同態(tài)性，滿足定義6中的公式，因此基于編碼的Hash函數(shù)FH是同態(tài)Hash。

4 基于編碼Hash的數(shù)據(jù)持有性證明

4.1 參數(shù)描述

方案中用到的參數(shù)說明如表1所示。

表1 參數(shù)描述

4.2 方案描述

基于編碼Hash同態(tài)性的數(shù)據(jù)完整性證明分為五個(gè)階段，即初始化（Setup）階段，生成標(biāo)簽（TagBlock）階段，挑戰(zhàn)（Challenge）階段，生成證據(jù)（ProofGen）階段和驗(yàn)證證據(jù)（ProofVerify）階段。CL與SR之間的數(shù)據(jù)傳輸圖如圖4所示。在進(jìn)行Hash運(yùn)算之前，先將數(shù)據(jù)M分為B塊存儲(chǔ)，之后若干階段都以這些數(shù)據(jù)塊為最小單位進(jìn)行。

圖4 數(shù)據(jù)傳輸流圖

（1）Setup階段：( )n,k,ω→FH

在該Setup階段，生成一系列初始化參數(shù)，生成該糾錯(cuò)碼的校驗(yàn)矩陣，生成編碼Hash的運(yùn)算結(jié)構(gòu)FH（包括H），方便后面階段的繼續(xù)進(jìn)行。

輸入 n表示字的長度，k表示消息位的長度，ω為字的重量；

輸出 編碼Hash函數(shù)FH。

（2）TagBlock階段

M=(m1,m2,…,mB)→ Tag=(T1,T2,…,TB)

客戶端（CL）利用偽隨機(jī)數(shù)生成器隨機(jī)生成一系列(n ,ω ) 正則字 ci，計(jì)算 HcTi，從而得到偽隨機(jī)數(shù)Ri=HcTi，將這些偽隨機(jī)數(shù)與數(shù)據(jù)塊的Hash值一對一的進(jìn)行循環(huán)右移“⊕”運(yùn)算，運(yùn)算后的結(jié)果Ti作為標(biāo)簽。CL將消息M ，標(biāo)簽Tag，塊數(shù)B，發(fā)送給云服務(wù)器（SR），自己保留Hash函數(shù)運(yùn)算結(jié)構(gòu)FH以及生成偽隨機(jī)數(shù)時(shí)使用的種子seed。

輸入 消息M=(m1,m2,…,mB)；

步驟 對于i∈(1,2,…,B)，有 Γi=FH(mi)；ci=rand(seed)；Ri=HcTi，則Ti=Γi⊕Ri；

輸出Tag=(T1,T2,…,TB)。

（3）Challenge階段

CL使用偽隨機(jī)數(shù)生成器生成v個(gè)隨機(jī)的挑戰(zhàn)塊，將其位置標(biāo)號(hào)i(s)發(fā)送給SR，s∈{1 ,2,…,v}。

步驟 對于s∈(1,2,…,v)，計(jì)算：

（4）ProofGen階段：(M,Tag,i(s),v)→(mc,Tc)

SR將v個(gè)隨機(jī)挑戰(zhàn)的數(shù)據(jù)塊進(jìn)行轉(zhuǎn)換加法“°”累加運(yùn)算，結(jié)果記為mc；將v個(gè)隨機(jī)挑戰(zhàn)塊的標(biāo)簽進(jìn)行循環(huán)右移“⊕”累加運(yùn)算，結(jié)果記為Tc；將mc和Tc的值返回給CL。

輸入 消息M=(m1,m2,…,mB)，標(biāo)簽Tag等；

步驟 對于輸入的消息M=(m1,m2,…,mB)，標(biāo)簽Tag ，計(jì)算

（5）ProofVerify階段

CL利用自己保留的偽隨機(jī)數(shù)生成器種子seed，重新生成偽隨機(jī)數(shù)Ri(1)→Ri(v)，利用Hash函數(shù)的同態(tài)性，計(jì)算出 T′c值：

驗(yàn)證T′c=?Tc是否相同。若相同，則SR的數(shù)據(jù)持有正確。同時(shí)還可驗(yàn)證這個(gè)Tc是否對應(yīng)正確的mc。

5 算法分析

下面主要對改進(jìn)后的數(shù)據(jù)持有性證明算法，即基于編碼Hash同態(tài)性的數(shù)據(jù)持有性證明CHH-PDP方案進(jìn)行正確性、效率性和安全性分析，并與之前研究者們的HH-PDP方案進(jìn)行對比。

5.1 正確性分析

下面來證明該方案的正確性，假設(shè)用戶需委托云服務(wù)器保存的數(shù)據(jù)為M，將M 分為B塊，M=(m1,m2,…,mB)，分別將每一個(gè)mi作為Hash函數(shù)FH的輸入。輸出相當(dāng)于一個(gè)(n ,ω )正則字c的校驗(yàn)子，對于任意長度的輸入數(shù)據(jù)mi，有FH(mi)=HcTi，F(xiàn)H(mi)有(n -k)bit。用戶利用偽隨機(jī)數(shù)生成器生成一系列(n ,ω )正則字ci，計(jì)算HcTi，得到偽隨機(jī)數(shù) Ri=HcTi，計(jì)算出標(biāo)簽Ti=FH(mi)⊕Ri，Tag=(T1,T2,…,TB)，然后用戶將M，Tag，B發(fā)送給云服務(wù)器，自己保留FH算法（包括H）和偽隨機(jī)數(shù)生成器種子seed。當(dāng)用戶想要驗(yàn)證任意v個(gè)數(shù)據(jù)塊是否完整保存時(shí)，用戶隨機(jī)生成任意v個(gè)下標(biāo)位置i(s)，將i(s)與檢驗(yàn)塊數(shù)v發(fā)送給云服務(wù)器。云服務(wù)器收到用戶的挑戰(zhàn)，計(jì)算出將證據(jù)(mc,Tc)返回給用戶。用戶利用seed重新生成要檢驗(yàn)的v個(gè)偽隨機(jī)數(shù)Ri(1)～Ri(v)，同時(shí)利用云服務(wù)器發(fā)過來的mc，計(jì)算FH( )mc。由于編碼Hash具有的同態(tài)性，所以，用戶自己計(jì)算：

足以證明該算法的正確性。

5.2 效率分析

用戶與服務(wù)器之間的“通話”存在于以下幾個(gè)階段：TagBlock階段，用戶將數(shù)據(jù) M ，標(biāo)簽Tag，塊數(shù)B，發(fā)送給服務(wù)器；當(dāng)用戶想要向服務(wù)器發(fā)出挑戰(zhàn)時(shí)，即Challenge階段，用戶將想要檢驗(yàn)的v個(gè)數(shù)據(jù)塊下標(biāo)發(fā)送給服務(wù)器；在ProofGen階段，服務(wù)器將計(jì)算出的證據(jù)mc和Tc發(fā)送給用戶進(jìn)行回應(yīng)。

方案中用戶與服務(wù)器之間的每次“通話”，只需傳輸少量bit即可達(dá)到驗(yàn)證目的。經(jīng)計(jì)算，假設(shè)用戶選擇使用( )

n,k糾錯(cuò)碼的校驗(yàn)矩陣H來構(gòu)造編碼Hash，則每個(gè)標(biāo)簽塊Ti僅占用( )n-kbit存儲(chǔ)空間。在TagBlock階段，用戶發(fā)送給服務(wù)器的Tag僅占( )n-k×n個(gè)bit位；在ProofGen階段，服務(wù)器返回給用戶的Tc僅占( )n-k個(gè)bit位。

在文獻(xiàn)[15]與文獻(xiàn)[21]所用的由Krohn等[16]提出的Hash算法中，其Hash值長度取決于所選大素?cái)?shù) p的長度λp，例如，λp取典型值1 024 bit，則輸入任意長數(shù)據(jù)塊，Hash輸出為1 024 bit。但是存在一個(gè)問題，算法安全性與λp的值成正比，與時(shí)間開銷成反比，所以λp不宜太小。而本文算法中任意大小的輸入數(shù)據(jù)塊，編碼Hash的輸出都為(n -k)bit。所以該方案中編碼Hash的輸出大小取決于所選糾錯(cuò)碼的校驗(yàn)子H的大小。取McElience經(jīng)典參數(shù)，即 n=1 024，k=524，則編碼Hash的輸出大小為500 bit。通過對比，該方案中用戶與服務(wù)器之間的“通話”所需的傳輸帶寬更少，時(shí)間開銷也更少，整個(gè)驗(yàn)證過程的效率有一定的提高。效率對比如表2所示。

表2 方案使用不同Hash的效率對比

為了更好地驗(yàn)證本方案的效率問題，在配置為Intel Core i7-5600U CPU 2.60 GHz，12 GB RAM的機(jī)器上基于由悉尼大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)系計(jì)算代數(shù)學(xué)小組開發(fā)的功能強(qiáng)大的代數(shù)計(jì)算程序包Magma，版本Magma2_12-Windows，實(shí)現(xiàn)編碼Hash函數(shù)算法。取n=8，k=5，ω=4，編碼Hash的輸入為一個(gè)任意長字符串（例如：100101011），輸出為長度為3的字符串（001），顯而易見該輸出為一個(gè)正則字的校驗(yàn)子。并且構(gòu)造出循環(huán)右移“⊕”算法，將兩個(gè)正則字（001）與（010）進(jìn)行“⊕”運(yùn)算，輸出結(jié)果為（100）。同時(shí)構(gòu)造出轉(zhuǎn)換加法“°”，將長度為3的兩個(gè)二進(jìn)制字符串（110）與（100）進(jìn)行“ °”運(yùn)算，輸出結(jié)果為（010）。通過實(shí)際測試，對一個(gè)20 kB的字符串計(jì)算其編碼Hash的時(shí)間開銷為0.17 s。

6 安全性分析

（1）算法安全性分析

服務(wù)器只知道標(biāo)簽Tag與塊數(shù)B，不知道編碼Hash函數(shù)FH的算法。服務(wù)器若想要欺騙用戶，需知道Hash函數(shù)FH的算法，從而計(jì)算出每個(gè)數(shù)據(jù)塊的Hash值Γi，利用Ti=Γi⊕Ri來得出偽隨機(jī)數(shù)Ri，通過改變Ri來破壞數(shù)據(jù)持有性。由于在TagBlock階段，用戶并沒有告知云服務(wù)器編碼Hash函數(shù)FH的算法，所以服務(wù)器在知道標(biāo)簽Tag與塊數(shù)B的條件下也無法求得偽隨機(jī)數(shù)Ri，從而無法偽造標(biāo)簽來欺騙用戶，增強(qiáng)了方案的安全性。

（2）編碼Hash安全性分析

安全性方面，該方案最大的優(yōu)點(diǎn)在于其核心部分使用的編碼Hash的安全性依賴于這樣一個(gè)NP完全問題，輸入有限域 Fq上的一個(gè)(n-k)×n矩陣 H，向量s∈Fn-kq，整數(shù)k＞0，是否存在一個(gè)字 x∈Fnq，其重量w(x)≤k，使得 HxT=s。

文中得出結(jié)論，Hash函數(shù)FH的輸出相當(dāng)于計(jì)算一個(gè)( )

n,ω正則字的校驗(yàn)子。該校驗(yàn)子譯碼問題已經(jīng)被證實(shí)屬于NP完全問題，可有效抵抗目前的量子攻擊，所以相比同類方案，該方案具有更高的安全。

7 結(jié)束語

本文提出的基于編碼Hash的數(shù)據(jù)持有性證明CHH-PDP方案，是將糾錯(cuò)碼的校驗(yàn)矩陣構(gòu)造成Hash函數(shù)的形式，實(shí)現(xiàn)Hash的功能，并且利用編碼Hash的同態(tài)性來驗(yàn)證云存儲(chǔ)中數(shù)據(jù)的持有性。將編碼Hash與前人方案相結(jié)合，使得數(shù)據(jù)持有性證明方案的運(yùn)行效率與安全性得到提高。在將來的研究中，方案的冗余存儲(chǔ)空間和時(shí)間開銷與帶寬消耗仍需進(jìn)一步改進(jìn)，從而實(shí)現(xiàn)更高效率的數(shù)據(jù)持有性證明。

[1]Wang H.Proxy provable data possession in public clouds[J].IEEE Transactions on Services Computing，2013，6（4）：551-559.

[2]Wang H.Identity-based distributed provable data possession in multicloud storage[J].IEEE Transactions on Services Computing，2015，8（2）：328-340.

[3]Liu C，Yang C，Zhang X，et al.External integrity verification for outsourced big data in cloud and IoT：A big picture[J].Future Generation Computer Systems，2015，49：58-67.

[4]Deswarte Y，Quisquater J J，Sa?dane A.Remote integrity checking[M]//Integrity and Internal Control in Information Systems VI.Boston，MA：Springer，2003，140：1-11.

[5]Yu Y，Au M H，Mu Y，et al.Enhanced privacy of a remote data integrity-checking protocol for secure cloud storage[J].International Journal of Information Security，2015，14（4）：307-318.

[6]Ateniese G，Burns R，Curtmola R，et al.Provable data possession at untrusted stores[C]//Proceedings of the 14th ACM Conference on Computer and Communications Security，2007：598-609.

[7]Ren Y J，Shen J，Wang J，et al.Mutual verifiable provable data auditing in public cloud storage[J].網(wǎng)際網(wǎng)路技術(shù)學(xué)刊，2015，16（2）：317-323.

[8]Juels A，Kaliski Jr B S.PORs：Proofs of retrievability for large files[C]//Proceedings of the 14th ACM Conference on Computer and Communications Security，2007：584-597.

[9]Nguyen T C，Shen W，Luo Z，et al.Novel data integrity verification schemes in cloud storage[M]//Computer and information science.[S.l.]：Springer International Publishing，2015：115-125.

[10]Curtmola R，Khan O，Burns R，et al.MR-PDP：Multiplereplica provable data possession[C]//The 28th International Conference on Distributed Computing Systems，2008，ICDCS’08，2008：411-420.

[11]Balamurugan B，Mandadi A R，Mohan S，et al.Multiple replica based remote data possession checking scheme based on matrix representation of data[C]//International Confernce on Innovation Information in Computing Technologies，2015：1-5.

[12]肖達(dá)，舒繼武，陳康，等.一個(gè)網(wǎng)絡(luò)歸檔存儲(chǔ)中實(shí)用的數(shù)據(jù)持有性檢查方案[J].計(jì)算機(jī)研究與發(fā)展，2009，46（10）：1660-1668.

[13]Ateniese G，Di Pietro R，Mancini L V，et al.Scalable and efficientprovable data possession[C]//Proceedings of the 4th International Conference on Security and Privacy in Communication Networks，2008：1-10.

[14]Erway C C，Küp?ü A，Papamanthou C，et al.Dynamic provable data possession[J].ACM Transactions on Information and System Security（TISSEC），2015，17（4）：15.

[15]陳蘭香.一種基于同態(tài) Hash的數(shù)據(jù)持有性證明方法[J].電子與信息學(xué)報(bào)，2011，33（9）：2199-2204.

[16]Krohn M N，F(xiàn)reedman M J，Mazieres D.On-the-fly verification of rateless erasure codes for efficient content distribution[C]//IEEE Symposium on Security and Privacy，2004：226-240.

[17]李超零，陳越，譚鵬許，等.基于同態(tài)hash的數(shù)據(jù)多副本持有性證明方案[J].計(jì)算機(jī)應(yīng)用研究，2013，30（1）：265-269.

[18]李超零，陳越，余洋，等.一種動(dòng)態(tài)數(shù)據(jù)多副本持有性證明方案[J].信息工程大學(xué)學(xué)報(bào)，2014，15（4）：385-392.

[19]Shor P W.Algorithms for quantum computation：Discrete logarithms and factoring[C]//Proceedings of the 35th Annual Symposium on Foundations of Computer Science，1994：124-134.

[20]Grover L K.A fast quantum mechanical algorithm for database search[C]//Proceedings of the Twenty-eighth Annual ACM Symposium on Theory of Computing，1996：212-219.

[21]黃石，劉文卓，曹天杰.改進(jìn)的基于同態(tài)哈希的云存儲(chǔ)數(shù)據(jù)完整性驗(yàn)證方案[J].河海大學(xué)學(xué)報(bào)：自然科學(xué)版，2015，43（3）.

[22]Augot D，F(xiàn)iniasz M，Sendrier N.A family of fast syndrome based cryptographic hash functions[C]//Dawson E，Vaudenay S.Progress in Cryptology-Mycrypt 2005.Berlin Heidelberg：Springer，2005：64-83.

[23]任方，鄭東.一種基于編碼的數(shù)字簽名算法的改進(jìn)[J].西安郵電大學(xué)學(xué)報(bào)，2015，20（4）：38-43.

XU Bihan1，2,ZHENG Dong1，2,REN Fang1，2

1.School of Communication and Information Engineering,Xi’an University of Posts and Telecommunications,Xi’an 710121,China 2.National Engineering Laboratory for Wireless Security,Xi’an University of Posts and Telecommunications,Xi’an 710121,China

Coding homomorphic hashing based provable data possession.Computer Engineering and Applications,2017,53（21）：91-97.

In order to verify the integrity of the data that users have stored in the storage server,based on analysis of existing Provable Data Possession（PDP）scheme and a homomorphic encoding hash function,this scheme puts forward a PDP solution.By pseudo-random number with the data block“bundling”as a tag to fix the position of the block,while the introduction of Hash function based on an encoding,this scheme also uses the homomorphic to complete data possession verification.The security of this scheme is dependent on NP-complete decoding against quantum attacks.It is more difficult to be broken than the traditional homomorphic hashing based PDP method.In theory,the algorithm scheme is more faster and effective.

data integrity;data possession;encoding Hash;the homomorphism;tag;quantum attack

A

TP309.2

10.3778/j.issn.1002-8331.1605-0092

國家自然科學(xué)基金（No.61272037，No.61472472）；陜西省自然科學(xué)基金（No.2015JQ6262）；陜西省教育廳專項(xiàng)科研項(xiàng)目（No.15JK1669）；西安郵電大學(xué)研究生創(chuàng)新基金（No.CXL2015-28）。

徐碧晗（1991—），女，碩士研究生，研究領(lǐng)域?yàn)樾畔踩珽-mail：xbh378698@163.com；鄭東（1964—），男，博士，教授，研究領(lǐng)域?yàn)槊艽a學(xué)，云存儲(chǔ)安全；任方（1981—），男，博士，副教授，研究領(lǐng)域?yàn)槊艽a學(xué)與信息安全。

2016-05-10

2016-09-19

1002-8331（2017）21-0091-07

CNKI網(wǎng)絡(luò)優(yōu)先出版：2016-12-02,http://www.cnki.net/kcms/detail/11.2127.TP.20161202.1503.026.html