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

劉 楠，姚昕羽

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

0 引言

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

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

① 解碼條件：根據數據庫的回復，用戶可以無誤地解碼自己感興趣消息的內容；

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

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

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

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

1 傳統PIR問題

1.1 最小下載量

圖1 傳統私密信息檢索問題Fig.1 Classical private information retrieval problem

1.2 最優檢索請求

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

1.3 性能極限

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

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

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

2.1 數據庫共謀

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

2.2 魯棒私密信息檢索

2.3 拜占庭私密信息檢索

2.4 消息安全

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

2.4.1 對稱私密信息檢索

2.4.2 外在竊聽者

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

3 第二類變種問題：數據庫存儲空間受限

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

3.1 分布式存儲系統中的PIR

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

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

3.2 數據庫存儲空間和PIR最小下載量的折中

通過對分布式存儲系統中PIR的研究，人們發現，數據庫存儲的數據越多，PIR的最小下載量越小。因此，數據庫存儲空間大小和PIR最小下載量存在著一個折中。假設數據庫的存儲方式可以任意設計，那么最優折中能達到多少呢？

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

3.3 數據庫存儲部分完整的消息

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

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

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

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

4.1 帶存儲功能的用戶

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

4.2 用戶知道某些消息的完整內容

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

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

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

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

6 結束語

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