Succinct Functional Commitments for Circuits from k-Lin
- LecturerProf. David Wu (The University of Texas at Austin)
Host: Kai-Min Chung - Time2024-06-20 (Thu.) 10:15 ~ 12:00
- LocationAuditorium 101 at IIS new Building
Abstract
A functional commitment allows a user to commit to an input x and later, open the commitment to an arbitrary function y = f(x). The size of the commitment should be sublinear in both the length of the input as well as the size of the function.
In this talk, I will describe how to construct functional commitments for arbitrary arithmetic circuits from the bilateral k-Lin assumption in pairing groups. Notably, both the size of the commitment and the size of the opening consist of a constant number of group elements. This is the first scheme with this level of succinctness from falsifiable bilinear map assumptions (previous constructions needed SNARKs for NP). This is also the first functional commitment scheme for general circuits with 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 with a universal setup as well as a homomorphic signature scheme that supports arbitrary circuits; in both cases, the size of the proof (resp., signature) consists of a constant number of group elements.
Joint work with Hoeteck Wee
In this talk, I will describe how to construct functional commitments for arbitrary arithmetic circuits from the bilateral k-Lin assumption in pairing groups. Notably, both the size of the commitment and the size of the opening consist of a constant number of group elements. This is the first scheme with this level of succinctness from falsifiable bilinear map assumptions (previous constructions needed SNARKs for NP). This is also the first functional commitment scheme for general circuits with 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 with a universal setup as well as a homomorphic signature scheme that supports arbitrary circuits; in both cases, the size of the proof (resp., signature) consists of a constant number of group elements.
Joint work with Hoeteck Wee