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

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

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

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

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

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

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

保護(hù)隱私

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

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

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

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

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

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

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

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

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

達(dá)到限速

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

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

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

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

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

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

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

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

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