Research On Secure Multiparty Computation Of Set-Related Problems

Cryptography studies how to ensure secure communication in the presence of adver-saries and is the cornerstone of information security.It can guarantee the confidentiality,integrity and authentication of information.Secure multi-party computation(SMC)is an important branch of cryptography,and it makes two or more parties perform cooperative computation on their private data without disclosing the privacy of the data.SMC makes us mine the full value of private data,and therefore it is becomes an important technology to preserve data privacy.As the demand for privacy-preserving increases,SMC becomes one of the focuses of international cryptographic community.Taking the related secure multiparty set computation problems as starting point,this thesis deeply studies secure set intersection computation,secure set union computation and secure vector computation and proposes more efficient protocols for these problems.Our contributions are as follows.1.We construct two efficient subset computing protocols.Most existing solutions for secure subset computation cannot solve this problem very well.They can only pre-serve the privacy of one set in the subset computation,while revealing the elements of another set.The protocol that can also preserve the privacy of two sets is inefficient.To narrow the gap,we first design an encoding scheme,and then we,based on the encoding scheme and homomorphic encryption algorithm,propose an efficient secure subset pro-tocol in case both private sets are subsets of a universal set.If two private sets are subsets of a large set,the protocol is not efficient enough.Therefore,we further design an ef-ficient protocol by using Bloom filter and homomorphic encryption scheme.We prove that these proposed protocols are secure in the semi-honest model by using the simulation paradigm.We theoretically analyze the efficiency and test the efficiency by experiment.2.We design efficient secure set intersection computation protocols for different situations,and prove that they secure in the semi-honest model.Firstly,we construct a multi-party set intersection computation protocol which is information-theoretically se-cure and more efficient than existing protocols.In order to balance the computational and communication complexity,we also propose an improved protocol for secure multi-party set intersection computation which reduces the computational complexity at the cost of increasing the communication complexity compared.Subsequently,for secure two-party set intersection computation,we propose two efficient protocols for different settings.One is applicable to the scenarios that private sets are subsets of an exponentially large.Another one is applicable to the scenarios that private sets are subsets of a finite set.This protocol for two-party set intersection computation protocol can also be extended to privately compute the cardinality of set intersection and union,and authenticated set com-putation.The protocol for set intersection can be used to solve other privacy-preserving problem such as privacy-preserving greatest common divisor computation.3.Compared with secure set intersection computation,few works study secure set union computation.The existing protocols are less efficient and not suitable for cloud computing environment.To bridge the gap,we propose two secure multiparty set union computation protocols for cloud environment and prove that they are secure.These two protocols are applicable to any set whose elements have total order relationship.They also can prevent collusion attack of multiple participants.It can also be used to privately sort the elements of multi private sets.The homomorphic encryption algorithm used in the first protocol can either be additively homomorphic or multiplicatively homomorphic with minor modification of encoding scheme.The second secure set union computation protocol is more efficient than the first one because it is based on a more efficient encoding method.With simple modification,the proposed set union protocols can also be used to privately compute set-intersection.4.The existing protocols for secure vector linear combination computation are all naive protocols.These protocol do not view a vector as whole,rather as many com-ponents,and the vector computation is applied to each component.Such computation results in high computational complexity.To overcame such shortcomings,we use Godel encoding scheme to represent a vector with a integer,and then we use additively homo-morphic encryption algorithm to design a protocol to directly add two private vectors.We further use NTRU encryption algorithm to design a protocol to resist quantum at-tack.Both protocols are efficient.We prove that they are secure in the semi-honest model by using the simulation paradigm.Finally,we use these protocols to construct secure statistical protocol and secure electing protocol.