Miyaji Laboratory

Recently, we are deeply dependent on the electronic information. There are numerous situations, where sensitive data need to be shared between two or more entities without mutual trust. As often it happens, the research community has foreseen the need for mechanisms to enable limited sharing of sensitive information. Therefore various ways have been proposed. Among them, Private Set Intersection Protocol(PSI) is particularly effective for scenarios, where two players with each data sets want to compute some information about their common data without disclosing them. Though many kinds of PSIs were proposed, all of them have some problems. The most conspicuous property is that the data size of each player is leaked to each other. SHI-PSI can prevent one party from being leaked his data size, but that of the other party is still leaked. There are some PSIs for more than two parties, and they are called Multi-Party PSI. This type of PSIs also have some problems, they are the restriction that the data size of all players is same and the communication complexity is O(cnk), where n is the number of the players, k is the data size and c is the allowed number of dishonest players, who can plot together. In this paper, we propose two Multi-Party PSIs based on a two party PSI, which computes the cardinarity of the intersection of two parties. Unlike previous protocols, the data size of each player is arbitrary and if the interesection is empty for multi party, the protocol aborts. As a result, the computational and communicational costs can be reduced. In the first proposed protocol, the computational and communicational costs are different in each player. The computational one is at most O(logn k) and at least only 4k, and the communicational one is at most O(nk) and at least only 3k. This protocol is secure against semi-honest adversary who act according to their prescribed actions in the protocol and this is a problem. The second protocol is secure against even malicious adversary model. In the second protocol, similariy, the computational and communicational costs are different in each player. The computational one is at most O(k) and at least only $5k$, and the communicational one is at most O(nk) and at least only k. These protocols are very efficient in terms of computational and communicational costs, but it remains that the problem that not only the data size of all players but also the cardinality of them are leaked to each other.