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

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

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

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

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

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

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

保護隱私

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

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

為了加快速度，麻省理工學(xué)院的研究人員開發(fā)了一種稱為 Simple PIR 的協(xié)議，在該協(xié)議中，服務(wù)器甚至在客戶端發(fā)送查詢之前就提前執(zhí)行大部分底層加密工作。此預(yù)處理步驟生成一個數(shù)據(jù)結(jié)構(gòu)，其中包含有關(guān)數(shù)據(jù)庫內(nèi)容的壓縮信息，客戶端在發(fā)送查詢之前下載該數(shù)據(jù)結(jié)構(gòu)。

從某種意義上說，這種數(shù)據(jù)結(jié)構(gòu)就像是向客戶提示數(shù)據(jù)庫中有什么。

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

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

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

使用 Double PIR，1 GB 數(shù)據(jù)庫的提示僅為 16 MB。

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

達(dá)到限速

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

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

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

此外，他們的方法只需要一臺服務(wù)器，這比許多需要兩臺具有相同數(shù)據(jù)庫的獨立服務(wù)器的高性能技術(shù)要簡單得多。他們的方法優(yōu)于這些更復(fù)雜的協(xié)議。

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

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

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

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

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