PIR with polylogarithmic communication ⇒ Designated-verifier delegation for P

CRS model · BHK17

Statement

If a computational PIR scheme with polylogarithmic communication exists, there is an adaptively sound non-interactive delegation scheme for all polynomial-time computations, RAM computations included, with verification in fixed polynomial time: the verifier sets up a public key once, any prover proves arbitrary statements with a single message, and verification uses a secret key, soundness relying on the prover not knowing it — BHK17. BHK17 base the scheme on any computational PIR scheme, which can in turn be based on standard polynomial-time assumptions such as the worst-case hardness of polynomial-factor approximation of short-vector lattice problems — BHK17.

Notes

• The public key is reusable across statements, and verification runs in a fixed polynomial time — BHK17.
• In the same paper, a non-adaptive two-message protocol proves $m$ $\mathbf{NP}$ instances with communication proportional to one witness — BHK17.
• From sub-exponentially secure PIR, every language computable in time $t$ has 1-round delegation with prover time $\mathrm{poly}(t)$ and verifier time $n\cdot \mathrm{polylog}(t)$, by proving the PIR-based compiler of Aiello et al. sound for multi-prover interactive proofs sound against no-signaling provers; polynomial-time such proofs capture exactly $\mathbf{EXP}$ — KRR14.
• Publicly verifiable delegation for P from LWE is LWE with polynomial ratio ⇒ SNARG for P — CJJ21.