建站
咨詢
售后
建站咨詢
新聞中心
互聯(lián)網(wǎng)的普及意味著有大量的在線數(shù)據(jù)和檢索信息不可或缺的資源, 在某種程度上，也對用戶隱私構(gòu)成了重大風(fēng)險。事實上，在用戶意圖保密的情況下，用戶通常對訪問公共數(shù)據(jù)持謹慎態(tài)度。例如，公司可能希望不透露自己身份來搜索某些專利。
那么，如何在用戶進行信息檢索時保護用戶的隱私呢？這或許會涉及到一種名為隱私信息檢索的技術(shù)。
什么是隱私信息檢索？
隱私信息檢索是一種加密協(xié)議，旨在保障數(shù)據(jù)使用者的私隱，允許客戶端從公共數(shù)據(jù)庫中檢索記錄，同時向數(shù)據(jù)所有者隱藏檢索記錄的身份。實際上，檢索數(shù)據(jù)而不向數(shù)據(jù)所有者透露其身份的可能性幾乎為零。當然，有一個簡單的解決方案: 當用戶需要單個數(shù)據(jù)時，可以要求獲得整個數(shù)據(jù)庫的副本。然而，這種解決方案涉及了巨大的通信開銷，可能是不可接受的。對于那些希望完全保護自己隱私的用戶，這種簡單的解決方案是最佳的。
在1995年，業(yè)界提出了 隱私信息檢索方案，在該方案的協(xié)議中，用戶查詢保存數(shù)據(jù)庫的每個服務(wù)器，確保每個單獨的服務(wù)器得不到關(guān)于用戶感興趣項的標識信息。
隱私信息檢索方案與一類特殊的糾錯碼密切相關(guān)，這類糾錯碼被稱為“局部可解碼碼”，它們本身就是人們感興趣的對象。糾錯碼有助于確保信息在嘈雜信道上的可靠傳輸，以及在取設(shè)備容易出錯的介質(zhì)上可靠地存儲信息。這種編碼允許人們向消息中添加冗余或位字符串，并將其編碼成更長的位字符串，即使一定比例的位字符串被破壞，消息仍然可以恢復(fù)。在糾錯碼的典型應(yīng)用中，消息首先被分成小塊，然后每個小塊被分別編碼。這種編碼策略允許對信息進行有效的隨機訪問檢索，因為只需要對感興趣的部分數(shù)據(jù)進行解碼。不幸的是，這種策略產(chǎn)生了較差的噪音恢復(fù)能力，因為，即使是一個單一的塊完全損壞，一些信息就會丟失。
鑒于這種局限性，似乎更可取的做法是將整個信息編碼成一個前向糾錯的單一碼字。這種解決方案提高了對噪聲的魯棒性，但是很難令人滿意，因為需要查看整個碼字，以便恢復(fù)消息的任何特定位。這種解碼復(fù)雜度對于當今的大規(guī)模數(shù)據(jù)集來說是不可能的。
隱私信息檢索方案提供了有效的隨機存取檢索和高噪聲恢復(fù)能力，允許通過只查看少量隨機選擇的碼字比特就可以對任意比特的信息進行可靠的重建。
初識隱私信息檢索
如果將數(shù)據(jù)建模為 n 位字符串 X，該字符串只在少量服務(wù)器 S1，... ，Sk 之間復(fù)制。用戶持有一個索引 i (介于1和 n 之間的整數(shù)) ，并對獲取位 Xi 的值感興趣。為了實現(xiàn)這個目標，用戶隨機查詢每個服務(wù)器，并接收響應(yīng)，從中計算所需的位 Xi。對每個服務(wù)器的查詢是獨立于 i 分布的，因此，每個服務(wù)器不會獲得關(guān)于用戶需要什么的信息。
用戶的查詢不一定是對特定單數(shù)據(jù)集的請求，它們指定由服務(wù)器計算的函數(shù); 例如，一個查詢可能指定一組介于1和 n 之間的索引，而服務(wù)器的響應(yīng)可能是存儲在這些索引的數(shù)據(jù)位 XOR。
隱私信息檢索方案的主要參數(shù)是通信復(fù)雜度，或者說是度量用戶和服務(wù)器之間通信的總比特數(shù)的函數(shù)。目前最有效的雙服務(wù)器隱私信息檢索協(xié)議的通信復(fù)雜度為 O (n的1/3次方)。然而，涉及三個或更多服務(wù)器的隱私信息檢索方案已經(jīng)得到了改進。
Hadamard 編碼允許以非常大的代碼長度為代價，超快速地恢復(fù)消息位。例如，給定一個有10%損壞的編碼，只讀取兩個代碼位就能恢復(fù)消息的任何位，概率為80%。這意味著可以從許多不同的碼字比特的 k 元組中恢復(fù)消息的每個比特 Xi。因此，解碼器的每個查詢的分布必須在一定程度上接近于編碼位上的均勻分布。
驗證協(xié)議是私有的，也非常簡單，因為對于[ k ]中的每個 j，查詢 Qj 均勻地分布在碼字坐標集上，總的通信量由 k (logN + 1)給出。
早期的隱私信息檢索
隱私信息檢索方案的目標是通過提供一個簡單的(d + 1)服務(wù)器方案，使用 O (n的1/d次方)通信來訪問 n 位數(shù)據(jù)，這個方案背后的關(guān)鍵思想是有限多項式插值。
設(shè) p > d 是素數(shù)，{0，... ，p1}模 p 的加法和乘法滿足實數(shù)上的標準恒等式。也就是說，數(shù)字{0，... ，p1}相對于這些操作形成一個有限域。這個字段用 Fp 表示。在下面處理定義在有限域上的多項式。這種多項式具有實數(shù)多項式所具有的所有代數(shù)性質(zhì)。具體地說，一個單變量多項式在任意 d + 1點上的值唯一地決定了它在d 的 Fp 上的多項式。
設(shè) m 是一個大整數(shù)。設(shè) E1，... ，En 是 m 維 Fp 上 n 個向量的一個集合。該集合是固定的，并且獨立于 n 位數(shù)據(jù)庫x。假設(shè)服務(wù)器和用戶都知道該集合，在隱私信息檢索協(xié)議的預(yù)處理階段，每個(d + 1)上的服務(wù)器在 m 個變量中用相同程度的 d 多項式 f 表示數(shù)據(jù) x。這種多項式的關(guān)鍵性質(zhì)是對于[ n ]中的每個 i: f (Ei) = xi。為了保證這樣一個多項式 f 的存在，選擇 m 相對于 n 來說比較大。一般地，設(shè)置 m = O (n1/d)就足夠了。
假設(shè)用戶想要檢索數(shù)據(jù)庫的第 i 位，并且知道了向量 E1，... ，En 的集合。因此，用戶的目標是恢復(fù) Ei 的多項式 f (由服務(wù)器持有)的值。顯然，用戶不能從任何服務(wù)器顯式地請求 f (Ei) 的值，因為這樣的請求會破壞協(xié)議的隱私性; 也就是說，一些服務(wù)器會知道用戶需要哪個數(shù)據(jù)位。相反，用戶間接地得到 f (Ei)的值，特別地，用戶在 Fp 上生成 m 維向量 P1，... ，Pd + 1的隨機集合，這樣:
每個向量 P 都是均勻隨機的，因此沒有提供關(guān)于 Ei 的信息;
任意次 d 多項式(包括多項式 f)在 P1，... ，Pd + 1的值決定了多項式在 Ei。
用戶向每個服務(wù)器發(fā)送一個向量 P1，... ，Pd + 1。然后，服務(wù)器在它們接收到的向量處計算多項式 f，并將它們獲得的值返回給用戶。用戶將值 f (P1)、 ... 、 f (Pd + 1)組合起來得到所需的值 f (Ei)。該協(xié)議是完全私有的，通信相當于將維數(shù) m 的(d + 1)向量發(fā)送到服務(wù)器，并將一個值返回給用戶。
現(xiàn)代的隱私信息檢索
現(xiàn)代的隱私信息檢索方案不再基于多項式，其關(guān)鍵技術(shù)要素是一個具有限制交集的大集合族的設(shè)計。設(shè) k 是一個小整數(shù)，它將 n 位消息編碼成碼字。這個構(gòu)造包括兩個步驟: 第一個步驟是構(gòu)造一個具有限制交集的集合族問題的簡化; 第二個步驟是期望集合族的代數(shù)構(gòu)造。
步驟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，設(shè)置為1。這些集合完全指定了編碼，因為對于任何消息 x，C (x) =C (Ei) ; 和一種碼字坐標的 k 大小子集族，在重構(gòu)第 i 個消息位時可由譯碼算法讀取。必須滿足某些組合約束，這些限制的基本理由如下:
解碼必須是正確的，以避免編碼位被破壞。這意味著，對于[ n ]中的每一個 i，j 和其中的任意 k 集合，如果 i = j，則 STj 的大小必為奇數(shù)，否則為偶數(shù);
譯碼算法的各個查詢的分布必須接近于均勻。這意味著對于[ n ]中的每一個 i，其中的 k 集合的并集相對于編碼坐標的數(shù)目必須是大的。
步驟2：
設(shè)計滿足這些約束條件的集合 Ti 和 Qi。這個結(jié)構(gòu)是由幾何直覺支持的?？紤]了基數(shù) k 的有限域上的編碼坐標集和 m 維向量集之間的雙向影射。在 Fk 上的 m 維線性空間中，選擇集 Ti 作為某些平行超平面的并集，用基本代數(shù)來討論交點的大小。
計算型隱私信息檢索方案之所以具有吸引力，是因為它們避免了維護數(shù)據(jù)庫的復(fù)制副本的需要，并且不會對用戶隱私造成損害。
結(jié)論
近年來，隱私信息檢索已經(jīng)成長為一個龐大而深入的領(lǐng)域，并與其他領(lǐng)域相連。隱私信息檢索主要涉及兩個方面，一方面是通信的復(fù)雜性，另一方面是，為了響應(yīng)用戶查詢，服務(wù)器必須執(zhí)行的計算量。
分享標題：隱私保護之隱私信息檢索
文章出自：http://m.5511xx.com/article/dhioops.html
