Welcome to the resource topic for 2022/1560
Title:
Verifiable Private Information Retrieval
Authors: Shany Ben-David, Yael Tauman Kalai, Omer Paneth
Abstract: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.
ePrint: https://eprint.iacr.org/2022/1560
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .