Paper 2024/688
Succinct Functional Commitments for Circuits from k-Lin
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)
- 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
-
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} }