Paper 2020/1429
On Computational Shortcuts for Information-Theoretic PIR
Abstract
Information-theoretic private information retrieval (PIR) schemes have attractive concrete efficiency features. However, in the standard PIR model, the computational complexity of the servers must scale linearly with the database size. We study the possibility of bypassing this limitation in the case where the database is a truth table of a "simple" function, such as a union of (multi-dimensional) intervals or convex shapes, a decision tree, or a DNF formula. This question is motivated by the goal of obtaining lightweight homomorphic secret sharing (HSS) schemes and secure multiparty computation (MPC) protocols for the corresponding families. We obtain both positive and negative results. For "first-generation" PIR schemes based on Reed-Muller codes, we obtain computational shortcuts for the above function families, with the exception of DNF formulas for which we show a (conditional) hardness result. For "third-generation" PIR schemes based on matching vectors, we obtain stronger hardness results that apply to all of the above families. Our positive results yield new information-theoretic HSS schemes and MPC protocols with attractive efficiency features for simple but useful function families. Our negative results establish new connections between information-theoretic cryptography and fine-grained complexity.
Note: Correction made to Figure 12.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- A major revision of an IACR publication in TCC 2020
- Keywords
- Information theoretic cryptography secure multiparty computation private information retrieval homomorphic secret sharing fine-grained hardness
- Contact author(s)
-
hoou8547 @ hotmail com
yuvali @ cs technion ac il
kolobov victor @ gmail com
russellnhellman @ gmail com - History
- 2022-05-30: last of 2 revisions
- 2020-11-15: received
- See all versions
- Short URL
- https://ia.cr/2020/1429
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2020/1429,
author = {Matthew M. Hong and Yuval Ishai and Victor I. Kolobov and Russell W. F. Lai},
title = {On Computational Shortcuts for Information-Theoretic {PIR}},
howpublished = {Cryptology {ePrint} Archive, Paper 2020/1429},
year = {2020},
url = {https://eprint.iacr.org/2020/1429}
}
