Paper 2022/1365

Functional Commitments for Circuits from Falsifiable Assumptions

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
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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint.
Keywords
functional commitments vector commitments SNARGs
Contact author(s)
david balbas @ imdea org
catalano @ dmi unict it
dario fiore @ imdea org
russell lai @ aalto fi
History
2022-10-14: approved
2022-10-11: received
See all versions
Short URL
https://ia.cr/2022/1365
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/1365,
      author = {David Balbás and Dario Catalano and Dario Fiore and Russell W. F. Lai},
      title = {Functional Commitments for Circuits from Falsifiable Assumptions},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1365},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/1365}},
      url = {https://eprint.iacr.org/2022/1365}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.