Our scheme consists of only two messages and has adaptive soundness, assuming the existence of a sub-exponentially secure private information retrieval (PIR) scheme, which can be instantiated under standard (albeit, sub-exponential) cryptographic assumptions, such as the sub-exponential LWE assumption. Specifically, the verifier publishes a (short) public key ahead of time, and this key can be used by any prover to non-interactively prove the correctness of any adaptively chosen non-deterministic computation. Such a scheme is referred to as a noninteractive delegation scheme. Our scheme is privately verifiable, where the verifier needs the corresponding secret key in order to verify proofs.
Prior to our work, such results were known only in the Random Oracle Model, or under knowledge assumptions. Our results yield succinct non-interactive arguments based on subexponential LWE, for many natural languages believed to be outside of P.
Category / Keywords: foundations / delegation, non-interactive, succinct arguments, non-determinism Date: received 27 Dec 2017, last revised 27 Feb 2018 Contact author: dakshita at cs ucla edu Available format(s): PDF | BibTeX Citation Version: 20180228:023140 (All versions of this report) Short URL: ia.cr/2017/1250 Discussion forum: Show discussion | Start new discussion