具有低編解碼復雜度的私有信息檢索

代明軍，李曉鳳，鄧海燕，陳 彬

(深圳大學 電子與信息工程學院，廣東 深圳 518060)

私有信息檢索(Private Information Retrieval，PIR)[1-2]是指用戶從分布式系統中檢索文件時不會向系統透露任何有關正在檢索哪個文件的信息。私有信息檢索在商業競爭、軍事合作、專利數據庫查詢、股票數據庫查詢、數字產品在線交易、云計算等分布式存儲系統(DSS)領域有著廣泛的應用[3-5]。私有信息檢索研究工作的主要目標是盡量減少上傳和下載的通信消耗[6]。TIAN等[7]提出一種不對稱碼來實現私有信息檢索方案的消息大小和上載成本最佳。最初的私有信息檢索方案大多是基于復制的分布式存儲系統，采用將文件簡單地復制到多個存儲節點存儲的方法[1-2，8-10]。因為是直接復制存儲的，所以它的存儲空間效率很低。后來基于網絡編碼(NC)的分布式存儲系統受到了研究者們的關注[11-13]，因為它提供了更好的數據可靠性性能，并且它的數據包是網絡編碼的，具有組合屬性(CP)：k個原始數據包被編碼為n(n≥k)個編碼數據包，n個編碼數據包中的任意k個可以解碼得到原始的k個數據包。例如，文獻[14]中研究的存在串謀、拜占庭、不響應的服務器的存儲系統的基于RS存儲碼的私有信息檢索協議；文獻[15]中提出一種基于MDS陣列碼的私有信息檢索協議，使得修復帶寬可以接近最佳。

現有的基于網絡編碼的私有信息檢索方案的不足之處在于：網絡編碼采用的是里德所羅門碼[16-18]。這個碼的操作要在一個很大的有限域內進行，其編碼和解碼復雜度過高[19-20]。在下面兩個場景中需要考慮具有低解碼復雜度的方案：(1)類似大數據存儲和頻繁的讀寫操作這樣解碼能量消耗巨大的場景[21-22]；(2)類似只有有限的計算能力和解碼能力的手持設備和無線云存儲系統的場景[23-25]。因此，設計具有低解碼復雜度的分布式存儲系統框架的私有信息檢索方案是必要的。

針對上述的缺點，筆者研究了在分布式存儲系統框架下具有低解碼復雜度的私有信息檢索方案，并考慮節點都是非串謀節點，即每個節點不向其他節點共享自己的信息。設計方案的目標是下載通信成本要盡量低和計算復雜度低。計算復雜度的大小主要是在計算的有限域的大小和解碼過程中解線性方程。目前解碼降低計算復雜度低的方法有LU解碼[26]和鋸齒解碼[27]。文獻[26]中針對從k個數據包中恢復r個數據包，提出一種基于EVENODD碼和RDP碼的LU解碼方案來降低解碼復雜度；文獻[28]中將鋸齒解碼應用在分布式存儲中修復節點，實現了最優修復帶寬和低計算復雜度。因為不考慮帶寬的修復，因此基于不考慮修復帶寬的純CP-ZD碼與文獻[26，28]有所不同。由于鋸齒解碼可在二元域進行操作，并且可以避免一系列的線性變換，鋸齒解碼的形式是向后替換，其解碼復雜度非常低，且解碼過程簡單，故采用CP-BZD編碼和鋸齒解碼來實現低計算復雜度的私有信息檢索。

1 預備知識

1.1 CP-BZD碼

CP-BZD存儲碼[19]是一種性能很好的存儲碼。CP(Combination Property)具有組合性質，BZD(Binary Zigzag Decoding)是指二進制域內的鋸齒形譯碼。CP-BZD編碼將文件分成多份，然后根據移位矩陣進行編碼。具體操作如下：將原始數據等分成k個長度為L的數據包，分別表示為s1，s2，…，sk，si，j∈{0，1}表示si的第j個比特，i∈{1，…，k}=K。這k個數據包根據(n，k)CP-BZD碼被編碼為n個編碼包，這n個編碼包表示為c1，c2，…，cn。由于CP-BZD碼具有系統性質，所以ci=si，i∈K。將前k個編碼包稱為系統包，剩下的α=n-k個編碼包稱為校驗包。CP-BZD碼的操作是在二進制域中進行的，是可鋸齒解碼的。

CP-BZD編碼生成校驗包的方法如下：校驗包是通過先將k個原始數據包分別移位不同的位數，然后按位方式在二進制域上逐位相加而產生的。每個原始數據包移位的位數用矩陣T表示：

(1)

用z表示數據包向右移一位。例如，si+zsj表示sj相對si向右移一位，然后再按位對齊方式在二進制域上逐位相加。z2表示數據包向右移兩位，依此類推。

鋸齒解碼在文獻[29]中有具體描述。為了論文的完整性，簡單闡述鋸齒解碼的過程。在解碼過程中，試圖找到一個與該校驗包中其他源塊的任何位都不重疊的暴露位，此位可被視為已恢復；然后可以從其他校驗包中減去該位。隨著解碼的進行，每個校驗包的長度變得越來越短。此過程將繼續，直到找不到暴露的位而結束解碼過程。

例如圖1，用(4，2)的例子來說明編碼和解碼的具體過程。原始數據被分為兩個長度相等的數據包s1和s2，每個數據包的長度L=4，把這兩個數據包視為前兩個編碼包c1和c2，另外的兩個編碼包表示為c3和c4。根據上面的矩陣T，把兩個源包s1和s2分別右移0位和1位，然后以二進制的方式按列逐位相加，生成c3。同理，兩個源包s1和s2分別被右移0位和2位，然后以二進制的方式按列逐位相加，生成c4。可以這樣表示：c3=c1+zc2和c4=c1+z2c2。

圖1 (4，2)CP-BZD碼的解碼

假設要從c3，c4中恢復出原始數據。首先，在c3和c4中，最左邊的暴露位分別是s1，1、s1，2，因為它們不涉及任何與其他信息位的計算，所以可以直接得到s1，1、s1，2，它們被認為是第1和第2個恢復的比特，在括號內用索引1和2表示。然后，將s1，2代入c3的第2位，并恢復s2，1，這個是第3個恢復的比特，在括號內用索引3表示。類似地，將s2，1代入c4的第3位，并恢復s1，3，這是第4個恢復的比特，在括號內用索引4表示。重復上述解碼過程，直至所有的比特都被恢復出來。

1.2 私有信息檢索方案的系統模型

表1 文件存儲模型

假設用戶對n個存儲節點中存的某個文件感興趣，想要下載這個文件，這個文件可以是m個文件中的任意一個。用sf表示用戶想要檢索的文件，f表示這個文件的索引。假設系統中不存在互相串謀的節點，也就是說，每個節點只知道自己的信息，不會將自己的信息共享給其他節點，每個節點都是有響應的。

2 私有信息檢索解決方案

筆者提出的方案分為兩個階段：首先是用戶向系統請求查詢，并從系統中下載數據包的數據請求和下載階段；然后是用戶對下載的數據包進行解碼階段。

2.1 數據請求和下載階段

在這一階段有兩個部分：第1部分，用戶生成查詢向量，然后將查詢向量發送給存儲節點；第2部分，用戶從存儲節點處接收到返回的數據包。

第1部分有兩個步驟。

步驟1 首先用戶生成k個長度為mα的隨機向量U1，U2，…，Uk；然后用戶生成k個長度為mα的檢索向量，檢索向量中包含了要檢索文件的索引信息。為了方便表達，將U1，U2，…，Uk垂直連接構成大小為k×mα的隨機矩陣U。相似地，垂直連接檢索向量可構成大小為k×mα的檢索矩陣El，l∈N。El是要發送給第l個節點的檢索矩陣，El的構造分為n≥2k和n<2k，分別討論。

(1)n≥2k的情況

當l=k+1時，

Ek+1=[0k×(f-1)αEf0k×(m-f)α]，

(2)

其中，Ef是Ek+1中的子矩陣，大小為k×α。Ef的表達式為

Ef=[Ik×k0k×(m-f)α] 。

(3)

當l=k+2，…，n時，El中的子矩陣Ef是由El-1的Ef中的列向量循環右移一位得到的。

(2)n<2k的情況

當l=1時，

(4)

當l=2，…，k時，El是由El-1中的行向量循環移位一位得到的。

步驟2 步驟1中得到隨機矩陣和檢索矩陣后，用戶再構造查詢矩陣，發送給存儲節點進行查詢。發送給節點l的查詢矩陣表示為Ql，Ql的行向量也就是用戶每輪查詢發送給節點的查詢向量。

(1)n≥2k：對于系統節點，用戶發送查詢矩陣Ql=U給系統節點，l∈Κ。對于校驗節點，用戶發送查詢矩陣Ql=U+El給校驗節點，l=k+1，…，n。

(2)n<2k：對于系統節點，用戶發送查詢矩陣Ql=U+El給系統節點，l∈Κ。對于校驗節點，用戶發送查詢矩陣Ql=U給校驗節點，l=k+1，…，n。

(5)

圖2 數據包

2.2 數據解碼階段

圖的解碼過程

圖的解碼過程

3 PIR方案性能分析

3.1 私有性分析

綜上所述，此方案用戶的隱私性是可以保證的。

3.2 通信成本和解碼復雜度分析

3.2.1 通信成本

通信成本是數據查詢和下載階段比特的傳輸量與檢索文件比特大小的比。數據查詢階段比特的上傳量相對于數據下載階段是非常小的，可以忽略不計，所以只討論數據下載階段的通信量。

先定義一些符號：max{Uji}是查詢向量Uj的最大元素，max{Uji+efβ}是查詢向量Uj+efβ的最大元素。

當n≥2k時，每個系統節點都存儲了ma個長度為L比特的數據包，每輪查詢每個系統節點發送給用戶的比特數是max{Uji}+L。校驗節點i存儲了mα個長度為i(k-1)+L比特的數據包，每輪查詢它傳輸給用戶的比特數是max{Uji+efβ}+i(k-1)+L。方案的比特總下載量表示為DPIR。當n≥2k時，

(6)

當n<2k時，在每輪查詢中，有k-α個系統節點接收到Uj，α個系統節點接收到Uj+efβ。又因系統節點存儲了mα個長度為L比特的數據包，因此，從每個系統節點處的下載量是max{Uji}+L或max{Uji+efβ}+L個比特。每個校驗節點i存儲了mα個長度為i(k-1)+L比特的數據包且接收到的查詢向量是Uj，因此它傳輸給用戶的比特量是max{Uji}+i(k-1)+L。故可以得到總的下載量為

(7)

實際上數據包的長度L非常大，max{Uji}、max{Uji+efβ}和i(k-1)相對可以忽略不計，故下載量為

DPIR=nLk。

(8)

私有信息檢索方案的通信成本表示為DccPIR，故有

(9)

3.2.2 解碼復雜度

在文獻[14]中，解碼復雜度高的原因有兩個：一是解碼操作在一個非常大的有限域內進行，二是解碼時需要進行矩陣求逆。筆者提出的私有信息檢索方案是基于二進制域的，解碼采用的是鋸齒解碼，不需要進行矩陣求逆操作，明顯地降低了解碼復雜度，它的解碼復雜度是O(k2L)。因為方案的編碼是采用二進制移位再相加的形式，所以會帶來一些額外的存儲開銷，移位量最大是α(k-1)，編碼后的額外開銷最大是α(k-1)。每個源包的長度為L，當L?α(k-1)時，這個存儲開銷可忽略。

4 總 結

未來的研究工作會考慮設計不會增加額外存儲開銷或存儲開銷盡量小的具有低計算復雜度的私有信息檢索方案。當系統中存在互相串謀的節點時，如何實現低計算復雜度的私有信息檢索，也是未來研究工作的一個方面。