Quadratic span programs and succinct NIZKs without PCPs. (English) Zbl 1300.94056
Johansson, Thomas (ed.) et al., Advances in cryptology – EUROCRYPT 2013. 32nd annual international conference on the theory and applications of cryptographic techniques, Athens, Greece, May 26–30, 2013. Proceedings. Berlin: Springer (ISBN 978-3-642-38347-2/pbk). Lecture Notes in Computer Science 7881, 626-645 (2013).
Summary: We introduce a new characterization of the NP complexity class, called quadratic span programs (QSPs), which is a natural extension of span programs defined by M. Karchmer and A. Wigderson [On span programs. In: Structure in Complexity Theory Conference, 102–111 (1993)]. Our main motivation is the quick construction of succinct, easily verified arguments for NP statements.
To achieve this goal, QSPs use a new approach to the well-known technique of arithmetization of Boolean circuits. Our new approach yields dramatic performance improvements. Using QSPs, we construct a NIZK argument – in the CRS model – for circuit-SAT consisting of just 7 group elements. The CRS size and prover computation are quasi-linear, making our scheme seemingly quite practical, a result supported by our implementation. Indeed, our NIZK argument attains the shortest proof, most efficient prover, and most efficient verifier of any known technique. We also present a variant of QSPs, called quadratic arithmetic programs (QAPs), that “naturally” compute arithmetic circuits over large fields, along with succinct NIZK constructions that use QAPs.
Finally, we show how QSPs and QAPs can be used to efficiently and publicly verify outsourced computations, where a client asks a server to compute \(F(x)\) for a given function \(F\) and must verify the result provided by the server in considerably less time than it would take to compute \(F\) from scratch. The resulting schemes are the most efficient, general purpose publicly verifiable computation schemes.
For the entire collection see [Zbl 1263.94005].
To achieve this goal, QSPs use a new approach to the well-known technique of arithmetization of Boolean circuits. Our new approach yields dramatic performance improvements. Using QSPs, we construct a NIZK argument – in the CRS model – for circuit-SAT consisting of just 7 group elements. The CRS size and prover computation are quasi-linear, making our scheme seemingly quite practical, a result supported by our implementation. Indeed, our NIZK argument attains the shortest proof, most efficient prover, and most efficient verifier of any known technique. We also present a variant of QSPs, called quadratic arithmetic programs (QAPs), that “naturally” compute arithmetic circuits over large fields, along with succinct NIZK constructions that use QAPs.
Finally, we show how QSPs and QAPs can be used to efficiently and publicly verify outsourced computations, where a client asks a server to compute \(F(x)\) for a given function \(F\) and must verify the result provided by the server in considerably less time than it would take to compute \(F\) from scratch. The resulting schemes are the most efficient, general purpose publicly verifiable computation schemes.
For the entire collection see [Zbl 1263.94005].
