Private set intersection using RSA subgroups with constant-size encryptions

Private set intersection (PSI) evaluation is a well-known secure multiparty computation problem that has received much attention. Authors generally tend to state improved performance as a goal and justification for their proposed PSI schemes. In this paper, we propose an original and new approach to two-party PSI evaluation for small sets that is based on small RSA subgroups. Contrary to previous approaches that at best incur linear communication and computational complexity to the set size, our scheme is the first to achieve constant communication and computational complexity incurring only 2 group elements and 5 exponentiations. An extended PSI scheme handling larger sets is also proposed.