Incremental proofs of sequential work

Döttling N, Lai RWF, Malavolta G (2019)

Publication Type: Conference contribution

Publication year: 2019

Journal

Lecture Notes in Computer Science Springer Verlag

Publisher: Springer Verlag

Book Volume: 11477 LNCS

Pages Range: 292-323

Conference Proceedings Title: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Event location: Darmstadt DE

ISBN: 9783030176556

DOI: 10.1007/978-3-030-17656-3_11

Abstract

A proof of sequential work allows a prover to convince a verifier that a certain amount of sequential steps have been computed. In this work we introduce the notion of incremental proofs of sequential work where a prover can carry on the computation done by the previous prover incrementally, without affecting the resources of the individual provers or the size of the proofs. To date, the most efficient instance of proofs of sequential work [Cohen and Pietrzak, Eurocrypt 2018] for N steps require the prover to have (formula presented) memory and to run for (formula presented) steps. Using incremental proofs of sequential work we can bring down the prover’s storage complexity to log N and its running time to N. We propose two different constructions of incremental proofs of sequential work: Our first scheme requires a single processor and introduces a poly-logarithmic factor in the proof size when compared with the proposals of Cohen and Pietrzak. Our second scheme assumes log N parallel processors but brings down the overhead of the proof size to a factor of 9. Both schemes are simple to implement and only rely on hash functions (modelled as random oracles).

Authors with CRIS profile

Wai Fu Lai Lehrstuhl für Informatik 13 (Angewandte Kryptographie)

Involved external institutions

CISPA − Helmholtz-Zentrum für Informationssicherheit DE Germany (DE) Carnegie Mellon University US United States (USA) (US)

How to cite

APA:

Döttling, N., Lai, R.W.F., & Malavolta, G. (2019). Incremental proofs of sequential work. In Yuval Ishai, Vincent Rijmen (Eds.), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp. 292-323). Darmstadt, DE: Springer Verlag.

MLA:

Döttling, Nico, Russell W. F. Lai, and Giulio Malavolta. "Incremental proofs of sequential work." Proceedings of the 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Eurocrypt 2019, Darmstadt Ed. Yuval Ishai, Vincent Rijmen, Springer Verlag, 2019. 292-323.

BibTeX: Download