In this work, we present an efficient PIR protocol that combines all of the above techniques to achieve constant amortized communication and computation complexity in the size of the database, and is the first to scale to more than $10^5$ queries per second deployed on an AWS micro instance. Our protocol also builds upon a new secret sharing scheme that is both incremental and non-malleable, which may be of interest to a wider audience. We leverage differentially private leakage in order to provide better trade-offs between privacy and efficiency. Our protocol provides security up to abort against malicious adversaries that can corrupt all but one party.
Category / Keywords: cryptographic protocols / Private Information Retrieval, Secret Sharing, Secure Multiparty Computation, Differential Privacy Date: received 22 Dec 2020 Contact author: kinan_dak_albab at brown edu, ra1issa@bu edu, varia@bu edu Available format(s): PDF | BibTeX Citation Version: 20201224:074020 (All versions of this report) Short URL: ia.cr/2020/1596