Paper 2022/1365

Chainable Functional Commitments for Unbounded-Depth Circuits

David Balbás, IMDEA Software Institute, Universidad Politecnica de Madrid
Dario Catalano, University of Catania
Dario Fiore, IMDEA Software Institute
Russell W. F. Lai, Aalto University

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$. Since their inception, FC schemes supporting ever more expressive classes of functions have been proposed. In this work, we introduce a novel primitive that we call chainable functional commitment (CFC), which extends the functionality of FCs by allowing one to 1) open to functions of multiple inputs $f(\vec x_1, \ldots, \vec x_m)$ that are committed independently, 2) while preserving the output also in committed form. We show that CFCs for quadratic polynomial maps generically imply FCs for circuits. Then, we efficiently realize CFCs for quadratic polynomials over pairing groups and lattices, resulting in the first FC schemes for circuits of unbounded depth based on either pairing-based or lattice-based falsifiable assumptions. Our FCs require fixing 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. Additionally, our FCs feature other nice properties such as being additively homomorphic and supporting sublinear-time verification after offline preprocessing. Using a recent transformation that constructs homomorphic signatures (HS) from FCs, we obtain the first pairing- and lattice-based realisations 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.

Available format(s)
Publication info
functional commitmentsvector commitmentsSNARGs
Contact author(s)
david balbas @ imdea org
catalano @ dmi unict it
dario fiore @ imdea org
russell lai @ aalto fi
2023-06-15: revised
2022-10-11: received
See all versions
Short URL
Creative Commons Attribution


      author = {David Balbás and Dario Catalano and Dario Fiore and Russell W. F. Lai},
      title = {Chainable Functional Commitments for Unbounded-Depth Circuits},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1365},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.