UCL logo

UCL Discovery

UCL home » Library Services » Electronic resources » UCL Discovery

Efficient Batch Zero-Knowledge Arguments for Low Degree Polynomials

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 Green open access

[img]
Preview
Text
0-main.pdf - ["content_typename_Accepted version" not defined]

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 > Provost and Vice Provost Offices
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: http://discovery.ucl.ac.uk/id/eprint/10045412
Downloads since deposit
30Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item