如何在數據庫中秘密地查詢隱私數據

日常生活中經常會出現這樣的場景：你想在數據庫上查詢某個東西，但卻不希望留下線索，讓別人知道你查詢了什么。比方說，投資人可能會在數據庫上查詢某支股票的信息，但卻不希望任何人知道他感興趣的股票究竟是哪一支?？瓷先?，似乎唯一的辦法就是把整個數據庫全部拷回家。然而，這些數據往往都擁有非常龐大的體積，全部拷走通常都是很不現實的；另外，考慮到數據內容的隱私性和數據本身的寶貴價值，數據的持有者通常也不允許其他人把整個數據全盤拷走。不過，隨著分布式數據庫的廣泛應用，上面的難題有了一個兩全其美的好辦法：假設有兩個內容完全相同的數據庫，投資人可以先在第一個數據庫上執行一個不會透露目的的查詢，再在另一個數據庫上執行另一個不會透露目的的查詢，兩次查詢結合起來便能推出想要的結果。只要沒有人刻意去收集并且對比兩個數據庫的查詢記錄，那么誰也不會知道投資人真正想要查詢的是什么。在這個背景下，我們有了下面這個有趣的問題。

服務器隨機產生了一個 {1, 2, …, 100} 的子集 S ，并且同時發送給了 A 和 B 兩名前臺工作人員。 A 、 B 兩名前臺都接受其他人的提問，但為了保護數據，兩個人都只能用“是”或者“否”來回答問題，并且都不允許同一個人重復提問。你非常關心某個數 n 是否在這個子集里。其實，你本來可以直接問 A 和 B 中的任何一個人“數字 n 是否在集合 S 里”，但是這樣一來，對方就知道了你想要查詢的是什么。為此，你可以向 A 和 B 各問一個問題（結合兩人的回答便能推出集合 S 里是否包含數字 n ），但卻不能讓 A 和 B 當中的任何一個人知道你查詢的是哪個數（我們假設 A 、 B 兩人不會串通起來，把他們各自收到的問題聯系在一起）。事實上，你需要保證 A 和 B 兩人都不能從你的問題中獲取到任何信息，也就是說，對于 A 和 B 當中的任何一個人來說，各種問題出現的概率不會隨著 n 值的改變而改變。再換句話說，如果 n 的值變了，那么 A 和 B 各自將會聽到的問題應該擁有和原來相同的概率分布。

答案：首先，自己隨機生成一個 {1, 2, …, 100} 的子集 T1 （每個數都有 1/2 的概率被選進 T1 ）。如果 T1 里面正好包含數字 n ，那么就把 T1 里的數字 n 去掉，把所得的結果記作 T2 ；如果 T1 里面沒有數字 n ，那么就在 T1 中加入數字 n ，從而得到 T2 ?，F在，將 T1 發送給 A ，并詢問 T1 里面是否有偶數個數正好也在 S 里。類似地，再將 T2 發送給 B ，并且詢問同樣的問題：在 T2 里面是否有偶數個數同時也屬于 S 。注意， T1 和 T2 的唯一差別，就是一個里面有 n 一個里面沒有 n 。因此，如果 A 和 B 的回答是一致的，就說明數字 n 不在 S 里面；如果 A 和 B 的回答不一致，就說明數字 n 在 S 里面。另外，容易看出，不管是 T1 還是 T2 ，從 1 到 100 每個數在里面出現的概率都是 1/2 。因此，不管是 A 還是 B ，他被問到的問題都總是具有完全相同的概率分布，這不隨 n 的變化而變化。

這種方案的缺陷就是，每條詢問都非常長。為了描述 T1 或者 T2 ，我們需要使用一個 100 位的 01 串，它一共有 100 個 bit 。如果 S 不是 {1, 2, …, 100} 的子集，而是 {1, 2, …, N} 的子集，那么在上述方案中，我們需要給 A 、 B 各發送 O(N) 個 bit 的數據。在 N 非常大的情況下，這么做同樣是不現實的。有趣的是，如果前臺不止兩個人，而是四個人的話，那么我們可以做得更好：我們可以給四個人都只發送 O(√N) 個 bit 的數據，并且同樣保證每個人都不能從中推出任何信息來。

為了便于說明，我們現在假設 S 是 {0, 1, 2, …, 99} 的一個子集。假設你想要知道， 67 是否在集合 S 里。于是，你首先隨機生成一個 {0, 1, 2, …, 9} 的子集 T1 ，然后在里面加上數字 6 （如果 T1 里沒有 6 的話）或者去掉數字 6 （如果 T1 里有 6 的話），得到 T2；再生成另一個 {0, 1, 2, …, 9} 的子集 T3 ，然后在里面加上數字 7 （如果 T3 里沒有 7 的話）或者去掉數字 7 （如果 T3 里有 7 的話），得到子集 T4 。接下來，向 A 、 B 、 C 、 D 依次詢問下面四個問題

• A ：在所有十位數屬于 T1 并且個位數屬于 T3 的數當中，是否有偶數個數在集合 S 里。
• B ：在所有十位數屬于 T1 并且個位數屬于 T4 的數當中，是否有偶數個數在集合 S 里。
• C ：在所有十位數屬于 T2 并且個位數屬于 T3 的數當中，是否有偶數個數在集合 S 里。
• D ：在所有十位數屬于 T2 并且個位數屬于 T4 的數當中，是否有偶數個數在集合 S 里。

如果 T1 等于 {2, 4, 7, 8, 6} ，那么 T2 就應該等于 {2, 4, 7, 8} ；如果 T3 等于 {2, 3, 5} ，那么 T4 就應該等于 {2, 3, 5, 7} 。四次詢問之后我們便可得知，在下圖各種顏色的方框中，屬于集合 S 的數有奇數個還是偶數個。結合 A 、 B 的回答（藍色方框和黃色方框），我們就能推出，在集合 S 當中，十位數屬于 T1 并且個位數恰好為 7 的數有奇數個還是偶數個；結合 C 、 D 的回答（紅色方框和綠色方框），我們就能推出，在集合 S 當中，十位數屬于 T2 并且個位數恰好為 7 的數有奇數個還是偶數個。于是，我們就可以知道，十位數恰好為 6 并且個位數恰好為 7 的數是否在集合 S 當中了。

類似地，如果集合 S 是 {1, 2, …, N} 的子集，那么我們可以對這 N 個數進行重新編碼，使得每個數都由高位和低位組成。那么，高位和低位的取值范圍都是從 1 到 √N 。在整個協議中，我們需要給每個人發送兩個 {1, 2, …, √N} 的子集，這相當于兩個 √N 位的 01 串，因此其數據量為 2√N 個 bit ，也就是 O(√N) 個 bit 。

不過，請注意，雖然與每個人交流的數據量少了，但這次卻有四個人了，因而你需要發送四個這么大的數據。當 N 很小的時候， 4 · 2√N 很可能反而比 2 · N 更大。

同樣地，如果我們有 2d 個人，我們就可以把 1 到 N 里面的所有數都看作 d 位數，每一位的取值范圍是從 1 到 N1/d 。為了完成一次查詢，我們需要給每個人發送 d 個 {1, 2, …, N1/d} 的子集，因此總共需要發送 2d · d · N1/d 個 bit 。對于不同的 N ，我們可以選取最合適的 d ，使得 2d · d · N1/d 最小。例如，下圖所示的就是 N = 1 000 000 時函數 f(d) = 2d · d · N1/d 的圖像，可見 d = 4 時的通信成本是最低的。因此，如果查詢點足夠多的話，我們可以選擇在 16 個不同的地方進行查詢。