Approximate Lower Bound Arguments

Pyrros Chaidos; Aggelos Kiayias; Leonid Reyzin; Anatoliy Zinovyev

Paper 2023/1655

Approximate Lower Bound Arguments

Pyrros Chaidos, National & Kapodistrian University of Athens, IOG

Aggelos Kiayias, University of Edinburgh, IOG

Leonid Reyzin

, Boston University

Anatoliy Zinovyev, Boston University

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 reference 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, 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 proving universal composability of succinct proofs.

Note: Removed limitation on n_p, optimized expected and worst case prover running time, improved numbers for the proof size - communication tradeoff.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: A major revision of an IACR publication in EUROCRYPT 2024
DOI: 10.1007/978-3-031-58737-5_3
Contact author(s): pyrros @ gmail com
Aggelos Kiayias @ ed ac uk
leonid reyzin @ gmail com
tolik @ bu edu
History: 2024-05-26: revised; 2023-10-25: received; See all versions
Short URL: https://ia.cr/2023/1655
License: CC BY

BibTeX

@misc{cryptoeprint:2023/1655,
      author = {Pyrros Chaidos and Aggelos Kiayias and Leonid Reyzin and Anatoliy Zinovyev},
      title = {Approximate Lower Bound Arguments},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/1655},
      year = {2023},
      doi = {10.1007/978-3-031-58737-5_3},
      url = {https://eprint.iacr.org/2023/1655}
}