白話導讀
Information Sciences
SCI · IF 4.31 · Q1
2014/08
兩邊比對名單，卻誰也不告訴誰
A Communication-efficient Private Matching Scheme in Client–Server Model
Mu-En Wu, Shih-Ying Chang, Chi-Jen Lu, Hung-Min Sun
一句話： 私密比對讓客戶端算出自己與伺服器名單的交集 ，卻不洩漏任何資訊給伺服器。在伺服器資料量很大的情境下，作者用 Oblivious Transfer ＋ 通用雜湊 把通訊複雜度從 Õ(m+n) 降到 Õ(m·log²n) ——並誠實說明這麼做要付出的代價。
先問：這在解什麼問題？the problem
私密比對（Private Matching, PM） 要解的問題是這樣的：客戶端 C 手上有一份 m 個元素的資料集 X，伺服器 S 有一份 n 個元素的資料集 Y。C 想知道兩份名單的交集 X∩Y ，但過程中不能洩漏任何資訊給 S 。
在此之前，最有效率的 PM 方案，通訊複雜度是 Õ(m+n)——會隨著 n 線性增加 。問題就在這裡：在 Client–Server 模型裡，伺服器的資料集 Y 通常非常大 ，通訊量跟著 n 一起長，效率自然不夠好。
怎麼做？OT ＋ 通用雜湊the method
作者提出一套基於 不經意傳輸（Oblivious Transfer, OT） 與通用雜湊函數（universal hash function） 的 PM 方案，把通訊複雜度降到 Õ(m·log²n) ——不再隨伺服器資料量線性成長。
作者並指出，當 log²(mn)1+Δ = Õ(n/m)（安全參數 Δ > 0）時，所提方案的效率優勢更明顯。
C 有 X（m 筆）
S 有 Y（n 筆）
Oblivious Transfer
不洩漏查詢內容
Universal Hash
壓縮通訊量
Õ(m·log²n)
不隨 n 線性成長
方案結構：以不經意傳輸保證伺服器學不到客戶端查了什麼，再用通用雜湊函數把通訊量從隨 n 線性成長壓到 Õ(m·log²n)。
代價是什麼？作者自己講得很清楚the trade-off
這篇論文最值得欣賞的地方，是作者主動把方法的副作用寫進摘要 ：
① 會出現「錯配」問題使用通用雜湊函數會造成 mismatch 問題 ，這會影響 PM 的準確度 ；此外，它還會洩漏伺服器的資訊 。
② 於是放寬定義，並證明它為此，作者放寬 PM 的定義 ，另外定義了「近似私密比對（approximate PM） 」，並證明在適當的參數設定下，它在 Client–Server 模型中幾乎和標準 PM 一樣安全 。
怎麼讀這個結論： 這不是「有 bug 沒解掉」，而是一個誠實的取捨——作者用「可證明幾乎等價的安全性」換來「不隨伺服器資料量成長的通訊成本」，並把換來的代價（準確度與資訊洩漏）明明白白寫出來。
閱讀原始論文（ScienceDirect） →