Faster Secure Comparisons with Offline Phase for Efficient Private Set Intersection

Abstract

In a Private section intersection (PSI) protocol, Alice and Bob compute the intersection of their respective sets without disclosing any element not in the intersection.PSI protocols have been extensively studied in the literature and are deployed in industry.With state-of-the-art protocols achieving optimal asymptotic complexity, performance improvements are rare and can only improve complexity constants.In this paper, we present a new private, extremely efficient comparison protocol that leads to a PSI protocol with low constants.A useful property of our comparison protocol is that it can be divided into an online and an offline phase.All expensive cryptographic operations are performed during the offline phase, and the online phase performs only four fast field operations per comparison.This leads to an incredibly fast online phase, and our evaluation shows that it outperforms related work, including KKRT (CCS'16), VOLE-PSI (EuroCrypt'21), and OKVS (Crypto'21).We also evaluate standard approaches to implement the offline phase using different trust assumptions: cryptographic, hardware, and a third party ("dealer model"). I. INTRODUCTIONCompanies collect increasingly larger amounts of data about their customers' operation.Each company collects different data depending on their business, and the combination of these different data sets offers greater benefit than each set by itself.A standard example is Google collecting which user clicks on which online ad while Mastercard collects financial transactions performed by its clients using their cards.To allow Google to compute the number of successful transactions after a user clicked on an online ad, Google and Mastercard link their data based on a common user identifier, e.g., the user's phone number.Abstractly, this is an instance of Private Set Intersection (PSI).In PSI, two parties, each have a set of (unique) elements and want to compute their intersection without revealing any element not in the intersection.PSI is indeed deployed by Google and Mastercard to analyze ad conversions [43,83], but it has many more applications.Consequently, PSI has recently been extensively studied in the literature [1, 12-17, 19, 22, 26-28, 31-33, 39, 41, 43, 47, 52, 55-58, 60-63, 66-72, 74-76, 83].The currently most efficient state-of-the-art PSI protocols are based on oblivious pseudo-random functions [15,57,76].They require a constant number of publickey cryptography operations, linearly many symmetric key cryptography operations, and one round of interaction.This is asymptotically optimal, and any performance improvement can only stem from reduced constants which are, however, already very low.We note that PSI requires public-key operations, since two-party computation can be reduced to PSI (see our reduction in Section II-D), and two-party computation requires public-key operations.Hence, any (new) approach must deal with these unavoidable and expensive operations.In this paper, we present a new (equality) comparison protocol that is simple, elegant, and very efficient.Our comparison protocol improves over the state-of-the-art in two aspects: first, it reduces (equality) comparison to oblivious linear evaluation (OLE), and, second, it enables the use of offline precomputed OLE tuples instead of computing the OLE online.This results in an alternative construction of PSI that off-loads all expensive cryptographic operations, public and symmetric key, to an initial offline phase.The offline phase precomputes correlated randomness and can be run in advance, independently of the inputs to the protocol.The online phase uses this randomness and the inputs to securely compute the output.Our online phase is highly efficient, comprising only four fast operations in a small field, i.e., one multiplication and three additions per comparison.Moreover, it takes only one round.The offline phase can be implemented using standard approaches based on only cryptographic assumptions, e.g., using lattice-based homomorphic encryption or Oblivious Transfer (OT), but also based on more efficient hardware or other trust assumptions, such as a trusted third party ("dealer model" [38]). A. Why consider an offline phase?Our offline phase enables a very fast online phase.In Figure 1 we display a comparison of computation time and communication cost to related work [15,33,57,70,76] for a data set size of 1 million elements in the online phase online.Note that VOLE-PSI [76] requires less communication for these small sets.On a larger data set with 16 million elements our online phase is between 2.4 and 3.5 times faster than Kolesnikov et al.'s work [57] and 1.2 and 14.6 times faster than Rindal and Schoppmann's work [76] while requiring less communication than either one of them.In general, our advantage increases as data set sizes grow, but Rindal and Schoppmann neither make their code available nor do they report evaluation results for larger data set sizes which makes

Topics & Concepts