葛奕飛，鄭彥斌

(1. 桂林電子科技大學(xué) 數(shù)學(xué)與計算科學(xué)學(xué)院， 廣西 桂林 541004；2. 桂林電子科技大學(xué) 廣西密碼學(xué)與信息安全重點實驗室，廣西 桂林 541004)

隱私保護信息檢索(private information retrieval，PIR)最早由Chor等[1-2]提出，并逐漸發(fā)展成為理論計算機科學(xué)和密碼學(xué)領(lǐng)域的經(jīng)典問題之一[3-5]。這一問題考慮如何在一串n個比特位中檢索特定的一個比特，且使得服務(wù)器無法得知所檢索比特的具體指標(biāo)信息。在僅有一個服務(wù)器的情況下，平凡的解決方案是下載整個數(shù)據(jù)庫，在有多個服務(wù)器的時候，可以設(shè)計出更好的PIR方案。衡量方案優(yōu)劣的主要指標(biāo)是計算整個檢索過程中的數(shù)據(jù)傳輸量，其中既包括查詢時的上傳量，也包括來自服務(wù)器反饋的下載量。在這一領(lǐng)域已有一系列工作逐步優(yōu)化了數(shù)據(jù)傳輸量，主要結(jié)果詳見文獻[6-10]及其中的參考文獻。

經(jīng)典的模型下，各個服務(wù)器的反饋被假定為真實無誤的。但是信息的傳遞必然會伴隨著數(shù)據(jù)的丟失、噪聲干擾甚至人為的篡改。因此，本文將考慮帶有糾刪性質(zhì)或帶有糾錯性質(zhì)的PIR模型，其具體定義如下。

帶有糾刪性質(zhì)的PIR模型：在這種模型中，N個服務(wù)器中的至多Z個服務(wù)器的反饋信息會在文件檢索過程中丟失，用戶在檢索之前并不知曉哪些服務(wù)器的反饋會丟失，這一模型在文獻[19，25]中提出。

帶有糾錯性質(zhì)的PIR模型：在這種模型中，N個服務(wù)器中的至多B個服務(wù)器的反饋信息會在文件檢索過程中發(fā)生錯誤，這既可能來自信道的噪音，亦可能來自第三方的人為惡意篡改，用戶在檢索之前并不知曉哪些服務(wù)器的反饋會發(fā)生錯誤。這一模型在文獻[26]中提出。

本文的主要貢獻為推廣文獻[15-16，19，21]中的PIR方案構(gòu)造，以適用于帶有糾刪或糾錯性質(zhì)的PIR變種模型。主要結(jié)果如下：

本文結(jié)構(gòu)如下。第1章給出PIR經(jīng)典模型及本文所考慮的3個變種的具體數(shù)學(xué)描述，并以一個例子來解釋經(jīng)典模型下的一類PIR方案的設(shè)計；第2章考慮帶有糾刪性質(zhì)的PIR模型；第3章考慮帶有糾錯性質(zhì)的PIR模型；第4章總結(jié)并展望后續(xù)的研究方向。

1 問題模型

下面介紹PIR模型及其相關(guān)變種的具體數(shù)學(xué)描述。

每個文件經(jīng)由一個(N,K)-MDS碼獨立存儲于分布式系統(tǒng)中，這一存儲碼的生成矩陣記為

G=[g1g2…gN]K×N。

(1)

(2)

(3)

(4)

當(dāng)用戶從所有服務(wù)器得到反饋之后，通過一定的譯碼過程得到所需要檢索的文件W[i]。PIR方案需要保證譯碼的正確性：

(5)

在整個檢索過程中，經(jīng)典的PIR模型假設(shè)任意T個服務(wù)器之間可合謀分析用戶的隱私，這些服務(wù)器所能分析的即為用戶向其發(fā)送的問詢，或者等價地說，其向用戶發(fā)送的反饋。PIR模型需要保證任意T個合謀的服務(wù)器無法得到關(guān)于文件指標(biāo)i的任何信息：

(6)

以上是經(jīng)典的PIR模型的數(shù)學(xué)描述。下面介紹各個變種中的細(xì)節(jié)變化。

在帶有糾刪性質(zhì)的PIR模型中，假設(shè)所有N個服務(wù)器的某Z個的反饋會在傳輸過程中丟失。在這種情況下，譯碼的正確性只能依靠正常收到的N-Z個反饋，即經(jīng)典模型中的譯碼正確性的描述(5)應(yīng)修改為

(7)

在帶有糾錯性質(zhì)的PIR模型中，假設(shè)所有N個服務(wù)器的某B個(記為集合B)的反饋會在傳輸過程中發(fā)生自然的或者人為的錯誤，也就是說，對于這些服務(wù)器而言，其反饋并不是完全由問詢和存儲內(nèi)容所唯一決定的函數(shù)，即經(jīng)典模型中的反饋內(nèi)容描述(4)應(yīng)修改為

(8)

用戶需要統(tǒng)籌利用這些帶有錯誤的反饋和其他服務(wù)器上的正確反饋，借由糾錯碼完成文件檢索。其他數(shù)學(xué)描述與經(jīng)典模型一致。

下面簡單回顧以文獻[15]為藍本的一類PIR方案的構(gòu)造思路?？紤]參數(shù)N=3,M=3,K=1,T=1這一情形，且不考慮糾刪糾錯性質(zhì)。這一設(shè)定下的PIR方案如表1所示(以字母a、b、c代指3個不同文件，用戶檢索文件a)，其碼率達到了最優(yōu)的PIR容量9/13。

表1 N=3,M=3,K=1,T=1時的PIR方案

表1中，每個文件長度為27，a[1:27],b[1:27],c[1:27]分別為3個文件的27 位字符各自經(jīng)過隨機的置換之后所得到的字符串(這里隨機的置換也是用來保障隱私性的一環(huán))。此PIR方案包括如下幾步：

①用戶首先向各服務(wù)器下載文件a的一個字符a1、a2、a3；為保障隱私性，需要對其它文件也采取同樣的行為，下載b1、b2、b3、c1、c2、c3；

②此時，所下載的b1、b2、b3、c1、c2、c3作為冗余信息，可以用來作為進一步檢索文件a時的輔助信息，則有了形如a4+b2這一部分下載，通過已知的輔助信息b2來得到a4，注意到每個服務(wù)器利用的都是其他服務(wù)器所提供的輔助信息；

③同理，在有了形如a4+b2、a10+c2這類下載之后，需要對文件b、c的組合采取同樣的行為，得到形如b4+c4這一部分下載；

④最終，形如b4+c4這種冗余信息，又可以用來作為進一步檢索文件a時的輔助信息，則有了形如a16+b6+c6這一部分下載，即通過已知的輔助信息b6+c6來得到a16。

本質(zhì)上，這一類PIR方案設(shè)計的核心思路是層層利用冗余信息作為輔助信息，保持查詢方案中文件之間的對稱性和服務(wù)器之間的對稱性。在接下來本文所考慮的帶有糾刪性質(zhì)和帶有糾錯性質(zhì)的PIR模型中，也將依照這樣的方法構(gòu)造PIR 方案，但在參數(shù)K、T和糾刪糾錯性質(zhì)的影響下，下載的內(nèi)容形式并不僅僅是簡單的來自文件的某個信息位字符或者多個信息位字符的組合，而需要是各個文件經(jīng)過一定編碼方式之后的字符組合。

2 帶有糾刪性質(zhì)的PIR方案

2.1 方案構(gòu)造

帶有糾刪性質(zhì)的PIR方案的構(gòu)造需以下幾個步驟：

①取定參數(shù)α和β，它們是滿足下述方程的最小正整數(shù)(最小這個要求可忽略，只是為了盡量簡化方案的規(guī)模/文件的大小，不影響整個方案的設(shè)計)

(9)

⑥將已預(yù)備的模塊進行分組，設(shè)集合D 為所有N個文件的一個非空子集，但不包含文件W[1]。如第④步中所要求，標(biāo)號為D 的模塊數(shù)目為αM-|D |β|D |-1，標(biāo)號為D ∪{W[1]}的模塊數(shù)目為αM-|D |-1β|D |。將這些模塊劃分到αM-|D |-1β|D |-1個區(qū)組之中，每個區(qū)組里有α個標(biāo)號為D 的模塊和β個標(biāo)號為D ∪{W[1]}的模塊。這些區(qū)組也稱為標(biāo)號為D 的區(qū)組，記為ΓDλ, 1≤λ≤αM-|D |-1β|D |-1。

下節(jié)將通過一個例子來理解上述構(gòu)造。

2.2 例N=6, Z=1, K=2, T=2, M=2

參照構(gòu)造方案，所涉及的參數(shù)取值為α=9，β=1，L=100，輔助陣列形如

2個文件符號簡記為U和V。每個文件長度為200，并各自以100×2矩陣的形式表示為

(10)

不失一般性，假設(shè)服務(wù)器Ⅰ的傳輸內(nèi)容丟失，則用戶可成功得到的信息只有{ai+bi:6≤i≤15}和{x15η+i:x∈{a,b},1≤η≤9,6≤i≤15}。下面說明這部分信息已足夠。利用MDS150×90的性質(zhì)，用戶可以通過獲得的90個b型字符串譯碼得到所有的b[1:150]，特別地，用戶可以最后譯碼得出{bi:6≤i≤15}。在{ai+bi:6≤i≤15}之中去掉來自{bi:6≤i≤15}的干擾信息后，用戶成功得到{ai:6≤i≤15}。最后，借由MDS15×10的性質(zhì)和S1為滿秩矩陣這一事實，用戶可譯碼得到全部{a15η+i:0≤η≤9, 1≤i≤15}，即得到整個文件U。

2.3 方案分析

綜上所述，對于帶有糾刪性質(zhì)的PIR模型，本文構(gòu)造的方案滿足：

3 帶有糾錯性質(zhì)的PIR方案

3.1 方案構(gòu)造

帶有糾錯性質(zhì)的PIR方案的構(gòu)造與第2章帶糾刪性質(zhì)的模型相仿，但由于在問詢符號之間需引入不同的冗余方式，則整個方案的相關(guān)參數(shù)也有一定的變化。參照帶糾刪性質(zhì)的方案，帶有糾錯性質(zhì)的PIR方案的構(gòu)造需以下幾個步驟：

①決定參數(shù)α和β的方程調(diào)整為

(11)

③與④同2.1節(jié)保持一致。

⑥同2.1節(jié)保持一致。

通過與2.1節(jié)糾刪PIR方案的對比可見，2個方案的核心區(qū)別源于參數(shù)α和β的選取，進而影響了問詢符號之間的冗余度設(shè)置以及同一個區(qū)組之中不同標(biāo)號的模塊的數(shù)目比例。同樣，下節(jié)將通過一個例子來理解上述構(gòu)造。

3.2 例N=8, B=1, K=2, T=2, M=2

參照構(gòu)造方案，所涉及的參數(shù)取值為α=13,β=1,L=196，輔助陣列形如

2個文件符號簡記為U和V，每個文件長度為392，并各自以196×2矩陣的形式表示為：

(12)

3.3 方案分析

綜上所述，對于帶有糾錯性質(zhì)的PIR模型，本文構(gòu)造的方案滿足：

4 總結(jié)

本文將經(jīng)典PIR模型中的一類PIR方案加以推廣，增加了在傳輸過程中的糾刪或糾錯的能力。本文核心方法是在問詢向量中引入一定的冗余并依賴一定的數(shù)學(xué)結(jié)構(gòu)將這些問詢向量分配到不同的服務(wù)器上。本文方法可進一步推廣至既帶有糾刪又同時帶有糾錯能力的PIR模型中，這類模型中的最優(yōu)PIR容量仍為一個公開問題，后續(xù)的研究方向可以是利用信息論工具研究最優(yōu)PIR 容量的上下界，或者進一步優(yōu)化本文PIR方案的碼率。