eprintid: 10063978
rev_number: 26
eprint_status: archive
userid: 608
dir: disk0/10/06/39/78
datestamp: 2021-11-24 17:31:36
lastmod: 2021-11-24 23:21:17
status_changed: 2021-11-24 17:31:36
type: proceedings_section
metadata_visibility: show
creators_name: Bootle, J
creators_name: Cerulli, A
creators_name: Groth, J
creators_name: Jakobsen, S
creators_name: Maller, M
title: Arya: Nearly linear-time zero-knowledge proofs for correct program execution
ispublished: pub
divisions: UCL
divisions: B04
divisions: C05
divisions: F48
keywords: Zero-knowledge proofs, Succinct arguments of knowledge, TinyRAM, Ideal linear commitments, Post-quantum security
note: This version is the author accepted manuscript. For information on re-use, please refer to the publisher’s terms and conditions.
abstract: There have been tremendous advances in reducing interaction, communication and verification time in zero-knowledge proofs but it remains an important challenge to make the prover efficient. We construct the first zero-knowledge proof of knowledge for the correct execution of a program on public and private inputs where the prover computation is nearly linear time. This saves a polylogarithmic factor in asymptotic performance compared to current state of the art proof systems.

We use the TinyRAM model to capture general purpose processor computation. An instance consists of a TinyRAM program and public inputs. The witness consists of additional private inputs to the program. The prover can use our proof system to convince the verifier that the program terminates with the intended answer within given time and memory bounds. Our proof system has perfect completeness, statistical special honest verifier zero-knowledge, and computational knowledge soundness assuming linear-time computable collision-resistant hash functions exist. The main advantage of our new proof system is asymptotically efficient prover computation. The prover’s running time is only a superconstant factor larger than the program’s running time in an apples-to-apples comparison where the prover uses the same TinyRAM model. Our proof system is also efficient on the other performance parameters; the verifier’s running time and the communication are sublinear in the execution time of the program and we only use a log-logarithmic number of rounds.
date: 2018-10-27
date_type: published
publisher: Springer
official_url: https://doi.org/10.1007/978-3-030-03326-2_20
oa_status: green
full_text_type: other
language: eng
primo: open
primo_central: open_green
verified: verified_manual
elements_id: 1563386
doi: 10.1007/978-3-030-03326-2_20
isbn_13: 978-3-030-03325-5
lyricists_name: Bootle, Jonathan
lyricists_name: Cerulli, Andrea
lyricists_name: Groth, Jens
lyricists_id: JBOOT21
lyricists_id: ACERU17
lyricists_id: JGROT52
actors_name: Groth, Jens
actors_id: JGROT52
actors_role: owner
full_text_status: public
series: Lecture Notes in Computer Science (LNCS)
volume: 11272
place_of_pub: Cham, Switzerland
pagerange: 595-626
issn: 0302-9743
book_title: Advances in Cryptology – ASIACRYPT 2018: 24th International Conference on the Theory and Application of Cryptology and Information Security, Brisbane, QLD, Australia, December 2–6, 2018, Proceedings, Part I
editors_name: Peyrin, T
editors_name: Galbraith, S
citation:        Bootle, J;    Cerulli, A;    Groth, J;    Jakobsen, S;    Maller, M;      (2018)    Arya: Nearly linear-time zero-knowledge proofs for correct program execution.                     In: Peyrin, T and Galbraith, S, (eds.) Advances in Cryptology – ASIACRYPT 2018: 24th International Conference on the Theory and Application of Cryptology and Information Security, Brisbane, QLD, Australia, December 2–6, 2018, Proceedings, Part I.  (pp. pp. 595-626).  Springer: Cham, Switzerland.       Green open access   
 
document_url: https://discovery.ucl.ac.uk/id/eprint/10063978/1/ZKRAM-Asiacrypt2018-Final.pdf