Paper 2024/341

VeriSimplePIR: Verifiability in SimplePIR at No Online Cost for Honest Servers

Leo de Castro, Massachusetts Institute of Technology
Keewoo Lee, University of California, Berkeley

We present VeriSimplePIR, a verifiable version of the state-of-the-art semi-honest SimplePIR protocol. VeriSimplePIR is a stateful verifiable PIR scheme guaranteeing that all queries are consistent with a fixed, well-formed database. It is the first efficient verifiable PIR scheme to not rely on an honest digest to ensure security; any digest, even one produced by a malicious server, is sufficient to commit to some database. This is due to our extractable verification procedure, which can extract the entire database from the consistency proof checked against each response. Furthermore, VeriSimplePIR ensures this strong security guarantee without compromising the performance of SimplePIR. The online communication overhead is roughly $1.1$-$1.5\times$ SimplePIR, and the online computation time on the server is essentially the same. We achieve this low overhead via a novel one-time preprocessing protocol that generates a reusable proof that can verify any number of subsequent query-response pairs as long as no malicious behavior is detected. As soon as the verification procedure rejects a response from the server, the offline phase must be rerun to compute a new proof. VeriSimplePIR represents an approach to maliciously secure cryptography that is highly optimized for honest parties while maintaining security even in the presence of malicious adversaries.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Minor revision. USENIX Security '24
Contact author(s)
ldec @ mit edu
keewoole @ gmail com
2024-02-27: approved
2024-02-27: received
See all versions
Short URL
Creative Commons Attribution


      author = {Leo de Castro and Keewoo Lee},
      title = {{VeriSimplePIR}: Verifiability in {SimplePIR} at No Online Cost for Honest Servers},
      howpublished = {Cryptology ePrint Archive, Paper 2024/341},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.