Researches On Private Set Intersection Protocols Using Polynomial Point-Value Pairs

Secure computation,called privacy-preserving computation,allows participants who do not trust each other to collaborate to complete a function calculation based on their private inputs.It has a wide of practical application scenarios,such as finance blacklist query,etc.As a protocol for specific application scenarios in the secure computation,private set intersection(PSI)protocol has been extensively studied and optimized in recent years.In current application scenarios,most of the PSI protocols are designed using public keys or symmetric cryptosystems.However,the PSI protocol using a cryptosystem has problems such as low efficiency,complex key management,key consistency,and secure transmission of keys.This paper mainly uses polynomial point-value pairs to represent set elements,combined with pseudo-random function and hash technology,and proposes a method of secure computation without cryptosystem.On the one hand,we design a PSI protocol using polynomial point-value pairs.First,both parties use polynomial point-value pairs to represent set elements.Next,the polynomial point-value pairs are blinded by a pseudo-random function.Then,the two parties interact and calculate through the blinded polynomial point-value pairs.Finally,we restore the polynomial by interpolation and find the root by polynomial decomposition to determine whether it is an intersection.To further improve the efficiency of the protocol,we use hash technology to map the set elements to the hash table,and split the high-order polynomial into several low-order sub-polynomials and use element preprocessing computation to reduce polynomial factorization operations.Through experimental results and theoretical analysis,our protocol has the following advantages:(1)it provides a scheme without cryptosystems;(2)it can provide a lightweight PSI protocol when the set elements are less than 2¹².On the other hand,we use polynomial point-value pairs to design a secure intersection computation protocol that can be delegated in a cloud environment.In this protocol,we delegate the blinded polynomial point-value pairs to the cloud server for computation through a pseudorandom function.Combining experimental results and performance analysis shows that:(1)Our protocol does not use a cryptosystem to design a PSI scheme,so there is no need to consider providing additional computation and communication costs for key processing;(2)Under ordinary channels,the efficiency of ours protocol is better than the O-PSI protocol that requires a secure channel;our protocol achieves a similar execution effect to the EO-PSI protocol that uses a symmetric cryptosystem and requires a secure channel.