UCL Discovery
UCL home » Library Services » Electronic resources » UCL Discovery

Sub-linear lattice-based zero-knowledge arguments for arithmetic circuits

Baum, C; Bootle, J; Cerulli, A; del Pino, R; Groth, J; Lyubashevsky, V; (2018) Sub-linear lattice-based zero-knowledge arguments for arithmetic circuits. In: Shacham, H and Boldyreva, A, (eds.) Advances in Cryptology – CRYPTO 2018: 38th Annual International Cryptology Conference, Proceedings, Part II. (pp. pp. 669-699). Springer: Cham, Switzerland. Green open access

[img]
Preview
Text
latticeAC.pdf - Accepted version

Download (539kB) | Preview

Abstract

We propose the first zero-knowledge argument with sub-linear communication complexity for arithmetic circuit satisfiability over a prime p whose security is based on the hardness of the short integer solution (SIS) problem. For a circuit with N gates, the communication complexity of our protocol is O(Nλlog3N−−−−−−−−√) , where λ is the security parameter. A key component of our construction is a surprisingly simple zero-knowledge proof for pre-images of linear relations whose amortized communication complexity depends only logarithmically on the number of relations being proved. This latter protocol is a substantial improvement, both theoretically and in practice, over the previous results in this line of research of Damgård et al. (CRYPTO 2012), Baum et al. (CRYPTO 2016), Cramer et al. (EUROCRYPT 2017) and del Pino and Lyubashevsky (CRYPTO 2017), and we believe it to be of independent interest.

Type: Proceedings paper
Title: Sub-linear lattice-based zero-knowledge arguments for arithmetic circuits
Event: CRYPTO 2018, 38th Annual International Cryptology Conference, 19-23 August 2018, Santa Barbara, California, USA
ISBN-13: 9783319968803
Open access status: An open access version is available from UCL Discovery
DOI: 10.1007/978-3-319-96881-0_23
Publisher version: https://doi.org/10.1007/978-3-319-96881-0
Language: English
Additional information: 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, Arithmetic circuit, SIS assumption
UCL classification: UCL
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: https://discovery.ucl.ac.uk/id/eprint/10059121
Downloads since deposit
194Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item