Functional commitments for arbitrary circuits of bounded sizes

A functional commitment (FC) scheme enables committing to a vector x and later producing an opening proof pi for a function value y=f(x) with function f in some function set F. Everyone can verify the validity of the opening proof pi w.r.t. the function f and the function value y. Up to now, the largest function set is the bounded-depth circuits and achieved by FC schemes in [Peikeit et al. TCC 2021, De Castro et al. TCC 2023, Wee et al. Eurocrypt 2023, Wee et al. Asiacrypt 2023] with the help of the homomorphic encoding and evaluation techniques from lattices. In fact, these FC schemes can hardly support circuits of large depth, due to the fast accumulation of noises in the homomorphic evaluations. For example, if the depth of the circuit is linear to the security parameter lambda, then the underlying GapSVP(gamma) problem will be accompanied with a super-exponentially large parameter gamma>(lambda log lambda)(Theta(lambda)) and can be easily solved by the LLL algorithm. In this work, we propose a new FC scheme supporting arbitrary circuits of bounded sizes. We make use of homomorphic encoding and evaluation as well, but we disassemble the circuit gate by gate, process the gates, and reassemble the processed gates to a flattened circuit of logarithm depth O(log lambda). This makes possible for our FC scheme to support arbitrary polynomial-size circuits. Our FC scheme has the common reference string (CRS) growing linear to the size of the circuit. So CRSs of different sizes allow our FC scheme to support circuits of different (bounded) sizes. Just like the recent work on FC schemes [Wee et al. Eurocrypt 2023, Asiacrypt 2023], our FC scheme achieves private opening and target binding based on a falsifiable family of "basis-augmented" SIS assumptions. Our FC scheme has succinct commitment but not succinct opening proof which of course does not support fast verification. To improve the running time of verification, we resort to the non-interactive GKR protocol to outsource the main computation in verification to the proof generation algorithm. As a result, we obtain an improved FC scheme which decreases the computational complexity of verification with a factor O(lambda).