Welcome to the resource topic for 2024/028
Title:
Lattice-Based Functional Commitments: Fast Verification and Cryptanalysis
Authors: Hoeteck Wee, David J. Wu
Abstract:A functional commitment allows a user to commit to an input \mathbf{x} \in \{0,1\}^\ell and later open up the commitment to a value y = f(\mathbf{x}) with respect to some function f. In this work, we focus on schemes that support fast verification. Specifically, after a preprocessing step that depends only on f, the verification time as well as the size of the commitment and opening should be sublinear in the input length \ell, We also consider the dual setting where the user commits to the function f and later, opens up the commitment at an input \mathbf{x}.
In this work, we develop two (non-interactive) functional commitments that support fast verification. The first construction supports openings to constant-degree polynomials and has a shorter CRS for a broad range of settings compared to previous constructions. Our second construction is a dual functional commitment for arbitrary bounded-depth Boolean circuits. Both schemes are lattice-based and avoid non-black-box use of cryptographic primitives or lattice sampling algorithms. Security of both constructions rely on the \ell-succinct short integer solutions (SIS) assumption, a falsifiable q-type generalization of the SIS assumption (Preprint 2023).
In addition, we study the challenges of extending lattice-based functional commitments to extractable functional commitments, a notion that is equivalent to succinct non-interactive arguments (when considering openings to quadratic relations). We describe a general methodology that heuristically breaks the extractability of our construction and provides evidence for the implausibility of the knowledge k-R-\mathsf{ISIS} assumption of Albrecht et al. (CRYPTO 2022) that was used in several constructions of lattice-based succinct arguments. If we additionally assume hardness of the standard inhomogeneous SIS assumption, we obtain a direct attack on a variant of the extractable linear functional commitment of Albrecht et al.
ePrint: https://eprint.iacr.org/2024/028
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .