如何在數(shù)據(jù)庫中秘密地查詢隱私數(shù)據(jù)

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

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

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

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

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

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

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

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

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

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