Title: Private set intersection with constant-size encryptions using RSA subgroups

Authors: Sigurd Eskeland

Addresses: Norsk Regnesentral, Postboks 114 Blindern, 0314 Oslo, Norway

Abstract: 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.

Keywords: private set intersection; secure multiparty computations; RSA subgroups.

DOI: 10.1504/IJACT.2024.144917

International Journal of Applied Cryptography, 2024 Vol.5 No.1, pp.30 - 40

Received: 09 Nov 2023
Accepted: 01 Mar 2024
Published online: 10 Mar 2025 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article