Linear-Time Accumulation Schemes
Giacomo Fenzi
Abstract:
Proof-carrying data (PCD) is a powerful cryptographic primitive for computational integrity in a distributed setting. State-of-the-art constructions of PCD are based on accumulation schemes (and, closely related, folding schemes). We present WARP [1]: the first accumulation scheme with linear prover time and logarithmic verifier complexity. Our scheme is hash-based (secure in the random oracle model), plausibly post-quantum secure, and supports unbounded accumulation depth. We achieve our result by constructing an interactive oracle reduction of proximity that works with any linear code over a sufficiently large field. Along the way, we introduce a new notion of straight line round-by-round knowledge soundness that is compatible with linear error correcting codes without efficient (error-tolerant) decoding algorithms.
Bio:
Giacomo Fenzi is a PhD student in the COMPSEC Lab at EPFL. His research is on cryptography and theoretical computer science, focusing on proof systems. He studies how to make zkSNARKs that are theoretically and concretely efficient, from post-quantum cryptographic primitives.