Paper 2023/1804

Fully Malicious Authenticated PIR

Marian Dietz, University of Washington
Stefano Tessaro, University of Washington

Authenticated PIR enables a server to initially commit to a database of $N$ items, for which a client can later privately obtain individual items with complexity sublinear in $N$, with the added guarantee that the retrieved item is consistent with the committed database. A crucial requirement is privacy with abort, i.e., the server should not learn anything about a query even if it learns whether the client aborts. This problem was recently considered by Colombo et al. (USENIX '23), who proposed solutions secure under the assumption that the database is committed to honestly. Here, we close this gap, and present a solution that tolerates fully malicious servers that provide potentially malformed commitments. Our scheme has communication and client computational complexity $\mathcal{O}_{\lambda}(\sqrt{N})$, solely relies on the DDH assumption, and does not introduce heavy machinery (e.g., generic succinct proofs). Privacy with abort holds provided the server succeeds in correctly answering $\lambda$ validation queries, which, from its perspective, are computationally indistinguishable from regular PIR queries. In fact, server side, our scheme is exactly the DDH-based scheme by Colombo et al.

Available format(s)
Cryptographic protocols
Publication info
PIRPrivate Information Retrieval
Contact author(s)
mariand @ cs washington edu
tessaro @ cs washington edu
2023-11-24: approved
2023-11-22: received
See all versions
Short URL
Creative Commons Attribution


      author = {Marian Dietz and Stefano Tessaro},
      title = {Fully Malicious Authenticated PIR},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1804},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.