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

We present VeriSimplePIR, a verifiable version of the stateof-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 Sim-plePIR. The online communication overhead is roughly 1.1-1.5× 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. Proof. This follows from lemma B.3 along with the correctness of the VLHE parameters. Lemma B.3 guarantees that the only ciphertexts that pass verification with probability better than 2 -λ are the honest ciphertexts. Decryption of the honest ciphertext will yield the correct result with probability at least 1 -2 -λ by lemma 2.5. Therefore, the second bit b in the distributions in definition A.4 are also simulatable.