Bootle, J;
Groth, J;
(2018)
Efficient Batch Zero-Knowledge Arguments for Low Degree Polynomials.
In:
PKC 2018: Public-Key Cryptography – PKC 2018.
(pp. pp. 561-588).
Springer Verlag
Preview |
Text
0-main.pdf - Accepted Version Download (498kB) | Preview |
Abstract
Bootle et al. (EUROCRYPT 2016) construct an extremely efficient zero-knowledge argument for arithmetic circuit satisfiability in the discrete logarithm setting. However, the argument does not treat relations involving commitments, and furthermore, for simple polynomial relations, the complex machinery employed is unnecessary. In this work, we give a framework for expressing simple relations between commitments and field elements, and present a zero-knowledge argument which, by contrast with Bootle et al., is constant-round and uses fewer group operations, in the case where the polynomials in the relation have low degree. Our method also directly yields a batch protocol, which allows many copies of the same relation to be proved and verified in a single argument more efficiently with only a square-root communication overhead in the number of copies. We instantiate our protocol with concrete polynomial relations to construct zero-knowledge arguments for membership proofs, polynomial evaluation proofs, and range proofs. Our work can be seen as a unified explanation of the underlying ideas of these protocols. In the instantiations of membership proofs and polynomial evaluation proofs, we also achieve better efficiency than the state of the art.
| Type: | Proceedings paper |
|---|---|
| Title: | Efficient Batch Zero-Knowledge Arguments for Low Degree Polynomials |
| Event: | PKC 2018 - International Conference on Practice and Theory of Public Key Cryptography |
| Location: | Rio de Janeiro, Brazil |
| Dates: | 25 March 2018 - 29 March 2018 |
| ISBN: | 9783319765808 |
| ISBN-13: | 9783319765815 |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1007/978-3-319-76581-5_19 |
| Publisher version: | http://dx.doi.org/10.1007/978-3-319-76581-5_19 |
| Language: | English |
| Additional information: | © International Association for Cryptologic Research 2018. This version is the author accepted manuscript. For information on re-use, please refer to the publisher’s terms and conditions. |
| Keywords: | Sigma-protocol; Zero-knowledge argument; Batch-verification; Discrete logarithm assumption |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science |
| URI: | https://discovery.ucl.ac.uk/id/eprint/10045412 |
Loading...
Loading...Loading...Loading...Archive Staff Only
 |
View Item |
