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

Fairness of Secure Computation Protocols for Disjointness of Two Sets

官振傑(Guan, Albert)

指導教授 ： 曾文貴

國立交通大學/資訊學院/資訊科學與工程研究所/碩士(2010年)

https://doi.org/10.6842/NCTU.2010.00472

摘要

給定兩個有限集合 $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.

並列關鍵字

Fairness Computation Protocols ； Set Intersection

參考文獻

[1] Fabrice Boudot, Berry Schoenmakers, and Jacques Traore. A fair and ecient

solution to the socialist millionaires' problem. Discrete Applied Mathematics,

111:23{36, 2001.

Computing, pages 364{369. ACM, 1986.

fairness in secure two-party computation. In Proceedings of 40-th Annual ACM