Paper 2019/239

Cheaper Private Set Intersection via Differentially Private Leakage

Adam Groce, Peter Rindal, and Mike Rosulek

Abstract

In this work we demonstrate that allowing differentially private leakage can significantly improve the concrete performance of secure 2-party computation (2PC) protocols. Specifically, we focus on the private set intersection (PSI) protocol of Rindal and Rosulek (CCS 2017), which is the fastest PSI protocol with security against malicious participants. We show that if differentially private leakage is allowed, the cost of the protocol can be reduced by up to 63%, depending on the desired level of differential privacy. On the technical side, we introduce a security model for differentially-private leakage in malicious-secure 2PC. We also introduce two new and improved mechanisms for "differentially private histogram overestimates," the main technical challenge for differentially-private PSI.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. PoPETS 2019
Keywords
private set intersectiondifferential privacy
Contact author(s)
rosulekm @ eecs oregonstate edu
History
2019-02-28: received
Short URL
https://ia.cr/2019/239
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/239,
      author = {Adam Groce and Peter Rindal and Mike Rosulek},
      title = {Cheaper Private Set Intersection via Differentially Private Leakage},
      howpublished = {Cryptology ePrint Archive, Paper 2019/239},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/239}},
      url = {https://eprint.iacr.org/2019/239}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.