Paper 2022/1365

Functional Commitments for Circuits from Falsifiable Assumptions

Abstract

A functional commitment (FC) scheme allows one to commit to a vector $\vec{x}$ and later produce a short opening proof of $(f, f(\vec{x}))$ for any admissible function $f$. The security of FC schemes, called evaluation binding, ensures that it is hard to open the commitment to the same function $f$ and different outputs $y \neq y'$. Unlike succinct non-interactive arguments (SNARG) which provide a stronger soundness guarantee but typically require non-falsifiable assumptions, the evaluation binding of FC schemes can often be based on falsifiable assumptions and is sufficient for certain applications such as constructing homomorphic signatures (HS). Since their inception, FC schemes supporting ever more expressive classes of functions have been proposed, with the state-of-the-art supporting low-degree polynomial maps. In this work we construct the first FC schemes for circuits, based on either pairing-based or lattice-based falsifiable assumptions. Our FCs require to fix a-priori only the maximal width of the circuit to be evaluated, and have opening proofs whose size only depends on the depth of the circuit. We obtain our results in two steps. First, we introduce a new tool which we call chainable functional commitment (CFC), and show that CFCs for quadratic polynomial maps generically imply an FC for bounded-width circuits. Then, we show how to efficiently instantiate CFCs for quadratic polynomial maps over either pairing groups or lattices. Using a recent transformation from FC to HS, we obtain the first pairing- and lattice-based constructions of HS for bounded-width, but unbounded-depth, circuits. Prior to this work, the only HS for general circuits is lattice-based and requires bounding the circuit depth at setup time.