# Approximate Lower Bound Arguments

#### Speaker

Tolik Zinovyev

Boston University

#### Host

Alexandra Henzinger

CSAIL MIT

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.

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.