Cryptology ePrint Archive: Report 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.

Category / Keywords: private set intersection, reactive functionalities

Original Publication (with minor differences): ACNS 2018

Date: received 13 Apr 2018, last revised 14 Apr 2018

Contact author: me at emilianodc com

Available format(s): PDF | BibTeX Citation

Version: 20180416:212554 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]