International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Approximate Lower Bound Arguments

Authors:
Pyrros Chaidos , National & Kapodistrian University of Athens, IOG
Aggelos Kiayias , University of Edinburgh and IOG
Leonid Reyzin , Boston University
Anatoliy Zinovyev , Boston University
Download:
DOI: 10.1007/978-3-031-58737-5_3 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: EUROCRYPT 2024
Abstract: Suppose a prover, in possession of a large body of valuable evidence, wants to quickly convince a verifier by presenting only a small portion of the evidence. We define an Approximate Lower Bound Argument, or ALBA, which allows the prover to do just that: to succinctly prove knowledge of a large number of elements satisfying a predicate (or, more generally, elements of a sufficient total weight when a predicate is generalized to a weight function). The argument is approximate because there is a small gap between what the prover actually knows and what the verifier is convinced the prover knows. This gap enables very efficient schemes. We present noninteractive constructions of ALBA in the random oracle and Uniform Random String models and show that our proof sizes are nearly optimal. We also show how our constructions can be made particularly communication-efficient when the evidence is distributed among multiple provers working together, which is of practical importance when ALBA is applied to a decentralized setting. We demonstrate two very different applications of ALBAs: for large-scale decentralized signatures and for achieving universal composability in general-purpose succinct proof systems (SNARKs).
BibTeX
@inproceedings{eurocrypt-2024-33987,
  title={Approximate Lower Bound Arguments},
  publisher={Springer-Verlag},
  doi={10.1007/978-3-031-58737-5_3},
  author={Pyrros Chaidos and Aggelos Kiayias and Leonid Reyzin and Anatoliy Zinovyev},
  year=2024
}