Paper 2022/1560

Verifiable Private Information Retrieval

Shany Ben-David, Tel Aviv University
Yael Tauman Kalai, Microsoft Research, Massachusetts Institute of Technology
Omer Paneth, Tel Aviv University

A computational PIR scheme allows a client to privately query a database hosted on a single server without downloading the entire database. We introduce the notion of verifiable PIR (vPIR) where the server can convince the client that the database satisfies certain properties without additional rounds and while keeping the communication sub-linear. For example, the server can prove that the number of rows in the database that satisfy a predicate $P$ is exactly $n$. We define security by modeling vPIR as an ideal functionality and following the real-ideal paradigm. Starting from a standard PIR scheme, we construct a vPIR scheme for any database property that can be verified by a machine that reads the database once and maintains a bounded size state between rows. We also construct vPIR with public verification based on LWE or on DLIN. The main technical hurdle is to demonstrate a simulator that extracts a long input from an adversary that sends a single short message. Our vPIR constructions are based on the notion of batch argument for NP. As contribution of independent interest, we show that batch arguments are equivalent to quasi-arguments---a relaxation of SNARKs which is known to imply succinct argument for various sub-classes of NP.

Available format(s)
Cryptographic protocols
Publication info
Published by the IACR in TCC 2022
Contact author(s)
shanygabizon @ gmail com
yael @ microsoft com
omerpa @ tauex tau ac il
2022-11-10: approved
2022-11-09: received
See all versions
Short URL
Creative Commons Attribution


      author = {Shany Ben-David and Yael Tauman Kalai and Omer Paneth},
      title = {Verifiable Private Information Retrieval},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1560},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.