Paper 2021/1113

On the Security of Doubly Efficient PIR

Elette Boyle, Justin Holmgren, Fermi Ma, and Mor Weiss


Doubly Efficient Private Information Retrieval (DEPIR) enables queries to an externally held database while hiding the identity of the queried indices, strengthening standard Private Information Retrieval (Chor, Goldreich, Kushilevitz, Sudan FOCS'95) with an efficiency requirement that the computational demands of both client and server are sublinear in the database size. The first DEPIR candidate constructions were recently put forth, based on a new type of assumption relating to indistinguishability of moderate-degree polynomials from random functions when given permuted versions of their evaluation graphs (Boyle, Ishai, Pass, Wootters TCC'17 and Canetti, Holmgren, Richelson TCC'17). To aid in the cryptanalytic study of this new assumption, the work of (BIPW TCC'17) put forth a simpler ``toy conjecture'' variant. In this note, we present an attack that provably breaks the BIPW TCC'17 toy conjecture. The attack identifies a natural embedding of permuted samples into a higher-dimensional linear space for which permuted polynomial samples will be rank deficient. We note, however, that our attack does not apply to the real assumption underlying the constructions, and thus the candidates still stand. We discuss extensions of the attack and present an alternative ``new toy conjecture'' for future study. Similar results were independently obtained by (Blackwell and Wootters, ArXiv'21).

Available format(s)
Publication info
Preprint. MINOR revision.
private information retrieval
Contact author(s)
justin holmgren @ ntt-research com
2021-09-03: received
Short URL
Creative Commons Attribution


      author = {Elette Boyle and Justin Holmgren and Fermi Ma and Mor Weiss},
      title = {On the Security of Doubly Efficient {PIR}},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1113},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.