Polynomial Representation Is Tricky: Maliciously Secure Private Set Intersection Revisited

Aydin Abadi; Steven J.  Murdoch; Thomas Zacharias

Paper 2021/1009

Polynomial Representation Is Tricky: Maliciously Secure Private Set Intersection Revisited

Aydin Abadi, Steven J. Murdoch, and Thomas Zacharias

Abstract

Private Set Intersection protocols (PSIs) allow parties to compute the intersection of their private sets, such that nothing about the sets’ elements beyond the intersection is revealed. PSIs have a variety of applications, primarily in efficiently supporting data sharing in a privacy-preserving manner. At Eurocrypt 2019, Ghosh and Nilges pro- posed three efficient PSIs based on the polynomial representation of sets and proved their security against active adversaries. In this work, we show that these three PSIs are susceptible to several serious attacks. The attacks let an adversary (1) learn the correct intersection while making its victim believe that the intersection is empty, (2) learn a certain element of its victim’s set beyond the intersection, and (3) delete multiple elements of its victim’s input set. We explain why the proofs did not identify these attacks and propose a set of mitigations

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Preprint. MINOR revision.
Keywords: Private Set Intersection Multi-party Computation Cryptographic Protocols Cryptanalysis
Contact author(s): aydin abadi @ ucl ac uk
s murdoch @ ucl ac uk
thomas zacharias @ ed ac uk
History: 2021-08-06: received
Short URL: https://ia.cr/2021/1009
License: CC BY

BibTeX

@misc{cryptoeprint:2021/1009,
      author = {Aydin Abadi and Steven J.  Murdoch and Thomas Zacharias},
      title = {Polynomial Representation Is Tricky: Maliciously Secure Private Set Intersection Revisited},
      howpublished = {Cryptology {ePrint} Archive, Paper 2021/1009},
      year = {2021},
      url = {https://eprint.iacr.org/2021/1009}
}