AbstractWe introduce the public key encryption with keywords search into the problem of secure two‐party computation and obtain a novel approach to accomplish private set intersection (PSI), which uses the public key encryption with keywords search as the basic tool. The public key encryption with keywords search scheme we adopt does not need the expensive MapToPoint operation, thus the computation complexity can be reduced significantly compared with other PSI schemes, which also obtain linear computation complexity. We aim to achieve PSI in computationally asymmetric settings, which can be instantiated by cloud computing. Our protocol satisfies the privacy with respect to semi‐honest behavior, and the client only needs to compute m multiplications, m hashes, and one modular exponentiation to obtain the intersection, where m denotes the cardinality of the client's input set. Copyright © 2014 John Wiley & Sons, Ltd.