Searchable Encryption：New Approaches for Private Set Intersection

Abstract: We introduce the technique of searchable encryption into the problem of secure two-party computation, and obtain novel approaches to accomplish Private Set Intersection (PSI). We present two protocols for PSI. The first one uses Baek’s Public Key Encryption with Multiple Keywords Search (MPEKS) as the basic tool, and the second one uses Gu’s Public Key Encryption with Keyword Search (PEKS) as the basic tool. Baek’s MPEKS supports multiple keywords search, but it requires expensive MapToPoint operations. Although the computation complexity of the MapToPoint operation can be reduced by new techniques, it indeed influences the efficiency. A natural method is to find a searchable encryption which requires no MapToPoint operations. So, we present the second protocol based on Gu’s PEKS. Gu’s PEKS does not support multiple keywords search, however, it still can help us to improve the efficiency of PSI significantly. We aim to achieve PSI in computationally asymmetric settings such as Cloud Computing, and both of our two protocols gain linear computation complexity for the client. We assume that m denotes the cardinality of the client’s input set. Concretely, in the protocol based on MPEKS, the client needs to compute m multiplications, m MapToPoint operations and one modular exponentiation; and in the protocol based on PEKS, the client only needs to compute m multiplications, m ordinary hashes, and one modular exponentiation to get the intersection. Both protocols satisfy privacy with respect to semi-honest behaviors