Paper 2020/1011
Private Join and Compute from PIR with Default
Tancrède Lepoint, Sarvar Patel, Mariana Raykova, Karn Seth, and Ni Trieu
Abstract
The private join and compute (PJC) functionality enables secure computation over data distributed across different databases, which is a functionality with a wide range of applications, many of which address settings where the input databases are of significantly different sizes. We introduce the notion of private information retrieval (PIR) with default, which enables two-party PJC functionalities in a way that hides the size of the intersection of the two databases and incurs sublinear communication cost in the size of the bigger database. We provide two constructions for this functionality, one of which requires offline linear communication, which can be amortized across queries, and one that provides sublinear cost for each query but relies on more computationally expensive tools. We construct inner-product PJC, which has applications to ads conversion measurement and contact tracing, relying on an extension of PIR with default. We evaluate the efficiency of our constructions, which can enable $\mathbf{2^{12}}$ PIR with default lookups on a database of size $\mathbf{2^{30}}$ (or inner-product PJC on databases with such sizes) with the communication of $\mathbf{945}$MB, which costs less than $\mathbf{\$0.04}$ for the client and $\mathbf{\$5.22}$ for the server.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- A minor revision of an IACR publication in ASIACRYPT 2021
- Contact author(s)
- nitrieu @ asu edu
- History
- 2021-10-02: last of 3 revisions
- 2020-08-22: received
- See all versions
- Short URL
- https://ia.cr/2020/1011
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2020/1011,
author = {Tancrède Lepoint and Sarvar Patel and Mariana Raykova and Karn Seth and Ni Trieu},
title = {Private Join and Compute from {PIR} with Default},
howpublished = {Cryptology {ePrint} Archive, Paper 2020/1011},
year = {2020},
url = {https://eprint.iacr.org/2020/1011}
}