互聯網的普及意味著有大量的在線數據和檢索信息不可或缺的資源, 在某種程度上，也對用戶隱私構成了重大風險。事實上，在用戶意圖保密的情況下，用戶通常對訪問公共數據持謹慎態度。例如，公司可能希望不透露自己身份來搜索某些專利。

那么，如何在用戶進行信息檢索時保護用戶的隱私呢？這或許會涉及到一種名為隱私信息檢索的技術。

什么是隱私信息檢索？

隱私信息檢索是一種加密協議，旨在保障數據使用者的私隱，允許客戶端從公共數據庫中檢索記錄，同時向數據所有者隱藏檢索記錄的身份。實際上，檢索數據而不向數據所有者透露其身份的可能性幾乎為零。當然，有一個簡單的解決方案: 當用戶需要單個數據時，可以要求獲得整個數據庫的副本。然而，這種解決方案涉及了巨大的通信開銷，可能是不可接受的。對于那些希望完全保護自己隱私的用戶，這種簡單的解決方案是最佳的。

在1995年，業界提出了 隱私信息檢索方案，在該方案的協議中，用戶查詢保存數據庫的每個服務器，確保每個單獨的服務器得不到關于用戶感興趣項的標識信息。

隱私信息檢索方案與一類特殊的糾錯碼密切相關，這類糾錯碼被稱為“局部可解碼碼”，它們本身就是人們感興趣的對象。糾錯碼有助于確保信息在嘈雜信道上的可靠傳輸，以及在取設備容易出錯的介質上可靠地存儲信息。這種編碼允許人們向消息中添加冗余或位字符串，并將其編碼成更長的位字符串，即使一定比例的位字符串被破壞，消息仍然可以恢復。在糾錯碼的典型應用中，消息首先被分成小塊，然后每個小塊被分別編碼。這種編碼策略允許對信息進行有效的隨機訪問檢索，因為只需要對感興趣的部分數據進行解碼。不幸的是，這種策略產生了較差的噪音恢復能力，因為，即使是一個單一的塊完全損壞，一些信息就會丟失。

鑒于這種局限性，似乎更可取的做法是將整個信息編碼成一個前向糾錯的單一碼字。這種解決方案提高了對噪聲的魯棒性，但是很難令人滿意，因為需要查看整個碼字，以便恢復消息的任何特定位。這種解碼復雜度對于當今的大規模數據集來說是不可能的。

隱私信息檢索方案提供了有效的隨機存取檢索和高噪聲恢復能力，允許通過只查看少量隨機選擇的碼字比特就可以對任意比特的信息進行可靠的重建。

初識隱私信息檢索

如果將數據建模為 n 位字符串 X，該字符串只在少量服務器 S1，... ，Sk 之間復制。用戶持有一個索引 i (介于1和 n 之間的整數) ，并對獲取位 Xi 的值感興趣。為了實現這個目標，用戶隨機查詢每個服務器，并接收響應，從中計算所需的位 Xi。對每個服務器的查詢是獨立于 i 分布的，因此，每個服務器不會獲得關于用戶需要什么的信息。

用戶的查詢不一定是對特定單數據集的請求，它們指定由服務器計算的函數; 例如，一個查詢可能指定一組介于1和 n 之間的索引，而服務器的響應可能是存儲在這些索引的數據位 XOR。

隱私信息檢索方案的主要參數是通信復雜度，或者說是度量用戶和服務器之間通信的總比特數的函數。目前最有效的雙服務器隱私信息檢索協議的通信復雜度為 O (n的1/3次方)。然而，涉及三個或更多服務器的隱私信息檢索方案已經得到了改進。

Hadamard 編碼允許以非常大的代碼長度為代價，超快速地恢復消息位。例如，給定一個有10%損壞的編碼，只讀取兩個代碼位就能恢復消息的任何位，概率為80%。這意味著可以從許多不同的碼字比特的 k 元組中恢復消息的每個比特 Xi。因此，解碼器的每個查詢的分布必須在一定程度上接近于編碼位上的均勻分布。

驗證協議是私有的，也非常簡單，因為對于[ k ]中的每個 j，查詢 Qj 均勻地分布在碼字坐標集上，總的通信量由 k (logN + 1)給出。

早期的隱私信息檢索

隱私信息檢索方案的目標是通過提供一個簡單的(d + 1)服務器方案，使用 O (n的1/d次方)通信來訪問 n 位數據，這個方案背后的關鍵思想是有限多項式插值。

設 p > d 是素數，{0，... ，p1}模 p 的加法和乘法滿足實數上的標準恒等式。也就是說，數字{0，... ，p1}相對于這些操作形成一個有限域。這個字段用 Fp 表示。在下面處理定義在有限域上的多項式。這種多項式具有實數多項式所具有的所有代數性質。具體地說，一個單變量多項式在任意 d + 1點上的值唯一地決定了它在d 的 Fp 上的多項式。

設 m 是一個大整數。設 E1，... ，En 是 m 維 Fp 上 n 個向量的一個集合。該集合是固定的，并且獨立于 n 位數據庫x。假設服務器和用戶都知道該集合，在隱私信息檢索協議的預處理階段，每個(d + 1)上的服務器在 m 個變量中用相同程度的 d 多項式 f 表示數據 x。這種多項式的關鍵性質是對于[ n ]中的每個 i: f (Ei) = xi。為了保證這樣一個多項式 f 的存在，選擇 m 相對于 n 來說比較大。一般地，設置 m = O (n1/d)就足夠了。

假設用戶想要檢索數據庫的第 i 位，并且知道了向量 E1，... ，En 的集合。因此，用戶的目標是恢復 Ei 的多項式 f (由服務器持有)的值。顯然，用戶不能從任何服務器顯式地請求 f (Ei) 的值，因為這樣的請求會破壞協議的隱私性; 也就是說，一些服務器會知道用戶需要哪個數據位。相反，用戶間接地得到 f (Ei)的值，特別地，用戶在 Fp 上生成 m 維向量 P1，... ，Pd + 1的隨機集合，這樣:

每個向量 P 都是均勻隨機的，因此沒有提供關于 Ei 的信息;

任意次 d 多項式(包括多項式 f)在 P1，... ，Pd + 1的值決定了多項式在 Ei。

用戶向每個服務器發送一個向量 P1，... ，Pd + 1。然后，服務器在它們接收到的向量處計算多項式 f，并將它們獲得的值返回給用戶。用戶將值 f (P1)、 ... 、 f (Pd + 1)組合起來得到所需的值 f (Ei)。該協議是完全私有的，通信相當于將維數 m 的(d + 1)向量發送到服務器，并將一個值返回給用戶。

現代的隱私信息檢索

現代的隱私信息檢索方案不再基于多項式，其關鍵技術要素是一個具有限制交集的大集合族的設計。設 k 是一個小整數，它將 n 位消息編碼成碼字。這個構造包括兩個步驟: 第一個步驟是構造一個具有限制交集的集合族問題的簡化; 第二個步驟是期望集合族的代數構造。

步驟1：

C 是 F2線性映射。對于 Fn2中的任意兩個消息 x1，x2，有 C (x1 + x2) = C (x1) + C (x2) ，其中向量的和在每個坐標中被計算為模2;

解碼算法通過讀取已損壞的代碼字的某個 k 元組坐標并輸出這些坐標中值的異或(XOR)來進行。對于[ n ]中的 i，讓 Ei 表示一個二元 n 維向量，其唯一的非零坐標是 i。每個線性映射都允許一個組合描述。也就是說，對[ n ]中的每個 i 指定:

C (Ei)坐標的一組 Ti，設置為1。這些集合完全指定了編碼，因為對于任何消息 x，C (x) =C (Ei) ; 和一種碼字坐標的 k 大小子集族，在重構第 i 個消息位時可由譯碼算法讀取。必須滿足某些組合約束，這些限制的基本理由如下:

解碼必須是正確的，以避免編碼位被破壞。這意味著，對于[ n ]中的每一個 i，j 和其中的任意 k 集合，如果 i = j，則 STj 的大小必為奇數，否則為偶數;

譯碼算法的各個查詢的分布必須接近于均勻。這意味著對于[ n ]中的每一個 i，其中的 k 集合的并集相對于編碼坐標的數目必須是大的。

步驟2：

設計滿足這些約束條件的集合 Ti 和 Qi。這個結構是由幾何直覺支持的。考慮了基數 k 的有限域上的編碼坐標集和 m 維向量集之間的雙向影射。在 Fk 上的 m 維線性空間中，選擇集 Ti 作為某些平行超平面的并集，用基本代數來討論交點的大小。

計算型隱私信息檢索方案之所以具有吸引力，是因為它們避免了維護數據庫的復制副本的需要，并且不會對用戶隱私造成損害。

結論

近年來，隱私信息檢索已經成長為一個龐大而深入的領域，并與其他領域相連。隱私信息檢索主要涉及兩個方面，一方面是通信的復雜性，另一方面是，為了響應用戶查詢，服務器必須執行的計算量。