新的研究使用戶能夠在不透露查詢內容的情況下搜索信息，所采用的方法比現有同類技術快 30 倍。

搜索互聯網可以揭示用戶寧愿保密的信息。例如，當有人在網上查找醫療癥狀時，他們可以向谷歌、WebMD 等在線醫療數據庫以及這些公司的數百個廣告商和業務合作伙伴透露他們的健康狀況。

幾十年來，研究人員一直在精心設計技術，使用戶能夠私下從數據庫中搜索和檢索信息，但這些方法仍然太慢，無法在實踐中有效使用。

麻省理工學院的研究人員現已開發出一種私人信息檢索方案，該方案比其他同類方法快約 30 倍。他們的技術使用戶能夠在不向服務器透露他們的查詢的情況下搜索在線數據庫。此外，它由一個簡單的算法驅動，該算法比以前工作中更復雜的方法更容易實現。

他們的技術可以通過阻止消息傳遞應用程序知道用戶在說什么或他們在與誰交談來實現私人通信。它還可以用于在廣告服務器不了解用戶興趣的情況下獲取相關的在線廣告。

“這項工作實際上是為了讓用戶重新控制自己的數據。從長遠來看，我們希望瀏覽網頁就像瀏覽圖書館一樣私密。這項工作還沒有實現這一點，但它開始構建工具，讓我們在實踐中快速有效地完成這類事情，”計算機科學研究生和介紹該技術的論文的主要作者亞歷山德拉亨辛格說。

合著者包括麻省理工學院計算機科學研究生 Matthew Hong；Henry Corrigan-Gibbs，麻省理工學院電氣工程與計算機科學系（EECS）道格拉斯羅斯軟件技術職業發展教授，計算機科學與人工智能實驗室（CSAIL）成員；Sarah Meiklejohn，倫敦大學學院密碼學和安全教授，谷歌研究員；和作者 Vinod Vaikuntanathan，他是 EECS 教授和 CSAIL 的首席研究員。該研究將在 2023 年 USENIX 安全研討會上發表。 

保護隱私

個私人信息檢索方案是在 1990 年代開發的，部分由麻省理工學院的研究人員開發。這些技術使用戶能夠與擁有數據庫的遠程服務器通信，并在服務器不知道用戶正在閱讀什么的情況下從該數據庫讀取記錄。

為了保護隱私，這些技術迫使服務器接觸數據庫中的每一項，因此它無法判斷用戶正在搜索的條目。如果一個區域未被觸及，服務器將了解到客戶端對該項目不感興趣。但是，當可能有數百萬個數據庫條目時接觸每個項目會減慢查詢過程。

為了加快速度，麻省理工學院的研究人員開發了一種稱為 Simple PIR 的協議，在該協議中，服務器甚至在客戶端發送查詢之前就提前執行大部分底層加密工作。此預處理步驟生成一個數據結構，其中包含有關數據庫內容的壓縮信息，客戶端在發送查詢之前下載該數據結構。

從某種意義上說，這種數據結構就像是向客戶提示數據庫中有什么。

“一旦客戶端有了這個提示，它就可以進行無限數量的查詢，并且這些查詢在您發送的消息大小和您需要服務器完成的工作方面都會小得多。這就是使 Simple PIR 速度如此之快的原因，”Henzinger 解釋道。

但是提示的大小可能相對較大。例如，要查詢 1 GB 的數據庫，客戶端需要下載 124 MB 的提示。這增加了通信成本，這可能使該技術難以在現實世界的設備上實施。

為了減小提示的大小，研究人員開發了第二種技術，稱為 Double PIR，基本上涉及運行 Simple PIR 方案兩次。這會產生一個更緊湊的提示，它的大小對于任何數據庫都是固定的。

使用 Double PIR，1 GB 數據庫的提示僅為 16 MB。

“我們的 Double PIR 方案運行速度稍慢，但通信成本會低得多。對于某些應用程序，這將是一個理想的權衡，”Henzinger 說。

達到限速

他們通過將 Simple PIR 和 Double PIR 方案應用于客戶尋求審核有關網站的特定信息以確保該網站可以安全訪問的任務來測試它們。為了保護隱私，客戶不能透露正在審核的網站。

研究人員快的技術能夠在以每秒約 10 GB 的速度運行時成功地保護隱私。以前的方案只能達到每秒約 300 兆字節的吞吐量。

Corrigan-Gibbs 補充說，他們表明他們的方法接近私人信息檢索的理論速度限制——這幾乎是人們可以構建的快的方案，在該方案中，服務器會接觸數據庫中的每條記錄。

此外，他們的方法只需要一臺服務器，這比許多需要兩臺具有相同數據庫的獨立服務器的高性能技術要簡單得多。他們的方法優于這些更復雜的協議。

“一段時間以來，我一直在考慮這些方案，但我從沒想過以這種速度這可能成為可能。民間傳說任何單服務器方案都會非常慢。這項工作顛覆了整個概念，”Corrigan-Gibbs 說。

Henzinger 說，雖然研究人員已經證明他們可以更快地制定 PIR 方案，但在他們能夠將他們的技術部署到現實場景之前，還有很多工作要做。他們希望降低方案的通信成本，同時仍能實現高速。此外，他們希望調整他們的技術來處理更復雜的查詢，例如一般的 SQL 查詢，以及要求更高的應用程序，例如一般的維基百科搜索。從長遠來看，他們希望開發更好的技術來保護隱私，而無需服務器接觸每個數據庫項目。 

“我聽到人們斷言 PIR 永遠不會實用。但我絕不會做空技術。這是從這項工作中吸取的樂觀教訓。總有創新的方法，”Vaikuntanathan 說。

“這項工作大大改善了私人信息檢索的實際成本。雖然眾所周知，低帶寬 PIR 方案意味著公鑰加密，這通常比私鑰加密慢幾個數量級，但這項工作開發了一種巧妙的方法來彌合差距。這是通過巧妙地利用 Regev 的公鑰加密方案的特殊屬性來完成的，將絕大多數計算工作推到預計算步驟，在該步驟中服務器計算有關數據庫的簡短“提示”，” Technion（以色列理工學院）計算機科學教授 Yuval Ishai 說，他沒有參與這項研究。“他們的方法之所以特別吸引人，是因為同一提示可以被任意數量的客戶無限次使用。

這項工作部分由科學基金會、谷歌、Facebook、麻省理工學院的 Fintech@CSAIL 計劃、NSF 研究生研究獎學金、EECS 偉大教育者獎學金、美國國立衛生研究院、國防研究計劃局、 MIT-IBM Watson AI 實驗室、Analog Devices、Microsoft 和 Thornton Family Faculty Research Innovation Fellowship。