Paper 2018/344
Nothing Refreshes Like a RePSI: Reactive Private Set Intersection
Andrea Cerulli and Emiliano De Cristofaro and Claudio Soriente
Abstract
Private Set Intersection (PSI) is a popular cryptographic primitive that allows two parties, a client and a server, to compute the intersection of their private sets, so that the client only receives the output of the computation, while the server learns nothing besides the size of the client's set. A common limitation of PSI is that a dishonest client can progressively learn the server's set by enumerating it over different executions. Although these ``oracle attacks'' do not formally violate security according to traditional secure computation definitions, in practice, they often hamper real-life deployment of PSI instantiations, especially if the server's set does not change much over multiple interactions. In a first step to address this problem, this paper presents and studies the concept of Reactive PSI (RePSI). We model PSI as a reactive functionality, whereby the output depends on previous instances, and use it to limit the effectiveness of oracle attacks. We introduce a general security model for RePSI in the (augmented) semi-honest model and a construction which enables the server to control how many inputs have been used by the client across several executions. In the process, we also present the first construction of a Size-Hiding PSI (SHI-PSI) protocol in the standard model, which may be of independent interest.
Metadata
- Available format(s)
- Publication info
- Published elsewhere. Minor revision. ACNS 2018
- Keywords
- private set intersectionreactive functionalities
- Contact author(s)
- me @ emilianodc com
- History
- 2018-06-01: revised
- 2018-04-16: received
- See all versions
- Short URL
- https://ia.cr/2018/344
- License
-
CC BY