Research On Key Techniques In Private Set Operations

With the continuous development of various technologies such as cloud computing,the Internet of Things,and artificial intelligence,people are enjoying unprecedented convenience while facing the risk of privacy leakage.Secure multiparty computation enables mutually untrusted parties to perform joint computation without disclosing their private inputs.It is currently a key technology for solving data security problems in the process of data circulation.As a specialpurpose protocol in secure multi-party computation,private set operation(PSO)allows parties to perform secure computation on their private sets,such as intersection,union,and intersection cardinality.PSO has a wide range of applications in private data mining,human genome research,social networks,and other privacy-preserving scenarios.We focus on the PSO and our main research includes:First,we investigate the key data structures in PSO.Advanced data structures play an important role in the design of efficient PSO protocols.However,there is a lack of systematic overview of various data structures in PSO and no uniform efficiency comparison on the same platform among them is provided.To address this problem,we classify the data structures deployed in existing PSO protocols into three categories:hashing tables,filters,and oblivious key-value stores.After clarifying the basic definitions and constructions of each data structure,we compare their main features,summarize their typical application methods in different protocols,and provide performance analysis and benchmarking results of each data structure.Second,we investigate efficient private computing on set intersection(PCSI)protocols in the unbalanced setting.In CCS 2018,Chen et al.firstly considered an unbalanced PCSI protocol.However,their inherent generic two-party computation(2PC)leads to the inefficiency,and their protocol is only a theoretical result without no concrete implementation.To address this problem,we combine the characteristic sharing protocol based on fully homomorphic encryption with a permuted matrix private equality test(pm-PEQT)protocol proposed by Tu et al.,and construct efficient private set intersection with cardinality(PSIcard)protocol and private set intersection cardinality with sum(PSI-card-sum)protocol.The communication complexity of our protocols is logarithmic in the large set.Moreover,we demonstrate the practicality of our protocols with C++implementation.It shows that our protocols achieve significantly shrinking in communication cost and speedup in running time compared to the state-of-theart protocols.Our PSI-card protocol,for example,reduces the communication cost to 4%-49%of the state-of-the-art protocol and running time to 36%-50%of the state-of-the-art protocol.