Approximate Lower Bound Arguments

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.

Based on https://eprint.iacr.org/2023/1655. Joint work with Pyrros
Chaidos, Aggelos Kiayias and Leonid Reyzin.