International Association for Cryptologic Research

International Association
for Cryptologic Research


Orbweaver: Succinct Linear Functional Commitments from Lattices

Ben Fisch , Yale University
Zeyu Liu , Yale University
Psi Vesely , Yale University
DOI: 10.1007/978-3-031-38545-2_4 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: CRYPTO 2023
Abstract: 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)loglog(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 k-R-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.
  title={Orbweaver: Succinct Linear Functional Commitments from Lattices},
  author={Ben Fisch and Zeyu Liu and Psi Vesely},