Paper 2023/1804

Fully Malicious Authenticated PIR

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

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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
PIRPrivate Information Retrieval
Contact author(s)
mariand @ cs washington edu
tessaro @ cs washington edu
History
2023-11-24: approved
2023-11-22: received
See all versions
Short URL
https://ia.cr/2023/1804
License
Creative Commons Attribution
CC BY

BibTeX

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