TY - GEN
T1 - Proof-Carrying Data Without Succinct Arguments
AU - Bünz, Benedikt
AU - Chiesa, Alessandro
AU - Lin, William
AU - Mishra, Pratyush
AU - Spooner, Nicholas
N1 - Funding Information:
Acknowledgements. This research was supported in part by the Ethereum Foundation, NSF, DARPA, a grant from ONR, and the Simons Foundation. Nicholas Spooner was supported by DARPA under Agreement No. HR00112020023.
Publisher Copyright:
© 2021, International Association for Cryptologic Research.
PY - 2021
Y1 - 2021
N2 - Proof-carrying data (PCD) is a powerful cryptographic primitive that enables mutually distrustful parties to perform distributed computations that run indefinitely. Known approaches to construct PCD are based on succinct non-interactive arguments of knowledge (SNARKs) that have a succinct verifier or a succinct accumulation scheme. In this paper we show how to obtain PCD without relying on SNARKs. We construct a PCD scheme given any non-interactive argument of knowledge (e.g., with linear-size arguments) that has a split accumulation scheme, which is a weak form of accumulation that we introduce. Moreover, we construct a transparent non-interactive argument of knowledge for R1CS whose split accumulation is verifiable via a (small) constant number of group and field operations. Our construction is proved secure in the random oracle model based on the hardness of discrete logarithms, and it leads, via the random oracle heuristic and our result above, to concrete efficiency improvements for PCD. Along the way, we construct a split accumulation scheme for Hadamard products under Pedersen commitments and for a simple polynomial commitment scheme based on Pedersen commitments. Our results are supported by a modular and efficient implementation.
AB - Proof-carrying data (PCD) is a powerful cryptographic primitive that enables mutually distrustful parties to perform distributed computations that run indefinitely. Known approaches to construct PCD are based on succinct non-interactive arguments of knowledge (SNARKs) that have a succinct verifier or a succinct accumulation scheme. In this paper we show how to obtain PCD without relying on SNARKs. We construct a PCD scheme given any non-interactive argument of knowledge (e.g., with linear-size arguments) that has a split accumulation scheme, which is a weak form of accumulation that we introduce. Moreover, we construct a transparent non-interactive argument of knowledge for R1CS whose split accumulation is verifiable via a (small) constant number of group and field operations. Our construction is proved secure in the random oracle model based on the hardness of discrete logarithms, and it leads, via the random oracle heuristic and our result above, to concrete efficiency improvements for PCD. Along the way, we construct a split accumulation scheme for Hadamard products under Pedersen commitments and for a simple polynomial commitment scheme based on Pedersen commitments. Our results are supported by a modular and efficient implementation.
KW - Accumulation schemes
KW - Proof-carrying data
KW - Recursive proof composition
UR - http://www.scopus.com/inward/record.url?scp=85115123469&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85115123469&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-84242-0_24
DO - 10.1007/978-3-030-84242-0_24
M3 - Conference contribution
AN - SCOPUS:85115123469
SN - 9783030842413
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 681
EP - 710
BT - Advances in Cryptology – CRYPTO 2021 - 41st Annual International Cryptology Conference, CRYPTO 2021, Proceedings
A2 - Malkin, Tal
A2 - Peikert, Chris
PB - Springer Science and Business Media Deutschland GmbH
T2 - 41st Annual International Cryptology Conference, CRYPTO 2021
Y2 - 16 August 2021 through 20 August 2021
ER -