In this talk, Dario Fiore will give an overview of the Succinct Zero-Knowledge Batch Proofs for Set Accumulators.
Cryptographic accumulators are a common solution to proving information about a large set S. They allow to compute a short digest of S and short certificates of some of its basic properties, notably membership of an element. Accumulators also allow to track set updates: a new accumulator is obtained by inserting/deleting a given element. In this work Dario and his colleagues consider the problem of generating membership and update proofs for {\em batches} of elements so that they can succinctly prove additional properties of the elements (i.e., proofs are of constant size regardless of the batch size), and they can preserve privacy. Solving this problem would allow to obtain blockchain systems with improved privacy and scalability.
The state-of-the-art approach to achieve this goal is to combine accumulators (typically Merkle trees) with zkSNARKs. This solution is however expensive for provers and does not scale for large batches of elements. In particular, there is no scalable solution for proving batch membership proofs when we require zero-knowledge (a standard definition of privacy-preserving protocols).
In this work Dario Fiore and his colleagues propose new techniques to efficiently use zkSNARKs with RSA accumulators. They design and implement two main schemes: 1) HaRiSA, which proves batch membership in zero-knowledge; 2) B-Ins-ARiSA, which proves batch updates. For batch membership, the prover in HaRiSA is orders of magnitude faster than existing approaches based on Merkle trees (depending on the hash function). For batch updates they get similar cost savings compared to approaches based on Merkle trees; they also improve over the recent solution of Ozdemir et al. [USENIX'20].
Dario Fiore is an Associate Research Professor at the IMDEA Software Institute in Madrid. Before joining IMDEA in 2013, he obtained a PhD in computer science from University of Catania in 2010, and then held postdoc positions at the Max Planck Institute for Software Systems in Germany, the New York University in the United States, and the École Normale Supérieure of Paris in France. Dario’s research interests are on theoretical and practical aspects of cryptography, and its applications to security and privacy. He is a recipient of an ERC Consolidator Grant in 2020, and he co-authored over 50 peer-reviewed research papers that have been published in flagship international conferences and journals in the areas of Cryptography and Security, and have attracted so far over 3000 citations.
