TY - GEN

T1 - Succinct delegation for low-Space non-deterministic computation

AU - Badrinarayanan, Saikrishna

AU - Kalai, Yael Tauman

AU - Khurana, Dakshita

AU - Sahai, Amit

AU - Wichs, Daniel

PY - 2018/6/20

Y1 - 2018/6/20

N2 - 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 non-interactive 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 sub-exponential LWE, for many natural languages believed to be outside of P.

AB - 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 non-interactive 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 sub-exponential LWE, for many natural languages believed to be outside of P.

KW - Low space

KW - Non-deterministic

KW - Non-interactive delegation

KW - NTISP

KW - SNARG

KW - Succinct proofs

UR - http://www.scopus.com/inward/record.url?scp=85049906896&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85049906896&partnerID=8YFLogxK

U2 - 10.1145/3188745.3188924

DO - 10.1145/3188745.3188924

M3 - Conference contribution

AN - SCOPUS:85049906896

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 267

EP - 280

BT - STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing

A2 - Henzinger, Monika

A2 - Kempe, David

A2 - Diakonikolas, Ilias

PB - Association for Computing Machinery,

T2 - 50th Annual ACM Symposium on Theory of Computing, STOC 2018

Y2 - 25 June 2018 through 29 June 2018

ER -