CryptoDB
Amortizing Circuit-PSI in the Multiple Sender/Receiver Setting
| Authors: |
|
|---|---|
| Download: | |
| Abstract: | Private set intersection (PSI) is a cryptographic functionality for two parties to learn the intersection of their input sets, without leaking any other information. Circuit-PSI is a stronger PSI functionality where the parties learn only a secret-shared form of the desired intersection, thus without revealing the intersection directly. These secret shares can subsequently serve as input to a secure multiparty computation of any function on this intersection. In this paper we consider several settings in which parties take part in multiple Circuit-PSI executions with the same input set, and aim to amortize communications and computations. To that end, we build up a new framework for Circuit-PSI around generalizations of oblivious (programmable) PRFs that are extended with offline setup phases. We present several efficient instantiations of this framework with new security proofs for this setting. As a side result, we obtain a slight improvement in communication and computation complexity over the state-of-the-art semi-honest Circuit-PSI protocol by Bienstock et al. (USENIX '23). Additionally, we present a novel Circuit-PSI protocol from a PRF with secret-shared outputs, which has linear communication and computation complexity in the parties' input set sizes, and is able to realize a stronger security notion. Lastly, we derive the potential amortizations over multiple protocol executions, and observe that each of the presented instantiations is favorable in at least one of the multiple-execution settings. |
BibTeX
@article{cic-2024-34813,
title={Amortizing Circuit-PSI in the Multiple Sender/Receiver Setting},
journal={cic},
publisher={International Association for Cryptologic Research},
volume={1, Issue 3},
url={https://cic.iacr.org//p/1/3/2},
doi={10.62056/a0fhsgvtw},
author={Aron van Baarsen and Marc Stevens},
year=2024
}