Entanglement-Resistant Two-Prover Interactive Proof Systems and Non-Adaptive Private Information Retrieval Systems

Richard Cleve, Dmitry Gavinsky, Rahul Jain

We show that, for any language in NP, there is an entanglement-resistant constant-bit two-prover interactive proof system with a constant completeness vs. soundness gap. The previo…