TY - GEN
T1 - Private Join and Compute from PIR with Default
AU - Lepoint, Tancrède
AU - Patel, Sarvar
AU - Raykova, Mariana
AU - Seth, Karn
AU - Trieu, Ni
N1 - Publisher Copyright:
© 2021, International Association for Cryptologic Research.
PY - 2021
Y1 - 2021
N2 - The private join and compute (PJC) functionality enables secure computation over data distributed across different databases, and is applicable to 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 28 PIR with default lookups on a database of size 225 (or inner-product PJC on databases with such sizes) with the communication of 44 MB, which costs less than 0.17 c. for the client and 26.48 c. for the server.
AB - The private join and compute (PJC) functionality enables secure computation over data distributed across different databases, and is applicable to 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 28 PIR with default lookups on a database of size 225 (or inner-product PJC on databases with such sizes) with the communication of 44 MB, which costs less than 0.17 c. for the client and 26.48 c. for the server.
UR - http://www.scopus.com/inward/record.url?scp=85121916578&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85121916578&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-92075-3_21
DO - 10.1007/978-3-030-92075-3_21
M3 - Conference contribution
AN - SCOPUS:85121916578
SN - 9783030920746
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 605
EP - 634
BT - Advances in Cryptology – ASIACRYPT 2021 - 27th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings, Part 2
A2 - Tibouchi, Mehdi
A2 - Wang, Huaxiong
PB - Springer Science and Business Media Deutschland GmbH
T2 - 27th International Conference on Theory and Application of Cryptology and Information Security, ASIACRYPT 2021
Y2 - 6 December 2021 through 10 December 2021
ER -