計算兩集合交集與否的公平協定

Abstract

給定兩個有限集合 $A$ 和 $B$. 假設沒有一個集合是空的, 而且至少有一個集合包含多於一個元素. 我們設計一個決定此二集合是否有交集的公平且安全的計算協定.

在此計算協定開始時, 每位參與者各自擁有一個集合當作此協定的輸入. 在此協定結束時, 每位參與者都知到這兩個集合是否有交集, 除此之外, 雙方都不知道其他的資訊. 例如: 他們都不知道別人的集合是甚麼. 假設此二集合的交集非空集合, 也沒有一方會知道這些交集的元素會是甚麼, 或是 $A$ 和 $B$ 的交集包含多少元素.

我們的第一個協定對雙方而言是完全公平的. 這意思是指, 即使有一方是惡意者, 他不忠實遵守協定來執行, 甚至可以提前結束此協定, 他也占不到便宜. 協定結束之後一定是雙方都知道答案或雙方都不知道答案. 我們的第二個協定對雙方而言幾乎是完全公平的. 第二個協定所需要的計算量比第一個少, 而且其安全性所需要的假設條件也比較少.

我們的協定先將兩集合的元素轉換成模糊的形式, 使得雙方都無知道照轉換後的元素與原來的元素對應關係. 我們的協定只需要 $O(m n)$ 的比較經過轉換之後集合的元素是否相等就可讓雙方知道答案, 其中 $m$ 和 $n$ 分別為集合 $A$ 和 $B$ 集合元素的個數. 其所需的比較次數和 $A$ 與 $B$ 集合元素的定義範圍無關.

我們已知百萬富翁問題可以化約為兩集合是否有交集的問題來解. 所以, 即使是定議域非常大的百萬富翁問題, 利用我們的協定來解百萬富翁問題也會非常有效率.

Given two finite nonempty sets $A$ and $B$. Assume that at least one of the set contains more than one elements. We present fairness secure computation protocols for determining whether the given two sets have intersection or not.

Each party has a set as the input to the protocol. At the end of the protocol both parties know whether the two sets have intersection or not, but noting else. In particular, each party does not know the set the other party has. Furthermore, if the intersection of the two sets is not empty, then none of the parties know the elements in the intersection, nor do they know the cardinality of the intersection.

Our first protocol is complete fair with respect to both parties. At the end of the protocol, both parties knows the final result or none of them know it, even if there is a malicious party who may violate the protocol. Our second protocol is almost complete fair. The probability that ``one party learns the result but the other does not'' is negligible. This protocol needs less computational time, and it also needs less proofs of knowledge in the protocol.

Our protocols need only $O(m n)$ comparisons of the obfuscated elements, where $m$ and $n$ are the number of elements in $A$ and $B$, respectively. The number of comparisons is independent of the size of the domain from which the elements of the sets $A$ and $B$ are selected.

It is known that the millionaires' problem can be reduced to the set intersection problem. Therefore, the millionaires' problem can be solved efficiently by our protocol even if the input domain is very large.