互聯(lián)網(wǎng)的普及意味著有大量的在線數(shù)據(jù)和檢索信息不可或缺的資源, 在某種程度上，也對(duì)用戶(hù)隱私構(gòu)成了重大風(fēng)險(xiǎn)。事實(shí)上，在用戶(hù)意圖保密的情況下，用戶(hù)通常對(duì)訪問(wèn)公共數(shù)據(jù)持謹(jǐn)慎態(tài)度。例如，公司可能希望不透露自己身份來(lái)搜索某些專(zhuān)利。

那么，如何在用戶(hù)進(jìn)行信息檢索時(shí)保護(hù)用戶(hù)的隱私呢？這或許會(huì)涉及到一種名為隱私信息檢索的技術(shù)。

什么是隱私信息檢索？

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

在1995年，業(yè)界提出了 隱私信息檢索方案，在該方案的協(xié)議中，用戶(hù)查詢(xún)保存數(shù)據(jù)庫(kù)的每個(gè)服務(wù)器，確保每個(gè)單獨(dú)的服務(wù)器得不到關(guān)于用戶(hù)感興趣項(xiàng)的標(biāo)識(shí)信息。

隱私信息檢索方案與一類(lèi)特殊的糾錯(cuò)碼密切相關(guān)，這類(lèi)糾錯(cuò)碼被稱(chēng)為“局部可解碼碼”，它們本身就是人們感興趣的對(duì)象。糾錯(cuò)碼有助于確保信息在嘈雜信道上的可靠傳輸，以及在取設(shè)備容易出錯(cuò)的介質(zhì)上可靠地存儲(chǔ)信息。這種編碼允許人們向消息中添加冗余或位字符串，并將其編碼成更長(zhǎng)的位字符串，即使一定比例的位字符串被破壞，消息仍然可以恢復(fù)。在糾錯(cuò)碼的典型應(yīng)用中，消息首先被分成小塊，然后每個(gè)小塊被分別編碼。這種編碼策略允許對(duì)信息進(jìn)行有效的隨機(jī)訪問(wèn)檢索，因?yàn)橹恍枰獙?duì)感興趣的部分?jǐn)?shù)據(jù)進(jìn)行解碼。不幸的是，這種策略產(chǎn)生了較差的噪音恢復(fù)能力，因?yàn)?，即使是一個(gè)單一的塊完全損壞，一些信息就會(huì)丟失。

鑒于這種局限性，似乎更可取的做法是將整個(gè)信息編碼成一個(gè)前向糾錯(cuò)的單一碼字。這種解決方案提高了對(duì)噪聲的魯棒性，但是很難令人滿(mǎn)意，因?yàn)樾枰榭凑麄€(gè)碼字，以便恢復(fù)消息的任何特定位。這種解碼復(fù)雜度對(duì)于當(dāng)今的大規(guī)模數(shù)據(jù)集來(lái)說(shuō)是不可能的。

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

初識(shí)隱私信息檢索

如果將數(shù)據(jù)建模為 n 位字符串 X，該字符串只在少量服務(wù)器 S1，... ，Sk 之間復(fù)制。用戶(hù)持有一個(gè)索引 i (介于1和 n 之間的整數(shù)) ，并對(duì)獲取位 Xi 的值感興趣。為了實(shí)現(xiàn)這個(gè)目標(biāo)，用戶(hù)隨機(jī)查詢(xún)每個(gè)服務(wù)器，并接收響應(yīng)，從中計(jì)算所需的位 Xi。對(duì)每個(gè)服務(wù)器的查詢(xún)是獨(dú)立于 i 分布的，因此，每個(gè)服務(wù)器不會(huì)獲得關(guān)于用戶(hù)需要什么的信息。

用戶(hù)的查詢(xún)不一定是對(duì)特定單數(shù)據(jù)集的請(qǐng)求，它們指定由服務(wù)器計(jì)算的函數(shù); 例如，一個(gè)查詢(xún)可能指定一組介于1和 n 之間的索引，而服務(wù)器的響應(yīng)可能是存儲(chǔ)在這些索引的數(shù)據(jù)位 XOR。

隱私信息檢索方案的主要參數(shù)是通信復(fù)雜度，或者說(shuō)是度量用戶(hù)和服務(wù)器之間通信的總比特?cái)?shù)的函數(shù)。目前最有效的雙服務(wù)器隱私信息檢索協(xié)議的通信復(fù)雜度為 O (n的1/3次方)。然而，涉及三個(gè)或更多服務(wù)器的隱私信息檢索方案已經(jīng)得到了改進(jìn)。

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

驗(yàn)證協(xié)議是私有的，也非常簡(jiǎn)單，因?yàn)閷?duì)于[ k ]中的每個(gè) j，查詢(xún) Qj 均勻地分布在碼字坐標(biāo)集上，總的通信量由 k (logN + 1)給出。

早期的隱私信息檢索

隱私信息檢索方案的目標(biāo)是通過(guò)提供一個(gè)簡(jiǎn)單的(d + 1)服務(wù)器方案，使用 O (n的1/d次方)通信來(lái)訪問(wèn) n 位數(shù)據(jù)，這個(gè)方案背后的關(guān)鍵思想是有限多項(xiàng)式插值。

設(shè) p > d 是素?cái)?shù)，{0，... ，p1}模 p 的加法和乘法滿(mǎn)足實(shí)數(shù)上的標(biāo)準(zhǔn)恒等式。也就是說(shuō)，數(shù)字{0，... ，p1}相對(duì)于這些操作形成一個(gè)有限域。這個(gè)字段用 Fp 表示。在下面處理定義在有限域上的多項(xiàng)式。這種多項(xiàng)式具有實(shí)數(shù)多項(xiàng)式所具有的所有代數(shù)性質(zhì)。具體地說(shuō)，一個(gè)單變量多項(xiàng)式在任意 d + 1點(diǎn)上的值唯一地決定了它在d 的 Fp 上的多項(xiàng)式。

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

假設(shè)用戶(hù)想要檢索數(shù)據(jù)庫(kù)的第 i 位，并且知道了向量 E1，... ，En 的集合。因此，用戶(hù)的目標(biāo)是恢復(fù) Ei 的多項(xiàng)式 f (由服務(wù)器持有)的值。顯然，用戶(hù)不能從任何服務(wù)器顯式地請(qǐng)求 f (Ei) 的值，因?yàn)檫@樣的請(qǐng)求會(huì)破壞協(xié)議的隱私性; 也就是說(shuō)，一些服務(wù)器會(huì)知道用戶(hù)需要哪個(gè)數(shù)據(jù)位。相反，用戶(hù)間接地得到 f (Ei)的值，特別地，用戶(hù)在 Fp 上生成 m 維向量 P1，... ，Pd + 1的隨機(jī)集合，這樣:

每個(gè)向量 P 都是均勻隨機(jī)的，因此沒(méi)有提供關(guān)于 Ei 的信息;

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

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

現(xiàn)代的隱私信息檢索

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

步驟1：

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

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

C (Ei)坐標(biāo)的一組 Ti，設(shè)置為1。這些集合完全指定了編碼，因?yàn)閷?duì)于任何消息 x，C (x) =C (Ei) ; 和一種碼字坐標(biāo)的 k 大小子集族，在重構(gòu)第 i 個(gè)消息位時(shí)可由譯碼算法讀取。必須滿(mǎn)足某些組合約束，這些限制的基本理由如下:

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

譯碼算法的各個(gè)查詢(xún)的分布必須接近于均勻。這意味著對(duì)于[ n ]中的每一個(gè) i，其中的 k 集合的并集相對(duì)于編碼坐標(biāo)的數(shù)目必須是大的。

步驟2：

設(shè)計(jì)滿(mǎn)足這些約束條件的集合 Ti 和 Qi。這個(gè)結(jié)構(gòu)是由幾何直覺(jué)支持的?？紤]了基數(shù) k 的有限域上的編碼坐標(biāo)集和 m 維向量集之間的雙向影射。在 Fk 上的 m 維線性空間中，選擇集 Ti 作為某些平行超平面的并集，用基本代數(shù)來(lái)討論交點(diǎn)的大小。

計(jì)算型隱私信息檢索方案之所以具有吸引力，是因?yàn)樗鼈儽苊饬司S護(hù)數(shù)據(jù)庫(kù)的復(fù)制副本的需要，并且不會(huì)對(duì)用戶(hù)隱私造成損害。

結(jié)論

近年來(lái)，隱私信息檢索已經(jīng)成長(zhǎng)為一個(gè)龐大而深入的領(lǐng)域，并與其他領(lǐng)域相連。隱私信息檢索主要涉及兩個(gè)方面，一方面是通信的復(fù)雜性，另一方面是，為了響應(yīng)用戶(hù)查詢(xún)，服務(wù)器必須執(zhí)行的計(jì)算量。