On computational shortcuts for information-theoretic PIR

Matthew M. Hong, Yuval Ishai, Victor I. Kolobov*, Russell W.F. Lai

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

2 Citations (Scopus)


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.

Original languageEnglish
Title of host publicationTheory of Cryptography - 18th International Conference, TCC 2020, Proceedings
EditorsRafael Pass, Krzysztof Pietrzak
Number of pages31
ISBN (Print)9783030643744
Publication statusPublished - 2020
MoE publication typeA4 Conference publication
EventTheory of Cryptography Conference - Durham, United States
Duration: 16 Nov 202019 Nov 2020
Conference number: 18

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12550 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


ConferenceTheory of Cryptography Conference
Abbreviated titleTCCC
Country/TerritoryUnited States


Dive into the research topics of 'On computational shortcuts for information-theoretic PIR'. Together they form a unique fingerprint.

Cite this