Chainable Functional Commitments for Unbounded-Depth Circuits

David Balbás*, Dario Catalano, Dario Fiore, Russell W.F. Lai

*Tämän työn vastaava kirjoittaja

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussaConference article in proceedingsScientificvertaisarvioitu


A functional commitment (FC) scheme allows one to commit to a vector x and later produce a short opening proof of (f, f(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(x1, …, xm) 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 proof size depending only on the circuit depth. 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.

OtsikkoTheory of Cryptography - 21st International Conference, TCC 2023, Proceedings
ToimittajatGuy Rothblum, Hoeteck Wee
ISBN (painettu)978-3-031-48620-3
DOI - pysyväislinkit
TilaJulkaistu - 2023
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisussa
TapahtumaTheory of Cryptography Conference - Taipei, Taiwan
Kesto: 29 marrask. 20232 jouluk. 2023
Konferenssinumero: 21


NimiLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Vuosikerta14371 LNCS
ISSN (painettu)0302-9743
ISSN (elektroninen)1611-3349


ConferenceTheory of Cryptography Conference


Sukella tutkimusaiheisiin 'Chainable Functional Commitments for Unbounded-Depth Circuits'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

Siteeraa tätä