Chinese Journal of Computers   Full Text
Title	Secure Computation Protocol for Testing the Inclusion Relation of Sets
Authors	LI Rong-Hua1)，2) WU Chuan-Kun3) ZHANG Yu-Qing2)
Address	1)(Graduate University of Chinese Academy of Sciences, Beijing 100049) 2)(National Computer Network Intrusion Protection Center, Beijing 100049) 3)(State Key Laboratory of Information Security, Institute of Software, Chinese Academy of Sciences, Beijing 100080)
Year	2009
Issue	No.7(1337—1345)
Abstract &   Background	Abstract A set operation problem is considered in the secure computation setting. Player A has a secret set SA and player B has a secret set SB, where SA and SB belong to a universe. They want to know if SA includes SB without leaking anything else about their secret sets. Three protocols of different levels of security and efficiency are proposed for this problem. The first protocol can be based on the so-called Superposed Encryption scheme or threshold encryption scheme. Let NB be the size of set SB, the first protocol needs NB rounds of communication. The other two protocols are based on standard public-key encryption schemes with additively homomorphic property, and need only one round of communication. Compared to previous results, the first two protocols use a new technique of representing sets, and the third protocol avoids threshold decryption in the output phase, and is more efficient. Keywords secure computation; set-inclusion; superposed encryption; homomorphic encryption Background Secure Multiparty computation is that n distrustful parties, with each holding a secret input, want to compute an agreed function of their inputs. But they don’t wish to leak anything else except the outputs of the function. A protocol for multiparty computation should satisfy correctness and privacy. That is to say, the results of the computation should be correct and the privacy of parties’ inputs should be protected even if an adversary corrupts some of the parties. The set inclusion problem can be seen as a special case of secure multiparty computation problem. Thus, the set inclusion problem can be solved using the general protocols for secure multiparty computation. However, general protocols are not very efficient. Li, Si, and Dai studied the set inclusion problem, and gave a solution to it. Actually, their protocol computes the cardinality intersection problem, not the set inclusion problem. That is to say, parties compute the size of the intersection set, and then decide if one set includes the other by comparing the sizes of the intersection and the sizes of their sets. Kissner and Song also studied the set inclusion problem. They presented a protocol based on threshold homomorphic encryption scheme. In their protocol, SAis represented as a polynomial f(x), such that f(a)=0 if and only if a∈SA. The set SA includes the set SB if Σf(SB［i］)=0, where SB［i］ denotes the ith element of SB. This paper proposes three protocols for the set inclusion problem. The first protocol can be based on superposed encryption or threshold encryption. The second protocol is a modified version of the first protocol, which can be based on the traditional homomorphic encryption (in contrast to superposed encryption and threshold encryption). These two protocols use a set representation method different from the one that Kissner and Song’s protocol uses. Here, SA is represented as a polynomial f(x) such that f(a)=1 if and only if a∈SA, and SA includes SB if Πf(SB［i］)=1. Such a method of representing sets may be of independent use. The third protocol uses the same method as Kissner and Song’s protocol; however, it is based on homomorphic encryption instead of threshold encryption, and is more efficient. This paper is supported by the National Natural Science Foundation Nos.60573048,60773135.The project No.60573048 is about survivability of networks. The project No.60773135 is about P2P trust management. The group has some results on security vulnerabilities, vulnerability rating methods, survivability of networks, etc. Secure multiparty computation is a part of these projects, and considers cryptographic protocols that are required to protect privacy of inputs.