Paper 2024/688

Succinct Functional Commitments for Circuits from k-Lin

Hoeteck Wee, NTT Research, École Normale Supérieure - PSL
David J. Wu, The University of Texas at Austin
Abstract

A functional commitment allows a user to commit to an input $\mathbf{x}$ and later, open the commitment to an arbitrary function $\mathbf{y} = f(\mathbf{x})$. The size of the commitment and the opening should be sublinear in $|\mathbf{x}|$ and $|f|$. In this work, we give the first pairing-based functional commitment for arbitrary circuits where the size of the commitment and the size of the opening consist of a constant number of group elements. Security relies on the standard bilateral $k$-$\mathsf{Lin}$ assumption. This is the first scheme with this level of succinctness from falsifiable bilinear map assumptions (previous approaches required SNARKs for $\mathsf{NP}$). This is also the first functional commitment scheme for general circuits with $\mathsf{poly}(\lambda)$-size commitments and openings from any assumption that makes fully black-box use of cryptographic primitives and algorithms. As an immediate consequence, we also obtain a succinct non-interactive argument for arithmetic circuits (i.e., a SNARG for $\mathsf{P}/\mathsf{poly}$) with a universal setup and where the proofs consist of a constant number of group elements. In particular, the CRS in our SNARG only depends on the size of the arithmetic circuit $|C|$ rather than the circuit $C$ itself; the same CRS can be used to verify computations with respect to different circuits. Our construction relies on a new notion of projective chainable commitments which may be of independent interest.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A major revision of an IACR publication in EUROCRYPT 2024
Keywords
functional commitmentpairingsSNARG
Contact author(s)
wee @ di ens fr
dwu4 @ cs utexas edu
History
2024-05-06: approved
2024-05-05: received
See all versions
Short URL
https://ia.cr/2024/688
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/688,
      author = {Hoeteck Wee and David J. Wu},
      title = {Succinct Functional Commitments for Circuits from k-Lin},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/688},
      year = {2024},
      url = {https://eprint.iacr.org/2024/688}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.