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

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

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

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

針對(duì)上述的缺點(diǎn)，筆者研究了在分布式存儲(chǔ)系統(tǒng)框架下具有低解碼復(fù)雜度的私有信息檢索方案，并考慮節(jié)點(diǎn)都是非串謀節(jié)點(diǎn)，即每個(gè)節(jié)點(diǎn)不向其他節(jié)點(diǎn)共享自己的信息。設(shè)計(jì)方案的目標(biāo)是下載通信成本要盡量低和計(jì)算復(fù)雜度低。計(jì)算復(fù)雜度的大小主要是在計(jì)算的有限域的大小和解碼過(guò)程中解線性方程。目前解碼降低計(jì)算復(fù)雜度低的方法有LU解碼[26]和鋸齒解碼[27]。文獻(xiàn)[26]中針對(duì)從k個(gè)數(shù)據(jù)包中恢復(fù)r個(gè)數(shù)據(jù)包，提出一種基于EVENODD碼和RDP碼的LU解碼方案來(lái)降低解碼復(fù)雜度；文獻(xiàn)[28]中將鋸齒解碼應(yīng)用在分布式存儲(chǔ)中修復(fù)節(jié)點(diǎn)，實(shí)現(xiàn)了最優(yōu)修復(fù)帶寬和低計(jì)算復(fù)雜度。因?yàn)椴豢紤]帶寬的修復(fù)，因此基于不考慮修復(fù)帶寬的純CP-ZD碼與文獻(xiàn)[26，28]有所不同。由于鋸齒解碼可在二元域進(jìn)行操作，并且可以避免一系列的線性變換，鋸齒解碼的形式是向后替換，其解碼復(fù)雜度非常低，且解碼過(guò)程簡(jiǎn)單，故采用CP-BZD編碼和鋸齒解碼來(lái)實(shí)現(xiàn)低計(jì)算復(fù)雜度的私有信息檢索。

1 預(yù)備知識(shí)

1.1 CP-BZD碼

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

CP-BZD編碼生成校驗(yàn)包的方法如下：校驗(yàn)包是通過(guò)先將k個(gè)原始數(shù)據(jù)包分別移位不同的位數(shù)，然后按位方式在二進(jìn)制域上逐位相加而產(chǎn)生的。每個(gè)原始數(shù)據(jù)包移位的位數(shù)用矩陣T表示：

(1)

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

鋸齒解碼在文獻(xiàn)[29]中有具體描述。為了論文的完整性，簡(jiǎn)單闡述鋸齒解碼的過(guò)程。在解碼過(guò)程中，試圖找到一個(gè)與該校驗(yàn)包中其他源塊的任何位都不重疊的暴露位，此位可被視為已恢復(fù)；然后可以從其他校驗(yàn)包中減去該位。隨著解碼的進(jìn)行，每個(gè)校驗(yàn)包的長(zhǎng)度變得越來(lái)越短。此過(guò)程將繼續(xù)，直到找不到暴露的位而結(jié)束解碼過(guò)程。

例如圖1，用(4，2)的例子來(lái)說(shuō)明編碼和解碼的具體過(guò)程。原始數(shù)據(jù)被分為兩個(gè)長(zhǎng)度相等的數(shù)據(jù)包s1和s2，每個(gè)數(shù)據(jù)包的長(zhǎng)度L=4，把這兩個(gè)數(shù)據(jù)包視為前兩個(gè)編碼包c(diǎn)1和c2，另外的兩個(gè)編碼包表示為c3和c4。根據(jù)上面的矩陣T，把兩個(gè)源包s1和s2分別右移0位和1位，然后以二進(jìn)制的方式按列逐位相加，生成c3。同理，兩個(gè)源包s1和s2分別被右移0位和2位，然后以二進(jìn)制的方式按列逐位相加，生成c4?？梢赃@樣表示：c3=c1+zc2和c4=c1+z2c2。

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

假設(shè)要從c3，c4中恢復(fù)出原始數(shù)據(jù)。首先，在c3和c4中，最左邊的暴露位分別是s1，1、s1，2，因?yàn)樗鼈儾簧婕叭魏闻c其他信息位的計(jì)算，所以可以直接得到s1，1、s1，2，它們被認(rèn)為是第1和第2個(gè)恢復(fù)的比特，在括號(hào)內(nèi)用索引1和2表示。然后，將s1，2代入c3的第2位，并恢復(fù)s2，1，這個(gè)是第3個(gè)恢復(fù)的比特，在括號(hào)內(nèi)用索引3表示。類似地，將s2，1代入c4的第3位，并恢復(fù)s1，3，這是第4個(gè)恢復(fù)的比特，在括號(hào)內(nèi)用索引4表示。重復(fù)上述解碼過(guò)程，直至所有的比特都被恢復(fù)出來(lái)。

1.2 私有信息檢索方案的系統(tǒng)模型

表1 文件存儲(chǔ)模型

假設(shè)用戶對(duì)n個(gè)存儲(chǔ)節(jié)點(diǎn)中存的某個(gè)文件感興趣，想要下載這個(gè)文件，這個(gè)文件可以是m個(gè)文件中的任意一個(gè)。用sf表示用戶想要檢索的文件，f表示這個(gè)文件的索引。假設(shè)系統(tǒng)中不存在互相串謀的節(jié)點(diǎn)，也就是說(shuō)，每個(gè)節(jié)點(diǎn)只知道自己的信息，不會(huì)將自己的信息共享給其他節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)都是有響應(yīng)的。

2 私有信息檢索解決方案

筆者提出的方案分為兩個(gè)階段：首先是用戶向系統(tǒng)請(qǐng)求查詢，并從系統(tǒng)中下載數(shù)據(jù)包的數(shù)據(jù)請(qǐng)求和下載階段；然后是用戶對(duì)下載的數(shù)據(jù)包進(jìn)行解碼階段。

2.1 數(shù)據(jù)請(qǐng)求和下載階段

在這一階段有兩個(gè)部分：第1部分，用戶生成查詢向量，然后將查詢向量發(fā)送給存儲(chǔ)節(jié)點(diǎn)；第2部分，用戶從存儲(chǔ)節(jié)點(diǎn)處接收到返回的數(shù)據(jù)包。

第1部分有兩個(gè)步驟。

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

(1)n≥2k的情況

當(dāng)l=k+1時(shí)，

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

(2)

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

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

(3)

當(dāng)l=k+2，…，n時(shí)，El中的子矩陣Ef是由El-1的Ef中的列向量循環(huán)右移一位得到的。

(2)n<2k的情況

當(dāng)l=1時(shí)，

(4)

當(dāng)l=2，…，k時(shí)，El是由El-1中的行向量循環(huán)移位一位得到的。

步驟2 步驟1中得到隨機(jī)矩陣和檢索矩陣后，用戶再構(gòu)造查詢矩陣，發(fā)送給存儲(chǔ)節(jié)點(diǎn)進(jìn)行查詢。發(fā)送給節(jié)點(diǎn)l的查詢矩陣表示為Ql，Ql的行向量也就是用戶每輪查詢發(fā)送給節(jié)點(diǎn)的查詢向量。

(1)n≥2k：對(duì)于系統(tǒng)節(jié)點(diǎn)，用戶發(fā)送查詢矩陣Ql=U給系統(tǒng)節(jié)點(diǎn)，l∈Κ。對(duì)于校驗(yàn)節(jié)點(diǎn)，用戶發(fā)送查詢矩陣Ql=U+El給校驗(yàn)節(jié)點(diǎn)，l=k+1，…，n。

(2)n<2k：對(duì)于系統(tǒng)節(jié)點(diǎn)，用戶發(fā)送查詢矩陣Ql=U+El給系統(tǒng)節(jié)點(diǎn)，l∈Κ。對(duì)于校驗(yàn)節(jié)點(diǎn)，用戶發(fā)送查詢矩陣Ql=U給校驗(yàn)節(jié)點(diǎn)，l=k+1，…，n。

(5)

圖2 數(shù)據(jù)包

2.2 數(shù)據(jù)解碼階段

圖的解碼過(guò)程

圖的解碼過(guò)程

3 PIR方案性能分析

3.1 私有性分析

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

3.2 通信成本和解碼復(fù)雜度分析

3.2.1 通信成本

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

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

當(dāng)n≥2k時(shí)，每個(gè)系統(tǒng)節(jié)點(diǎn)都存儲(chǔ)了ma個(gè)長(zhǎng)度為L(zhǎng)比特的數(shù)據(jù)包，每輪查詢每個(gè)系統(tǒng)節(jié)點(diǎn)發(fā)送給用戶的比特?cái)?shù)是max{Uji}+L。校驗(yàn)節(jié)點(diǎn)i存儲(chǔ)了mα個(gè)長(zhǎng)度為i(k-1)+L比特的數(shù)據(jù)包，每輪查詢它傳輸給用戶的比特?cái)?shù)是max{Uji+efβ}+i(k-1)+L。方案的比特總下載量表示為DPIR。當(dāng)n≥2k時(shí)，

(6)

當(dāng)n<2k時(shí)，在每輪查詢中，有k-α個(gè)系統(tǒng)節(jié)點(diǎn)接收到Uj，α個(gè)系統(tǒng)節(jié)點(diǎn)接收到Uj+efβ。又因系統(tǒng)節(jié)點(diǎn)存儲(chǔ)了mα個(gè)長(zhǎng)度為L(zhǎng)比特的數(shù)據(jù)包，因此，從每個(gè)系統(tǒng)節(jié)點(diǎn)處的下載量是max{Uji}+L或max{Uji+efβ}+L個(gè)比特。每個(gè)校驗(yàn)節(jié)點(diǎn)i存儲(chǔ)了mα個(gè)長(zhǎng)度為i(k-1)+L比特的數(shù)據(jù)包且接收到的查詢向量是Uj，因此它傳輸給用戶的比特量是max{Uji}+i(k-1)+L。故可以得到總的下載量為

(7)

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

DPIR=nLk。

(8)

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

(9)

3.2.2 解碼復(fù)雜度

在文獻(xiàn)[14]中，解碼復(fù)雜度高的原因有兩個(gè)：一是解碼操作在一個(gè)非常大的有限域內(nèi)進(jìn)行，二是解碼時(shí)需要進(jìn)行矩陣求逆。筆者提出的私有信息檢索方案是基于二進(jìn)制域的，解碼采用的是鋸齒解碼，不需要進(jìn)行矩陣求逆操作，明顯地降低了解碼復(fù)雜度，它的解碼復(fù)雜度是O(k2L)。因?yàn)榉桨傅木幋a是采用二進(jìn)制移位再相加的形式，所以會(huì)帶來(lái)一些額外的存儲(chǔ)開(kāi)銷，移位量最大是α(k-1)，編碼后的額外開(kāi)銷最大是α(k-1)。每個(gè)源包的長(zhǎng)度為L(zhǎng)，當(dāng)L?α(k-1)時(shí)，這個(gè)存儲(chǔ)開(kāi)銷可忽略。

4 總 結(jié)

未來(lái)的研究工作會(huì)考慮設(shè)計(jì)不會(huì)增加額外存儲(chǔ)開(kāi)銷或存儲(chǔ)開(kāi)銷盡量小的具有低計(jì)算復(fù)雜度的私有信息檢索方案。當(dāng)系統(tǒng)中存在互相串謀的節(jié)點(diǎn)時(shí)，如何實(shí)現(xiàn)低計(jì)算復(fù)雜度的私有信息檢索，也是未來(lái)研究工作的一個(gè)方面。