Private set intersection with constant-size encryptions using RSA subgroups

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 based on RSA subgroups. The novel idea aims at that each element and subgroups of a universe can be represented by means of subgroups having unique order. Moreover, this representation means that any subset within that universe can be encrypted by a single encryption, and not by many individual encryptions. The proposed protocols combine the private inputs of two parties securely, in such a way that all that can be deduced from the resulting subgroup is whether the inputs overlap or not. 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 two encryptions and five exponentiations. Configurations for three output granularities (Boolean, cardinal, and intersection subset) are proposed. Lastly, an extended PSI scheme handling larger sets is also proposed.