我們都知道要小心對待我們在網上分享的細節信息，其實我們搜尋的内容也可能會暴露信息。如搜索駕駛路線，我們的位置就會變得極容易猜到；在大量被洩露的數據中查找密碼，我們就面臨自己洩露密碼的風險。
這些情況引出了密碼學領域的一個關鍵問題：如何從公共數據庫中提取信息，又不暴露訪問内容的任何信息？這就相當于從圖書館借了一本書，而圖書管理員不知道是哪一本書。
美國得克薩斯大學奧斯汀分校的密碼學家 David Wu 表示，制定一種解決這個問題的策略（即所謂的私密信息檢索）是 " 許多保護隐私的應用程序中一種非常有用的基本模塊 "。
自 20 世紀 90 年代以來，研究人員一直在努力解決這個問題——改進私密訪問數據庫的策略。一個主要的目标（對于大型數據庫來說仍然不可能實現）相當于私密谷歌搜索，即你可以匿名篩選一大堆數據，無需進行任何繁重的計算操作。
現在，三位研究人員精心設計出一種私密信息檢索技術，并在此基礎上制定了一種更通用的隐私策略。這項研究在今年 6 月的年度計算理論研讨會上獲得了最佳論文獎，它掃除了通往真正私密的搜索道路上的一大理論上的障礙。
麻省理工學院的密碼學家 Vinod Vaikuntanathan 表示：" 這是裏程碑式的重大成果。"
私密數據庫訪問的問題在 20 世紀 90 年代形成。起初，研究人員以爲唯一的解決辦法是在每次搜索時掃描整個數據庫，這就好比檢索你要找的書時，圖書管理員把每個書架都翻遍一樣。畢竟，如果搜索跳過了任何部分，圖書管理員就會知道你要找的書不在圖書館的那個對應區。
規模比較小時 ，這種方法的效果足夠好，但是随着數據庫日益龐大，掃描數據庫所需的時間至少會成比例地增長。當從更大的數據庫中讀取時（互聯網是個龐大的數據庫），這個過程就變得非常低效。
在 21 世紀初，研究人員開始覺得他們可以通過 " 預處理 " 數據庫來避開全面掃描這個障礙。粗略地說，這意味着将整個數據庫編碼爲一個特殊的結構，這樣服務器就可以通過讀取該結構的僅僅一小部分來回答查詢。從理論上講，足夠仔細的預處理可能意味着，一台托管信息的服務器隻需要經曆一次這個過程，允許所有未來的用戶無需花更大的精力就可以私密獲取信息。
2017 年，兩組研究人員編寫出首批可以進行這種私密信息檢索的程序，但他們無法證明這些程序是安全的。（密碼學家通過證明破解一個系統就像解決某個難題一樣困難來證明系統的安全性。研究人員無法将其與标準的難題進行比較。）
左起：Wei-Kai Lin、Ethan Mook 和 Daniel Wichsawmg 設計了一種新方法，用于私密搜索大型數據庫
在他們研究的方法中，數據庫中的信息可以轉換成一個數學表達式，服務器可以對其進行計算以提取信息。論文作者認爲，可以使這個評估過程更有效。他們嘗試了 2011 年的一個想法，當時其他研究人員發現了一種方法，可以通過預處理來快速評估這樣一種表達式，創建特殊的緊湊值表，以便略過正常的評估步驟。
這種方法沒有帶來任何改進，研究小組差點就要放棄，直到他們想搞清楚這個工具在單服務器情況下是否果真可以适用。他們發現，隻要足夠小心地選擇一個多項式，單單一台服務器就可以根據 2011 年的結果對其進行預處理，從而獲得了 Wichs 已思考多年的安全高效的查找方案。
Wichs 表示，在設計了秘密查找方案之後，論文作者轉向了私密互聯網搜索的實際目标，這比從數據庫中提取信息要複雜得多。私密查找方案本身确實允許類似谷歌的秘密搜索，但它非常耗費人力：你自己運行谷歌的算法，并在必要時從互聯網上秘密提取數據。真正的搜索（你發出請求，然後靜等服務器收集結果）實際上是同态加密這種更廣泛的方法力求實現的目标，這種方法掩蓋數據，以便其他人可以在一無所知的情況下操縱數據。
典型的同态加密策略會遇到與私密信息檢索同樣的障礙，每次搜索都要長時間地搜索互聯網上的所有内容。但是使用私密查找方法作爲基本框架，論文作者設計出了一種新的方案，該方案運行的計算更像我們每天使用的程序，在不搜遍整個互聯網的情況下秘密提取信息。
這将爲互聯網搜索和任何需要快速訪問數據的程序提高效率。
Ishai 表示，雖然同态加密是私密查找方案的一種實用擴展，但他認爲私密信息檢索是更爲根本性的問題。論文作者的解決方案是 " 神奇的構建模塊 "，他們的同态加密策略是自然而然的後續策略。
目前，這兩種方案都沒有實際用途。幸運的是，Vaikuntanathan 表示，未來從大型數據庫中進行私密查找将觸手可及。
