TL;DR
This paper introduces "Reactive Private Set Intersection" (RePSI), a new cryptographic primitive designed to prevent "oracle attacks" where a dishonest client learns a server's private set by repeatedly querying a standard Private Set Intersection (PSI) protocol. They achieve this by modeling PSI as a stateful, reactive functionality and present practical constructions that limit the client's ability to probe the server's set over multiple interactions.
What Problem Does This Paper Address?
Traditional Private Set Intersection (PSI) protocols allow two parties (a client and a server) to compute the intersection of their private sets without revealing anything beyond the intersection itself. However, a significant practical vulnerability arises when these protocols are used repeatedly. A malicious client can exploit this by making multiple queries, effectively "enumerating" the server's set over time. This is known as an "oracle attack." While not a violation of traditional security definitions (which often assume stateless interactions), it severely limits PSI's real-world applicability, especially when the server's data is static. This paper addresses this gap by introducing a framework for "Reactive PSI" (RePSI) that accounts for state and previous interactions to thwart such attacks.
Methods
The core innovation is the introduction of Reactive Private Set Intersection (RePSI). This is achieved by:
- Modeling PSI as a Reactive Functionality: Instead of stateless interactions, RePSI treats PSI as a stateful process where the output of one execution can depend on previous ones. This allows the server to maintain state and enforce limits across multiple runs.
- Augmented Semi-Honest Model: They define security in the "augmented semi-honest model." This model is crucial because it allows the adversary (the dishonest client) to adaptively change their inputs between protocol runs, which is precisely what's needed to model oracle attacks. Standard semi-honest models don't permit this.
- Constructions:
- Bounded Input PSI: This is a stepping stone, a stateless PSI protocol that limits the size of the client's input in a single execution. It's notable for being the first practical Size-Hiding PSI (SHI-PSI) protocol in the standard model (not relying on random oracles), which is a significant contribution in itself.
- Input Controlling RePSI: This is the main reactive construction. It builds upon Bounded Input PSI and introduces state to limit the total number of unique elements a client can use across all executions. This directly counters the oracle attack by preventing the client from incrementally learning the server's set.
- Cryptographic Primitives: The constructions heavily rely on bilinear accumulators and Smooth Projective Hash Functions (SPHF). These primitives are used to efficiently manage sets and prove membership in a way that allows for privacy and security.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- The Need for Stateful PSI: The paper convincingly argues that stateless security models are insufficient for practical, repeated use of PSI, highlighting the vulnerability to oracle attacks.
- RePSI as a Solution: Modeling PSI as a reactive, stateful primitive is a natural and effective way to address these attacks. The server can leverage state to enforce limits on client behavior over time.
- Augmented Semi-Honest Model is Key: This model is essential for capturing the adaptive nature of oracle attacks where the adversary can change inputs between rounds.
- SPHF for Privacy and Efficiency: The use of SPHFs, particularly in conjunction with bilinear accumulators, is a clever way to achieve the desired security properties (like size-hiding) while maintaining practical efficiency. It allows the client to verify matches without revealing its entire input or the server's entire set.
- First Standard Model SHI-PSI: The Bounded Input PSI construction is a notable achievement as it provides size-hiding PSI without relying on the random oracle model, which is often a practical limitation.
Key Results
- Formalization of Reactive PSI (RePSI): The paper introduces a new security model and definition for RePSI.
- Two Constructions:
- Bounded Input PSI: A stateless, size-hiding PSI protocol in the standard model.
- Input Controlling RePSI: A stateful RePSI protocol that prevents oracle attacks by limiting the total number of unique client inputs across multiple executions.
- Security Guarantees: Both constructions are proven secure in the augmented semi-honest model under standard cryptographic assumptions (q-SDH and q-DBDHI).
- Efficiency: The proposed constructions are shown to be efficient, with constant state for both parties in the Input Controlling RePSI, independent of the number of runs.
Limitations and Future Work
- Semi-Honest Model: The security proofs are provided in the augmented semi-honest model. The authors acknowledge that extending this to the fully malicious model is a significant open problem, though they suggest existing generic transformations might be applicable.
- General RePSI Functionalities: While the paper focuses on RePSI for PSI, the definitions are general enough to capture other reactive functionalities. Future work could explore these.
- Comparison with DMV13: The paper compares its Input Controlling RePSI to the "rate-hiding" compiler from [DMV13]. While [DMV13] offers a more general approach, the authors note that their specific construction for PSI is more efficient in terms of state and communication, especially for the client. Further exploration of the trade-offs and practical implications of these different approaches could be valuable.
Summary updated