Nothing Refreshes Like a RePSI: Reactive Private Set Intersection

Andrea Cerulli, Emiliano De Cristofaro, Claudio Soriente

TL;DR

This paper introduces "Reactive Private Set Intersection" (RePSI), a novel cryptographic primitive designed to address "oracle attacks" in standard Private Set Intersection (PSI). By making PSI stateful, RePSI allows servers to limit the cumulative number of unique inputs a client can use across multiple interactions, thereby enhancing security and practical deployment.

What Problem Does This Paper Address?

Private Set Intersection (PSI) is a cryptographic technique that allows two parties to compute the intersection of their private sets without revealing any information beyond the intersection itself. A common limitation of existing PSI protocols is their vulnerability to "oracle attacks." In these attacks, a malicious client can repeatedly query a PSI protocol with slightly modified inputs, gradually learning the server's entire set. While not a violation of traditional security definitions, this significantly hampers real-world applications where servers might have static or slowly changing datasets. Existing PSI protocols struggle to prevent this leakage because they are typically stateless and don't allow the server to track or limit a client's cumulative input history across multiple interactions.

Methods

The core contribution is the introduction of Reactive Private Set Intersection (RePSI). This is achieved by:

  • Modeling PSI as a Reactive Functionality: Instead of a single-shot computation, PSI is modeled as a sequence of stateful interactions where the output of one round can depend on previous ones.
  • Augmented Semi-Honest Model: Security is defined in an augmented semi-honest model. This model allows an adversary to adaptively change the inputs of the corrupted party between protocol runs, which is crucial for modeling oracle attacks.
  • Bounded Input PSI (BIPSI): As a building block, the paper presents a construction for Bounded Input PSI. This protocol limits the size of the client's input set within a single execution. It cleverly uses cryptographic accumulators and Smooth Projective Hash Functions (SPHFs) to achieve size-hiding PSI in the standard model, removing the need for random oracles found in prior work.
  • Input Controlling RePSI: This is the main construction that extends BIPSI to the reactive setting. It allows the server to control the total number of unique inputs a client has used across all previous executions. This is achieved by maintaining state, specifically by accumulating the union of all client inputs seen so far.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Statefulness is Key to Countering Oracle Attacks: The fundamental insight is that to prevent clients from learning a server's set through repeated queries, the protocol needs to remember past interactions. RePSI introduces this necessary statefulness.
  • Cumulative Input Control: The novel concept of "Input Controlling RePSI" allows servers to limit the cumulative number of unique client inputs over time, not just within a single interaction. This directly tackles the gradual leakage problem of oracle attacks.
  • SPHFs as a Replacement for Random Oracles: The paper demonstrates how Smooth Projective Hash Functions (SPHFs), based on bilinear pairings and the q-DBDHI assumption, can replace random oracles in achieving size-hiding PSI. This leads to constructions in the standard model, which is a significant practical improvement.
  • Bridging Semi-Honest and Malicious Models: The use of the augmented semi-honest model provides a natural framework for studying reactive functionalities and composing protocols, acting as a stepping stone towards more robust security definitions.

Key Results

  • Formalization of Reactive PSI (RePSI): The paper defines RePSI and its security model (correctness, client privacy, server privacy) in the augmented semi-honest model.
  • First Size-Hiding PSI in the Standard Model: The paper presents a practical construction for Size-Hiding PSI (SHI-PSI) in the standard model, which is a notable contribution independent of the RePSI concept.
  • Bounded Input PSI (BIPSI) Construction: A protocol that limits the client's input size per execution, serving as a foundation for RePSI.
  • Input Controlling RePSI Construction: A stateful protocol that limits the cumulative number of unique client inputs across multiple executions, effectively mitigating oracle attacks.
  • Efficiency Analysis: The paper provides a detailed efficiency analysis, showing that the RePSI constructions maintain constant state for both client and server, 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 future direction.
  • Comparison with [DMV13]: While the paper compares its approach to [DMV13]'s "rate-limited SFE," a direct complexity comparison is difficult because [DMV13] only hints at how to build a rate-hiding PSI. The authors suggest that their RePSI offers constant state for both parties, which is an advantage.
  • Practical Deployment: While the constructions are in the standard model, further research into practical implementation and performance tuning for real-world scenarios would be beneficial.

Summary updated

BibTeX
@article{cerulli2018nothing,
  author = {Andrea Cerulli and Emiliano De Cristofaro and Claudio Soriente},
  title = {{Nothing Refreshes Like a RePSI: Reactive Private Set Intersection}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2018},
  url = {https://openreview.net/forum?id=y2iJY8cPmF},
}

Loading related content...

Figure