Jonathan Bootle
Linear-time zero-knowledge proofs for arithmetic circuit satisfiability
Bootle, Jonathan; Cerulli, Andrea; Ghadafi, Essam; Groth, Jens; Hajiabadi, Mohammad; Jakobsen, Sune K.
Authors
Andrea Cerulli
Essam Ghadafi Essam.Ghadafi@uwe.ac.uk
Senior Lecturer in Computer Science
Jens Groth
Mohammad Hajiabadi
Sune K. Jakobsen
Abstract
We give computationally efficient zero-knowledge proofs of knowledge for arithmetic circuit satisfiability over a large field. For a circuit with N addition and multiplication gates, the prover only uses O(N) multiplications and the verifier only uses O(N) additions in the field. If the commitments we use are statistically binding, our zero-knowledge proofs have unconditional soundness, while if the commitments are statistically hiding we get computational soundness. Our zero-knowledge proofs also have sub-linear communication if the commitment scheme is compact. Our construction proceeds in three steps. First, we give a zero-knowledge proof for arithmetic circuit satisfiability in an ideal linear commitment model where the prover may commit to secret vectors of field elements, and the verifier can receive certified linear combinations of those vectors. Second, we show that the ideal linear commitment proof can be instantiated using error-correcting codes and non-interactive commitments. Finally, by choosing efficient instantiations of the primitives we obtain linear-time zero-knowledge proofs.
Citation
Bootle, J., Cerulli, A., Ghadafi, E., Groth, J., Hajiabadi, M., & Jakobsen, S. K. (2017). Linear-time zero-knowledge proofs for arithmetic circuit satisfiability. In Lecture Notes in Computer Science (336-365). https://doi.org/10.1007/978-3-319-70700-6_12
Conference Name | ASIACRYPT 2017 |
---|---|
Conference Location | Hong Kong, China |
Start Date | Dec 3, 2017 |
End Date | Dec 7, 2017 |
Acceptance Date | Aug 13, 2017 |
Online Publication Date | Nov 17, 2017 |
Publication Date | Dec 31, 2017 |
Deposit Date | Sep 14, 2017 |
Publicly Available Date | Dec 18, 2017 |
Publisher | Springer Verlag |
Peer Reviewed | Peer Reviewed |
Volume | 10626 |
Pages | 336-365 |
Series Title | Advances in Cryptology – ASIACRYPT 2017 |
Series ISSN | 0302-9743 |
Book Title | Lecture Notes in Computer Science |
ISBN | 9783319706993 |
DOI | https://doi.org/10.1007/978-3-319-70700-6_12 |
Keywords | zero-knowledge, arithmetic circuit |
Public URL | https://uwe-repository.worktribe.com/output/876742 |
Publisher URL | https://link.springer.com/bookseries/558 |
Additional Information | Title of Conference or Conference Proceedings : International Conference on the Theory and Applications of Cryptology and Information Security (Asiacrypt 2017) |
Files
872.pdf
(898 Kb)
PDF
You might also like
Feature vulnerability and robustness assessment against adversarial machine learning attacks
(2021)
Conference Proceeding
Partially structure-preserving signatures: Lower bounds, constructions and more
(2021)
Conference Proceeding
Foundations of fully dynamic group signatures
(2020)
Journal Article
Further lower bounds for structure-preserving signatures in asymmetric bilinear groups
(2019)
Conference Proceeding
Downloadable Citations
About UWE Bristol Research Repository
Administrator e-mail: repository@uwe.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search