Orbweaver: Succinct Linear Functional Commitments from Lattices

We present Orbweaver, the first plausibly post-quantum functional commitment to achieve quasilinear prover time together with O(log n) proof size and O(log n log log n) verifier time. Orbweaver enables evaluation of linear maps on committed vectors over cyclotomic rings or the integers. It is extractable, preprocessing, non-interactive, structure-preserving, amenable to recursive composition, and supports logarithmic public proof aggregation. The security of our scheme is based on the kR-ISIS assumption (and its knowledge counterpart), whereby we require a trusted setup to generate a universal structured reference string. We additionally use Orbweaver to construct a succinct polynomial commitment for integer polynomials.