Abstract:In order to improve efficiency and solve the security vulnerabilities of the secure set computation protocols in practical applications, two secure two-party protocols for set membership and set intersection were proposed based on discrete logarithm problem and the polynomial representation of sets with which the set operation problem could be transformed into a polynomial evaluation problem. Firstly, a latest efficient secure set membership protocol was analyzed, and a security vulnerability of leaking the privacy of the participants by obtaining the element of participants on the brute attack was found. To overcome the security vulnerability, a new method was introduced by representing sets by polynomials and randomizing the polynomials, which could ensure the security of the participants without any leakage of interactions. Based on the discrete logarithm problem and the new method, a new secure set membership protocol was presented. The protocol could judge set-element membership with high-efficiency, and did not leak any other information about the participants besides the size of the set. Further, a secure set intersection protocol was showed according to the same technique. The security proofs of both protocols were given under the semi-honest model by using the probability polynomial time simulator, which indicated that the simulator views were computationally indistinguishable from the original protocols' execution views. Finally, the detailed analysis about the protocols' performance was presented, showing that both protocols were more efficient than other protocols since their communication complexity and computational complexity were smaller.