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

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

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

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

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

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

• A ：在所有十位數(shù)屬于 T1 并且個(gè)位數(shù)屬于 T3 的數(shù)當(dāng)中，是否有偶數(shù)個(gè)數(shù)在集合 S 里。
• B ：在所有十位數(shù)屬于 T1 并且個(gè)位數(shù)屬于 T4 的數(shù)當(dāng)中，是否有偶數(shù)個(gè)數(shù)在集合 S 里。
• C ：在所有十位數(shù)屬于 T2 并且個(gè)位數(shù)屬于 T3 的數(shù)當(dāng)中，是否有偶數(shù)個(gè)數(shù)在集合 S 里。
• D ：在所有十位數(shù)屬于 T2 并且個(gè)位數(shù)屬于 T4 的數(shù)當(dāng)中，是否有偶數(shù)個(gè)數(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ù)個(gè)還是偶數(shù)個(gè)。結(jié)合 A 、 B 的回答（藍(lán)色方框和黃色方框），我們就能推出，在集合 S 當(dāng)中，十位數(shù)屬于 T1 并且個(gè)位數(shù)恰好為 7 的數(shù)有奇數(shù)個(gè)還是偶數(shù)個(gè)；結(jié)合 C 、 D 的回答（紅色方框和綠色方框），我們就能推出，在集合 S 當(dāng)中，十位數(shù)屬于 T2 并且個(gè)位數(shù)恰好為 7 的數(shù)有奇數(shù)個(gè)還是偶數(shù)個(gè)。于是，我們就可以知道，十位數(shù)恰好為 6 并且個(gè)位數(shù)恰好為 7 的數(shù)是否在集合 S 當(dāng)中了。

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

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

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