Paper 2024/2026

Orbweaver: Succinct Linear Functional Commitments from Lattices

Abstract

We present Orbweaver, a plausibly post-quantum functional commitment for linear relations that achieves quasilinear prover time together with $O(\log n)$ proof size and polylogarithmic verifier time. Orbweaver enables evaluation of linear functions on committed vectors over cyclotomic rings and the integers. It is extractable, preprocessing, non-interactive, structure-preserving, and supports compact public proof aggregation. The security of our scheme is based on the $$-$$-ISIS assumption (and its knowledge counterpart), whereby we require a trusted setup to generate a universal structured reference string. We use Orbweaver to construct succinct univariate and multilinear polynomial commitments. Concretely, our scheme has smaller proofs than most other succinct post-quantum arguments for large statements. For binary vectors of length $$ we achieve $$KiB linear map evaluation proofs with evaluation binding, and $$MiB proofs when extractability is required; for $$-bit integers these sizes are $$KiB and $$MiB, respectively.