Succinct Functional Commitments for Circuits from k- \(\textsf{Lin}\)

A functional commitment allows a user to commit to an input \(\textbf{x}\) and later, open the commitment to an arbitrary function \(\textbf{y}= f(\textbf{x})\) . The size of the commitment and the opening should be sublinear in \(\left| \textbf{x} \right| \) and \(\left| f \right| \) . 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- \(\textsf{Lin}\) assumption. This is the first scheme with this level of succinctness from falsifiable bilinear map assumptions (previous approaches required SNARKs for \(\textsf{NP} \) ). This is also the first functional commitment scheme for general circuits with \(\textsf{poly}(\lambda )\) -size commitments and openings from any assumption that makes fully black-box use of cryptographic primitives and algorithms. Our construction relies on a new notion of projective chainable commitments which may be of independent interest.