Non-Interactive Delegation for Low-Space Non-Deterministic Computation

Saikrishna Badrinarayanan; Yael Tauman Kalai; Dakshita Khurana; Amit Sahai; Daniel Wichs

Paper 2017/1250 Original: eprint.iacr.org/2017/1250 ↗

Non-Interactive Delegation for Low-Space Non-Deterministic Computation

Saikrishna Badrinarayanan

Yael Tauman Kalai

Dakshita Khurana

Amit Sahai

Daniel Wichs

Abstract

We construct a delegation scheme for verifying non-deterministic computations, with complexity proportional only to the non-deterministic space of the computation. Specifically, letting $n$ denote the input length, we construct a delegation scheme for any language verifiable in non-deterministic time and space $(T (n); S(n))$ with communication complexity $poly(S(n))$, verifier runtime $n polylog(T (n)) + poly(S(n))$, and prover runtime $poly(T (n))$. 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.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Preprint.
History: 2018-02-28: last updated; 2017-12-30: published
Short URL: https://ia.cr/2017/1250
License: https://creativecommons.org/licenses/by/4.0/

BibTeX

@misc{cryptoeprint:2017/1250,
      author = {Saikrishna Badrinarayanan and Yael Tauman Kalai and Dakshita Khurana and Amit Sahai and Daniel Wichs},
      title = {Non-Interactive Delegation for Low-Space Non-Deterministic Computation},
      howpublished = {Cryptology {ePrint} Archive, Paper 2017/1250},
      year = {2017},
      url = {https://eprint.iacr.org/2017/1250}
}