信息論中私密信息檢索問題綜述

劉 楠，姚昕羽

(1.東南大學(xué) 移動通信國家重點實驗室，江蘇 南京 210096；2.東南大學(xué) 信息科學(xué)與工程學(xué)院，江蘇 南京 210096)

0 引言

在這個日益數(shù)字化的時代,我們在瀏覽網(wǎng)頁、網(wǎng)上購物、在線社交、導(dǎo)航定位等的同時,越來越多的數(shù)字化個人信息流落于網(wǎng)絡(luò)的各個角落。如何能夠保護用戶的隱私已成為人們越來越關(guān)注的話題。

早在1998年，私密信息檢索問題(Private Information Retrieval,PIR)在計算科學(xué)領(lǐng)域便受到了廣泛的關(guān)注。此問題由Chor等人提出[1]：假設(shè)一個數(shù)據(jù)庫存有K條相互獨立的消息，W1,W2,…,WK，它們的長度都為L。一個用戶想通過檢索該數(shù)據(jù)庫以獲取一條消息的內(nèi)容。同時，該用戶不想自己的隱私被泄漏，即不想讓數(shù)據(jù)庫獲知具體哪一條信息被檢索。因此，用戶設(shè)計自己向數(shù)據(jù)庫發(fā)出的檢索請求，以達到下面兩個條件：

① 解碼條件：根據(jù)數(shù)據(jù)庫的回復(fù)，用戶可以無誤地解碼自己感興趣消息的內(nèi)容；

② 私密條件：數(shù)據(jù)庫從檢索請求中，對用戶感興趣消息的下標一無所知。

文獻[1]中指出，當只能從一個數(shù)據(jù)庫進行檢索時，滿足以上兩個條件的檢索請求只有一種，就是把所有K條消息都進行請求并下載?？梢?，為了保護自己的隱私，需要付出巨大的下載量浪費。

2016年，Sun和Jafar作為信息論研究的學(xué)者，對“最優(yōu)”的檢索請求產(chǎn)生了興趣，他們提出這樣一個問題[2]：在所有滿足解碼條件和單個數(shù)據(jù)庫私密條件的檢索請求中，哪種檢索請求方式的下載量最?。克麄冎灾魂P(guān)心下載量，而不關(guān)心檢索請求時上傳數(shù)據(jù)量的大小，是因為在信息論中，通常假設(shè)消息的長度很長，因此相比于下載量，上傳請求的大小可以忽略不計。文獻[2]利用信息論的工具完整地解出了私密檢索下載量的性能極限，并給出了達到此性能極限的最優(yōu)檢索方法，為人們對私密信息檢索問題的理解和方案設(shè)計提供了巨大的幫助。自2016年Sun和Jafar文章發(fā)布以來，私密信息檢索這個原本只在計算機科學(xué)領(lǐng)域活躍的研究內(nèi)容，在信息論領(lǐng)域也備受矚目，短短幾年中已有近100篇該方面的文章。這些論文對各種私密信息檢索場景進行了擴展和探究，提出了很多表現(xiàn)優(yōu)秀的私密檢索方案，得出了不少私密檢索的性能極限，對現(xiàn)實生活中用戶隱私保護提供了大量的理論指導(dǎo)。

本文首先給出傳統(tǒng)私密信息檢索問題的最小下載量及其證明理論方法。而后，將這幾年信息論私密信息檢索方面的論文進行歸類、闡述與總結(jié)。最后，指出私密信息檢索方向的未來發(fā)展趨勢和若干重要開放問題。

1 傳統(tǒng)PIR問題

1.1 最小下載量

圖1 傳統(tǒng)私密信息檢索問題Fig.1 Classical private information retrieval problem

1.2 最優(yōu)檢索請求

最優(yōu)的檢索請求，即下載總量最少的檢索請求，并不唯一[3]。Sun和Jafar在文獻[2]中提出的最優(yōu)檢索請求方法，采用了不同消息符號k項求和的形式,k=1,2,…,K。文獻[2]的檢索請求充分利用了兩種對稱性：① 消息的對稱性；② 數(shù)據(jù)庫的對稱性。消息的對稱性保證了用戶隱私的保密，數(shù)據(jù)庫的對稱性可以最大化重復(fù)利用那些下載的關(guān)于其他非感興趣消息的數(shù)據(jù)，這些非感興趣數(shù)據(jù)是為保護用戶隱私迷惑數(shù)據(jù)庫而下載的。

1.3 性能極限

PIR信息論問題的提出和完整解出[2]，引起信息論領(lǐng)域很多學(xué)者的極大興趣。他們開始更深入地探索該問題的其他變種，探求在更靈活、更實際場景中私密信息檢索的最優(yōu)方案。本文將研究方向歸為幾類進行介紹。

2 第一類變種問題：PIR中其他隱私保護和安全問題

這類問題探索的是PIR中滿足其他隱私保護需求和數(shù)據(jù)安全需求下的最優(yōu)檢索請求方案。具體來說，包括下面幾個問題。

2.1 數(shù)據(jù)庫共謀

數(shù)據(jù)庫共謀場景下的最優(yōu)檢索方案需要用到MDS碼。MDS碼可以把重復(fù)利用的非感興趣數(shù)據(jù)的相關(guān)性均勻擴展開來，使得合謀數(shù)據(jù)庫集合由于看到的非感興趣數(shù)據(jù)數(shù)目不多，感覺不到非感興趣數(shù)據(jù)的相關(guān)性，進而對于合謀數(shù)據(jù)庫集合來說，非感興趣數(shù)據(jù)和感興趣數(shù)據(jù)都是不相關(guān)的，這樣就達到了對隱私的保護。此種場景下的性能極限證明與傳統(tǒng)PIR問題證明步驟基本一致，迭代公式的第二步證明需要用到Han′s inequality[5]。在文獻[4]結(jié)論的基礎(chǔ)上，文獻[6]將合謀方式的對稱性去掉，給出了任意合謀模式下的最小下載量和最優(yōu)檢索請求方案。

2.2 魯棒私密信息檢索

2.3 拜占庭私密信息檢索

2.4 消息安全

PIR與以往通信安全問題的不同之處在于，它考慮的是消息下標保密，而不是消息內(nèi)容保密。那么，如果在這類問題中也加入消息內(nèi)容需對不授權(quán)用戶進行保密的需求呢？這一類問題中可以進一步按不授權(quán)用戶的種類進行分類。

2.4.1 對稱私密信息檢索

2.4.2 外在竊聽者

上面介紹的幾種擴展都已求得最優(yōu)檢索方案和對應(yīng)的最小下載量。因此，人們還探索了它們的組合問題，例如魯棒加數(shù)據(jù)庫共謀[4]、拜占庭加數(shù)據(jù)庫共謀[7]、拜占庭加對稱PIR[11]、外在竊聽者加數(shù)據(jù)庫共謀[10]以及對稱PIR加數(shù)據(jù)庫共謀加拜占庭[12]等。第一類變種問題的共同特點就是最優(yōu)檢索方案和對應(yīng)的最小下載量基本全部可以完整解出。因此，人們對這一類的問題有著深刻透徹的理解。

3 第二類變種問題：數(shù)據(jù)庫存儲空間受限

傳統(tǒng)PIR中，假設(shè)每個數(shù)據(jù)庫都完整地存有K個消息。這對數(shù)據(jù)庫的存儲空間要求很高。因此，人們開始研究數(shù)據(jù)庫存儲空間受限情況。第二類變種問題中又分以下4類。

3.1 分布式存儲系統(tǒng)中的PIR

如果每個數(shù)據(jù)庫只是分布式存儲系統(tǒng)中的一個節(jié)點或者硬盤，那么每個數(shù)據(jù)庫無需存儲全部K條消息。但分布式存儲系統(tǒng)的存儲方案，要考慮下面兩點需求：① 數(shù)據(jù)冗余需求,即在某些硬盤壞掉的情況下，剩余硬盤仍可以恢復(fù)全部數(shù)據(jù)；② 通信少的需求,即當產(chǎn)生新的硬盤來替代壞掉的硬盤保持冗余時，新硬盤與舊的可用硬盤之間的通信量要盡可能地少[13]。

雖然MDS碼在數(shù)據(jù)冗余方面表現(xiàn)優(yōu)秀，它在滿足通信量少方面卻表現(xiàn)不佳[13]。因此，在MDS編碼PIR問題研究成功后，人們開始探索非MDS碼編碼的數(shù)據(jù)庫中，PIR的最小下載量是多少。 文獻[15-19]研究了這類問題，并給出了若干非MDS碼能達到MDS碼PIR性能的條件。廣泛的線性碼下PIR的最小下載量仍是一個開放的問題。

3.2 數(shù)據(jù)庫存儲空間和PIR最小下載量的折中

通過對分布式存儲系統(tǒng)中PIR的研究，人們發(fā)現(xiàn)，數(shù)據(jù)庫存儲的數(shù)據(jù)越多，PIR的最小下載量越小。因此，數(shù)據(jù)庫存儲空間大小和PIR最小下載量存在著一個折中。假設(shè)數(shù)據(jù)庫的存儲方式可以任意設(shè)計，那么最優(yōu)折中能達到多少呢？

如果不做數(shù)據(jù)庫存儲不編碼消息這一假設(shè)，那探求最優(yōu)折中變得更加困難。文獻[25]指出把不同消息編碼在一起可以超越MDS碼的存儲空間和下載量折中，文獻[26]提出了把MDS編碼方案和不編碼存儲方案結(jié)合可以得到比MDS編碼和不編碼存儲更優(yōu)的折中，而文獻[27]則探索了數(shù)據(jù)庫存儲非線性編碼較線性編碼的優(yōu)越性，即非線性編碼能夠提供更優(yōu)的折中。在數(shù)據(jù)庫存儲可以任意設(shè)計情況下的最優(yōu)折中，至今仍是一個開放問題。

3.3 數(shù)據(jù)庫存儲部分完整的消息

前面兩類問題中，假設(shè)數(shù)據(jù)庫存儲每個消息的編碼或非編碼的一部分。如果數(shù)據(jù)庫存儲空間大小受限，它也可以選擇存儲K條消息中的若干條完整的消息。文獻[28]研究了每條消息都存在兩個數(shù)據(jù)庫上的情況，而文獻[29]則研究了每個數(shù)據(jù)庫能存兩條消息的情況。這一類問題，除特殊情況外，最小下載量仍是開放問題。

把第一類變種問題和第二類變種問題結(jié)合到一起，也有不少論文的研究，例如分布式存儲PIR加數(shù)據(jù)庫共謀[30-36]、分布式存儲加魯棒PIR[37]、分布式存儲加對稱PIR加數(shù)據(jù)庫共謀[38]、分布式存儲加拜占庭加魯棒PIR加數(shù)據(jù)庫共謀[39]等。由于分布式存儲系統(tǒng)下的PIR問題的復(fù)雜性，這些結(jié)合問題也基本都是開放問題。

4 第三類變種問題：用戶有邊信息的PIR

如果用戶在不知道自己的檢索需求之前，能夠得到一些關(guān)于消息的邊信息，此時這些邊信息對PIR能有多少幫助？這是這一類變種問題研究并希望回答的。第三類變種問題中又分為兩小類：

4.1 帶存儲功能的用戶

如果用戶有一定的存儲空間，可以在知道自己檢索需求之前先存一些關(guān)于消息的比特，那么這些預(yù)存比特對PIR有著什么樣的幫助？這個問題的解答與預(yù)存比特下標是否為數(shù)據(jù)庫所知有很大的關(guān)系。文獻[40]指出，如果預(yù)存比特的下標是數(shù)據(jù)庫知道的，那么最優(yōu)方案為，平均預(yù)存每個消息的一部分，消息的剩余部分用文獻[2]中最優(yōu)檢索請求來進行檢索。也就是說，如果數(shù)據(jù)庫知道預(yù)存內(nèi)容的下標，那預(yù)存對用戶來說幫助很?。撼祟A(yù)存的部分無需下載外，沒有額外的幫助。針對文獻[40]這個比較悲觀的結(jié)論，文獻[41-42]研究了另一個極端，即數(shù)據(jù)庫對預(yù)存內(nèi)容的下標一無所知的情況。由于問題的復(fù)雜性，它們額外做了一個假設(shè)，就是預(yù)存的只能是一些非編碼比特。文獻[42]提出的存儲方案是均勻存儲每個消息的部分比特，檢索請求則再次用到了文獻[2]中提出的消息對稱性及數(shù)據(jù)庫對稱性。不同的是，由于數(shù)據(jù)庫不知道預(yù)存內(nèi)容，預(yù)存的非感興趣數(shù)據(jù)可以優(yōu)先拿出來單獨或者以k項和的形式在每個數(shù)據(jù)庫重復(fù)利用。文獻[42]證明，在用戶存儲空間較小或較大，或者只有3個消息的時候，其提出的存儲與檢索請求方案是最優(yōu)的。其他情況下，文獻[42]刻畫了最小下載量上下界的差距。文獻[43]在數(shù)據(jù)庫完全知道[40]和完全不知道[41-42]的兩種假設(shè)下做了一個折中，它認為從哪個數(shù)據(jù)庫得到的預(yù)存比特，那個數(shù)據(jù)庫就知道這些預(yù)存比特下標，而其他數(shù)據(jù)庫對這部分預(yù)存內(nèi)容的下標一無所知。在這種情況下，文獻[43]得出的結(jié)論與文獻[42]類似，即在用戶存儲空間較小或較大，或者只有3個消息的時候，最優(yōu)存儲與檢索請求方案已找到。其他情況下，文獻[44]給出了最小下載量上下界的差距。

4.2 用戶知道某些消息的完整內(nèi)容

用戶通過其他用戶或者其他傳輸，得知了某些消息的完整內(nèi)容或者某些消息線性組合的內(nèi)容，這些內(nèi)容被稱為邊信息。這些邊信息雖然不是用戶感興趣的消息，它們能否幫助用戶進行PIR呢？一系列研究指出，邊信息分為兩種情況，一種是邊信息是用戶不感興趣的某些消息，另一種是邊信息是某些消息的線性組合。此類問題還需考慮的一個關(guān)鍵在于是否需要保證邊信息的下標不被數(shù)據(jù)庫知道。如果邊信息希望被重復(fù)利用，那么保護邊信息的隱私對于用戶來說也很重要。如果用戶只用邊信息一次，那么邊信息的下標在檢索請求中被泄漏也沒有關(guān)系。因此，此類問題被分為4種情況：① 保護消息邊信息的下標[44-45]；② 不保護消息和邊信息的下標[46]；③ 保護線性組合邊信息的下標[47-48]；④ 不保護線性組合邊信息的下標[48-49]。目前已知最優(yōu)解的情況是①及①②③的單數(shù)據(jù)庫場景。其他的情況還屬于開放性問題。

5 其他變種問題和性能指標

還有一些有意思的PIR變種問題，每個問題研究的文章較少。比如多消息PIR，即用戶請求的消息多于一個，一個消息一個消息的私密請求是可以的，但是能否做到更好？文獻[50]研究了此種情形，并在請求消息數(shù)多于全體消息數(shù)一半時，尋求到了最優(yōu)檢索請求方案。再比如數(shù)據(jù)庫流量非對稱的PIR[51]，如果每個數(shù)據(jù)庫下載量占總下載量的比例給定且不相等，那么文獻[2]中檢索請求的數(shù)據(jù)庫對稱性就必須被破壞，此時，最優(yōu)檢索請求是什么？文獻[51]在消息數(shù)等于2或3時，找到了該問題的完整解，然而其他情況還屬于開放問題。再比如數(shù)據(jù)庫到用戶的通信信道并不是沒有噪聲的完美信道，文獻[52-53]在這方面做了一些嘗試，但是目前對此種問題的理解還遠遠不夠。

傳統(tǒng)PIR考慮的性能指標是滿足解碼條件和私密條件下的最小下載量，但是其實PIR問題還有許多其他人們關(guān)心的性能指標，例如：① 隱私條件放松后，隱私泄漏量和最小下載量的折中[54-55]；② 最小的消息長度[3，56-61]，該值小說明消息需要分塊的數(shù)量少、編碼操作的復(fù)雜度低；③ 上傳代價最小[3]；④ 數(shù)據(jù)庫計算復(fù)雜度低[62-63]；⑤ 數(shù)據(jù)庫讀取復(fù)雜度低[64]。

6 結(jié)束語

信息論中私密信息檢索問題與一般信息論問題不同，一般信息論問題關(guān)心的是消息內(nèi)容的傳輸、保密等，而私密信息檢索問題關(guān)心消息下標的保密。很多私密信息檢索問題都可以使用線性碼、信息論工具和方法等推導(dǎo)出工整的最優(yōu)解，這大大增強了人們對隱私保護的理解，提供了許多有效的隱私保護方法。信息檢索只是隱私保護的一個方面，把私密信息檢索問題的隱私保護框架放入更多的通信實際問題中，例如文獻[65-66]，是未來一個很有前景和應(yīng)用價值的研究方向。