Lattice-Based Functional Commitments: Fast Verification and Cryptanalysis

Abstract

A functional commitment allows a user to commit to an input $\textbf{x}\in \{0,1\}^\ell$ and later open up the commitment to a value $y = f(\textbf{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 $\textbf{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 that supports fast verification with security from falsifiable assumptions. 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-$\textsf{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.

1 Introduction

In a functional commitment scheme [IKO07, BC12, LRY16], a user can commit to a vector $\textbf{x}$ and at a later point in time, provide a short opening to a value $y = f(\textbf{x})$ with respect to an (arbitrary) function f. We also consider a dual notion where a user commits to the function f and opens to an evaluation at a point $\textbf{x}$ [BNO21, dCP23]. The efficiency requirement on a functional commitment is both the commitment and the openings are short (i.e., have size that is sublinear or polylogarithmic in the length of $\textbf{x}$ and the size of the function f). The security requirement is that an adversary cannot open up a commitment $\sigma$ to two distinct values $y_0 \ne y_1$ with respect to any function f (or in the dual formulation, with respect to an input $\textbf{x}$). In this work, we focus exclusively on non-interactive functional commitments [LRY16, LP20, PPS21, BNO21, ACL+22, BCFL22, dCP23, WW23] in the standard model (with a common reference string). Functional commitments generalize notions like vector commitments [LY10, CF13] and polynomial commitments [KZG10, PSTY13] and have found numerous applications to cryptography, most notably, to efficient constructions of succinct non-interactive arguments (SNARGs).

Functional Commitments with Fast Verification. Our focus in this work is on lattice-based functional commitments for general functions. We are specifically interested in constructions that support fast verification in the preprocessing model. In this setting, we allow for an initial preprocessing stage that can depend only on the function f (which operates on inputs of length $\ell$) and outputs a short verification key $\textsf{vk}_f$. Given the preprocessed verification key $\textsf{vk}_f$, we then require that the verifier running time (and by extension, the size of the commitment and opening) to be sublinear in the input length $\ell$. We can define a similar property in the dual setting where we preprocess the input $\textbf{x}$ instead of the function f. Note that having succinct commitments and openings alone does not imply fast verification. For instance, the verification time in [WW23] is linear in the size of the function f even though the size of the commitment and the opening only depend on the depth of f.

In applications where the function of interest is known in advance, preprocessing can significantly reduce verification costs. This is common in settings like delegation and outsourcing computation. Specifically, for the closely-related problem of succinct arguments, working in the “preprocessing” model yields the most succinct constructions [GGPR13, BCI+13, PHGR13, Gro16].

Lattice-Based Functional Commitments. Functional commitments from lattice-based assumptions have received extensive study in the last few years. Several works [PPS21, ACL+22, BCFL22, WW23] gave constructions of functional commitments for broad classes of functions from lattice-based assumptions with a structured CRS. De Castro and Peikert [dCP23] gave a dual functional commitment for all circuits from the standard short integer solutions (SIS) problem in the uniform random string model. The authors of [KLVW23] consider a closely-related problem of delegation for RAM programs; their techniques can be adapted to obtain a functional commitments scheme for Boolean circuits from the learning with errors (LWE) assumption in the random string model; see Sect. 1.3 for more details. Their construction relies on non-black-box use of cryptographic hash functions (as well as lattice sampling algorithms). Our focus in this work is on constructions that only make black-box use of cryptographic algorithms.

Table 1. Summary of succinct lattice-based functional commitments. For each scheme, we report the class of functions they support, the size of the common reference string $\textsf{crs}$, the size of the commitment $\sigma$, and the size of an opening $\pi$ as a function of the function f and the input length $\ell$. We assume functions with a single output. For simplicity, we suppress $\textsf{poly}(\lambda , d, \log \ell )$ terms throughout the comparison (where d refers to either the degree of the polynomial or the depth of the circuit). The first set of constructions (above the line) are standard functional commitments where one commits to an input $\textbf{x}$ and opens to a function f while the second set (below the line) are dual functional commitments where one commits to a function f and opens to an input $\textbf{x}$. We say that a scheme supports “fast verification” (FV) if after an input-independent preprocessing step, the verification time is sublinear in $\ell$ and that it is “black-box” (BB) if it only makes black-box use of cryptographic algorithms. Note that $\textsf{BASIS}_{\textsf{struct}}$ implies $\ell$-succinct $\textsf{SIS}$  [Wee23]. In all constructions, the running time of the commitment algorithm is linear in the input length.

If we restrict our attention to lattice-based functional commitments that only make black-box use of cryptography, the existing constructions with fast verification either support constant-degree polynomials [ACL+22] or bounded-width Boolean circuits [BCFL22]. In the dual setting, we do not have any constructions with fast verification. We refer to Table 1 for a summary of the current state of the art.

$^{*}$ While [KLVW23] construct delegation for RAM programs, their construction can be adapted to obtain a functional commitments for all Boolean circuits. We provide more details in Sect. 1.3.

$^{\S }$ Only supports commitments and openings to small values.

$^{\dag }$ The width of the circuit w is always at least the input length $\ell$. In the case of an arbitrary dense polynomial of degree d (e.g., a polynomial with $\ell ^d$ distinct monomials), then the width of the circuit computing it is $\ell ^d$.

$^{\ddagger }$ The [dCP23] construction supports fast verification for certain special cases (e.g., vector commitments and polynomial commitments).

1.1 Our Contributions

In this work, we give two constructions of functional commitments that support fast verification. Security of both construction rely on the $\ell$-succinct SIS assumption, a falsifiable “q-type” generalization of the SIS assumption introduced by [Wee23]. Notably, this is a weaker assumption than the more structured $\textsf{BASIS}_{\textsf{struct}}$ assumption from [WW23]. Our first construction supports constant-degree polynomials and the second is the first dual functional commitment for (bounded-depth) Boolean circuits with fast verification and only making black-box use of cryptography. We provide a more detailed comparison to previous constructions in Table 1 and summarize the main results here.

Functional Commitment for Constant-Degree Polynomials. Our first construction (Construction 3.2) is a functional commitment for constant-degree polynomials where the size of the CRS scales with $\ell ^{d + 1} \cdot \textsf{poly}(\lambda , d, \log \ell )$, where d is the degree of the polynomial, $\lambda$ is the security parameter, and $\ell$ is the input length.

For the particular case of opening to quadratic polynomials (an important special case for delegating computations due to the $\textsf{NP}$-hardness of deciding satisfiability of a system of quadratic functions), our construction has a CRS size of $\ell ^3$. Previous approaches required a CRS that scale with $\ell ^4$ [ACL+22] or $\ell ^5$ [BCFL22]. More broadly, when considering openings to polynomials of constant degree d, we achieve a factor of 2 reduction in the exponent for the CRS size compared to [ACL+22]. Namely, the [ACL+22] construction has a CRS of size $\ell ^{2d} \cdot \textsf{poly}(\lambda , d, \log \ell )$, so our construction reduces the exponent from 2d to $d + 1$. The [BCFL22] scheme has a smaller CRS for the case of sparse polynomials (e.g., when the width w of the circuit computing the polynomial f is roughly the input length $w \approx \ell$). Conversely, for dense polynomials with $\approx \ell ^d$ monomials, and which corresponds to a circuit of width $\ell ^d$, the size of the CRS is significantly worse for their scheme. While the CRS size of our construction is worse than that of [WW23], the latter does not support fast verification (except in the case of linear functions).

On the assumption front, the security of Construction 3.2 follows from the L-succinct SIS assumption (with $L = O(\ell ^d)$), a falsifiable “q-type” generalization of the SIS assumption introduced by [Wee23]. This is a weaker assumption than the $\textsf{BASIS}_{\textsf{struct}}$ assumption used in [WW23] (i.e., is implied by the $\textsf{BASIS}_{\textsf{struct}}$ assumption), and less structured generalizations of SIS compared to the k-R-$\textsf{ISIS}$ and twin-k-M-$\textsf{ISIS}$ assumptions used in [ACL+22, BCFL22]. We refer to Sect. 1.2 and Sect. 3 for an overview of the assumption and construction.

Dual Functional Commitment for Boolean Circuits. Our second construction is a dual functional commitment for arbitrary (bounded-depth) Boolean circuits (Construction 3.10). This is the first dual functional commitment scheme based on falsifiable assumptions that supports succinct openings and verification and which does not make non-black-box use of cryptography. Previously, [dCP23] constructed a dual functional commitment from the standard $\textsf{SIS}$ assumption with short commitments but long openings and thus, slow verification. Specifically, in their scheme, the size of the opening and the running time of the verification algorithm scaled linearly with the input size $\ell$. In our construction, the size of the opening is polylogarithmic in the input length, as is verification (after an initial preprocessing step). On the flip side, the [dCP23] construction has a transparent CRS whose size scales linearly with $\ell$ while our construction has a structured CRS whose size scales quadratically with $\ell$. The structured CRS is used to “compress” the openings (see Sect. 1.2 and Construction 3.10). Security of our construction also relies on the falsifiable $\ell$-succinct SIS assumption.

Extractable Commitments and Cryptanalysis. The authors of [ACL+22] showed that if the binding property on a functional commitment for quadratic functions was replaced by a stronger extractability property, then it can be used to obtain a succinct non-interactive argument for $\textsf{NP}$. A functional commitment is extractable if for any efficient adversary that outputs a commitment $\sigma$ and an opening $\pi$ to the value y with respect to a function f, there exists an extractor that outputs an input x such that $f(x) = y$. Extractable functional commitments for quadratic functions can be used to obtain a succinct non-interactive argument (SNARG) for $\textsf{NP}$ (using the fact that satisfiability of quadratic systems is $\textsf{NP}$-complete). In this work, we describe a general methodology for cryptanalyzing existing approaches for constructing extractable functional commitments. Notably, we show heuristically that our functional commitment for constant-degree polynomials is unlikely to satisfy extractability. We then describe a similar attack on an adaptation of the [ACL+22] functional commitment for linear functions. Here, we show that assuming (non-uniform) hardness of the standard inhomogeneous SIS problem, the variant of [ACL+22] we consider is not extractable. Alone the way, we also give an oblivious sampling algorithm on a matrix version of the k-R-ISIS knowledge assumption from [ACL+22]. We provide an overview in Sect. 1.2 and the details in Sect. 4.

1.2 Technical Overview

In this section, we provide a high-level overview of our approach for constructing functional commitments with fast verification in the preprocessing model as well as the challenges in extending these constructions to satisfy the stronger extractability notion needed to construct preprocessing succinct non-interactive arguments.

Notation. We start with some basic notation. For a matrix $\textbf{A}\in \mathbb {Z}_{q}^{n \times m}$ and a target vector $\textbf{t}\in \mathbb {Z}_{q}^n$, we write $\textbf{A}^{-1}(\textbf{t})$ to denote a random variable $\textbf{x}\in \mathbb {Z}_{q}^m$ whose entries are distributed according to a discrete Gaussian distribution conditioned on $\textbf{A}\textbf{x}= \textbf{t}$. We can efficiently sample from $\textbf{A}^{-1}(\textbf{t})$ given a trapdoor for the matrix $\textbf{A}$. We write $\textbf{I}_n$ to denote the identity matrix of dimension n. We let $\textbf{G}\in \mathbb {Z}_{q}^{n \times m}$ denote the standard gadget matrix (i.e., $\textbf{G}= \textbf{I}_n \otimes \textbf{g}^{\scriptscriptstyle \textsf{T}}$, where $\textbf{g}^{\scriptscriptstyle \textsf{T}}= [1, 2, \ldots , 2^{\left\lfloor \log q \right\rfloor }]$) [MP12], and $\textbf{G}^{-1}(\cdot ) :\mathbb {Z}_{q}^n \rightarrow \mathbb {Z}_{q}^m$ denote the usual binary-decomposition operator.

The $\ell$-Succinct SIS Assumption. Our constructions rely on the $\ell$-succinct short integer solutions (SIS) assumption [Wee23]. For a matrix , the standard SIS problem [Ajt96] is to find a short non-zero solution $\textbf{x}\in \mathbb {Z}_{q}^m$ such that $\textbf{A}\textbf{x}= \boldsymbol{0}$. The $\ell$-succinct SIS assumption states that SIS is hard with respect to $\textbf{A}$ even given a trapdoor for $[\textbf{I}_\ell \otimes \textbf{A}\mid \textbf{W}]$ where is a random narrow matrix. Note that if is wide, then hardness of $\ell$-succinct SIS can be reduced to the hardness of SIS using lattice trapdoor extension techniques [Wee23].

The $\ell$-succinct SIS assumption is a weaker assumption that the structured $\textsf{BASIS}_{\textsf{struct}}$ assumption used in [WW23] for constructing functional commitments; notably, the $\textsf{BASIS}_{\textsf{struct}}$ assumption from [WW23] is an instance of the $\ell$-succinct SIS assumption with a structured $\textbf{W}$. While $\ell$-succinct SIS is a new and non-standard assumption, it is a falsifiable assumption, and can be viewed as a “q-type” analog of the SIS assumption. We note that it is also implied by the “evasive LWE” assumption [Wee22, Tsa22], which is an assumption that has been used successfully in several other recent works [WWW22, VWW22].

1.2.1 1.2.1 A Functional Commitment Scheme for Quadratic Polynomials

Here, we describe our approach for constructing a functional commitment for constant-degree polynomials on $\ell$-dimensional inputs. Specifically, the committer should be able to commit to an input $\textbf{x}\in \mathbb {Z}_{q}^\ell$ and then subsequently open up the commitment to $f(\textbf{x})$ where f is a constant-degree polynomial. For simplicity of exposition, we will focus on the case of quadratic polynomials, and defer the generalization to higher-degree polynomials to Sect. 3.

The Wee-Wu Scheme. We start with a quick recap of the functional commitment for circuits from [WW23] based on the $\textsf{BASIS}_{\textsf{struct}}$ assumption (c.f., [WW23, Remark 4.13]), adapted to the $\ell$-succinct SIS assumption.¹ As we explain below, although the [WW23] construction shares a similar verification relation as our construction, it does not appear to support fast verification. To describe the construction, we first parse the matrix $\textbf{W}\in \mathbb {Z}_{q}^{\ell n \times m}$ from the $\ell$-succinct SIS assumption as the vertical concatenation of matrices $\textbf{W}^{(1)},\ldots ,\textbf{W}^{(\ell )} \in \mathbb {Z}_{q}^{n \times m}$. A commitment to a (short) input vector $\textbf{x}\in \mathbb {Z}_{q}^\ell$ consists of a short matrix $\textbf{C}\in \mathbb {Z}^{m \times m}$ along with short matrices $\textbf{V}_i$ satisfying the following relation:

$$\begin{aligned} \textbf{W}^{(i)} \textbf{C}&= x_i \textbf{G}- \textbf{A}\textbf{V}_i \end{aligned}$$

Then, for all $i, j \in [\ell ]$,

$$\begin{aligned} (\textbf{W}^{(i)} \textbf{C}) \cdot \textbf{G}^{-1}(\textbf{W}^{(j)} \textbf{C}) &= x_i \textbf{W}^{(j)} \textbf{C}- \textbf{A}\textbf{V}_{i} \textbf{G}^{-1}(\textbf{W}^{(j)} \textbf{C}) \\ &= x_i x_j \cdot \textbf{G}- \textbf{A}\cdot (\underbrace{x_i\textbf{V}_j + \textbf{V}_{i} \textbf{G}^{-1}(\textbf{W}^{(j)} \textbf{C})}_{\tilde{\textbf{V}}_{ij}}) \end{aligned}$$

Observe that $\tilde{\textbf{V}}_{i, j} = x_i \textbf{V}_j + \textbf{V}_{i} \textbf{C}$ is small since $x_i$, $\textbf{V}_i$, $\textbf{V}_j$, and $\textbf{C}$ are all small. We now view $\tilde{\textbf{V}}_{ij}$ as the opening for $\textbf{C}$ to the quadratic relation $x_i x_j$. Furthermore, this extends readily to circuits following [BGG+14, GVW15b]. For the specific case of a general quadratic polynomial $f(\textbf{x}) = \sum _{i, j \in [\ell ]} \gamma _{ij} x_i x_j$, the left-hand side of the verification relation becomes

$$ \sum _{i,j \in [\ell ]} \gamma _{ij} (\textbf{W}^{(i)} \textbf{C}) \cdot \textbf{G}^{-1}(\textbf{W}^{(j)} \textbf{C}). $$

We do not know how to decompose this computation into a slow preprocessing phase that is independent of $\textbf{C}$, followed by a fast computation on $\textbf{C}$. The analogous expression in the functional commitment scheme of [ACL+22] is given by $\sum _{i, j \in [\ell ]} {\gamma _{ij}} w^{(i)} c \cdot w^{(j)} c$ where $w^{(i)}, w^{(j)}, c$ are ring elements. Since ring multiplication is commutative (unlike matrix multiplication), this can be rewritten as $(\sum \gamma _{i, j \in [\ell ]} w^{(i)}w^{(j)}) \cdot c^2$. By precomputing the quantity $(\sum \gamma _{i, j \in [\ell ]} w^{(i)}w^{(j)})$, which is independent of the commitment, the [ACL+22] construction supports fast verification in the preprocessing model.

Our Approach. To construct a functional commitment scheme that supports fast verification (with preprocessing), we introduce additional structure. For the case of quadratic functions, we rely on the $(\ell + \ell ^2)$-succinct SIS assumption; contrast this with the [WW23] construction described above which relied on the smaller $\ell$-succinct SIS assumption. We parse the matrix $\textbf{W}\in \mathbb {Z}_{q}^{(\ell + \ell ^2) n \times m}$ from the assumption as

$$ \textbf{W}= \begin{bmatrix} \textbf{W}_1 \\ \textbf{W}_2 \end{bmatrix} \quad \text {where} \quad \textbf{W}_1 = \begin{bmatrix} \textbf{W}_1^{(1)} \\ \vdots \\ \textbf{W}_1^{(\ell )} \end{bmatrix} \in \mathbb {Z}_{q}^{n \ell \times m} \quad \text {and} \quad \textbf{W}_2 = \begin{bmatrix} \textbf{W}_2^{(1, 1)} \\ \vdots \\ \textbf{W}_1^{(\ell , \ell )} \end{bmatrix} \in \mathbb {Z}_{q}^{n \ell ^2 \times m}, $$

where $\textbf{W}_1^{(i)}, \textbf{W}_2^{(i, j)} \in \mathbb {Z}_{q}^{n \times m}$. A commitment to a (short) input vector $\textbf{x}\in \mathbb {Z}_{q}^\ell$ consists of a short matrix $\textbf{C}\in \mathbb {Z}^{m \times m}$ along with short matrices $\textbf{V}_i, \textbf{V}_{i j} \in \mathbb {Z}_{q}^{m \times m}$ satisfying the following relation:

$$\begin{aligned} \textbf{W}_1^{(i)} \textbf{C}&= x_i \textbf{G}- \textbf{A}\textbf{V}_i \end{aligned}$$

(1.1)

$$\begin{aligned} \textbf{W}_2^{(i,j)} \textbf{C}&= x_i \textbf{W}_1^{(j)} - \textbf{A}\textbf{V}_{ij} \end{aligned}$$

(1.2)

Then, for all $i, j \in [\ell ]$,

$$\begin{aligned} \textbf{W}_2^{(i,j)} \textbf{C}^2 &= x_i \textbf{W}_1^{(j)} \textbf{C}- \textbf{A}\textbf{V}_{ij} \textbf{C}\\ &= x_i x_j \cdot \textbf{G}- \textbf{A}\cdot (\underbrace{x_i\textbf{V}_j + \textbf{V}_{ij} \textbf{C}}_{\tilde{\textbf{V}}_{ij}}) \end{aligned}$$

Observe that $\tilde{\textbf{V}}_{i, j} = x_i \textbf{V}_j + \textbf{V}_{i j} \textbf{C}$ is small since $\textbf{x}$, $\textbf{V}_j$, $\textbf{V}_{ij}$, and $\textbf{C}$ are all small. We now take $\tilde{\textbf{V}}_{ij}$ to be the opening for $\textbf{C}$ to the quadratic relation $x_i x_j$. More generally, an opening for a general quadratic polynomial $f(\textbf{x}) = \sum _{i, j \in [\ell ]} \gamma _{ij} x_i x_j$ to the value $y = f(\textbf{x})$ is a short matrix $\tilde{\textbf{V}}$ where

$$\begin{aligned} \underbrace{\left( \sum _{i, j \in [\ell ]} \gamma _{i j} \textbf{W}_2^{(i,j)} \right) }_{\textbf{W}_f} \cdot \textbf{C}^2 = y \cdot \textbf{G}- \textbf{A}\cdot \tilde{\textbf{V}}. \end{aligned}$$

(1.3)

Our Scheme. To complete the description, we publish the following components in the CRS:

$$\begin{aligned} \begin{bmatrix} \textbf{T}_{\textsf{open}}\\ \textbf{T}_{\textsf{com}}\end{bmatrix} \leftarrow \left[ \begin{array}{cc|c} \textbf{I}_\ell \otimes \textbf{A}&{} &{} \textbf{W}_1 \\ &{} \textbf{I}_{\ell ^2} \otimes \textbf{A}&{} \textbf{W}_2 \end{array} \right] ^{-1} \left( \begin{bmatrix} \textbf{I}_\ell \otimes \textbf{G}\\ \textbf{I}_\ell \otimes \textbf{W}_1 \end{bmatrix} \right) , \end{aligned}$$

(1.4)

where $\textbf{T}_{\textsf{open}}\in \mathbb {Z}_{q}^{(\ell + \ell ^2) m \times m \ell }$ and $\textbf{T}_{\textsf{com}}\in \mathbb {Z}_{q}^{m \times m \ell }$. Note that the CRS has size $O(\ell ^3)$, improving upon the $O(\ell ^4)$-sized CRS in [ACL+22].

To commit to a short $\textbf{x}\in \mathbb {Z}_{q}^\ell$, the committer computes $\textbf{C}\leftarrow \textbf{T}_{\textsf{com}}(\textbf{x}\otimes \textbf{I}_m)$. By construction this means that

$$\begin{aligned} \textbf{W}_1 \textbf{C}&= \textbf{W}_1 \textbf{T}_{\textsf{com}}(\textbf{x}\otimes \textbf{I}_m) = (\textbf{I}_\ell \otimes \textbf{G})(\textbf{x}\otimes \textbf{I}_m) - (\textbf{I}_\ell \otimes \textbf{A}) \textbf{T}_{\textsf{open}}(\textbf{x}\otimes \textbf{I}_m) \\ &= \textbf{x}\otimes \textbf{G}- (\textbf{I}_\ell \otimes \textbf{A}) \textbf{T}_{\textsf{open}}(\textbf{x}\otimes \textbf{I}_m) \\ \textbf{W}_2 \textbf{C}&= \textbf{W}_2 \textbf{T}_{\textsf{com}}(\textbf{x}\otimes \textbf{I}_m) = (\textbf{I}_\ell \otimes \textbf{W}_1)(\textbf{x}\otimes \textbf{I}_m) - (\textbf{I}_{\ell ^2} \otimes \textbf{A}) \textbf{T}_{\textsf{open}}(\textbf{x}\otimes \textbf{I}_m) \\ &= \textbf{x}\otimes \textbf{W}_1 - (\textbf{I}_{\ell ^2} \otimes \textbf{A}) \textbf{T}_{\textsf{open}}(\textbf{x}\otimes \textbf{I}_m). \end{aligned}$$

Observe that taking $\textbf{V}_i$ and $\textbf{V}_{ij}$ to be the blocks of $\textbf{T}_{\textsf{open}}(\textbf{x}\otimes \textbf{I}_m)$, we satisfy Eqs. (1.1) and (1.2). To argue binding from the $(\ell ^2 + \ell )$-succinct SIS assumption, observe that $\textbf{T}_{\textsf{open}}$ and $\textbf{T}_{\textsf{com}}$ can be sampled using the trapdoor provided by the $(\ell ^2 + \ell )$-succinct SIS assumption. Suppose now that an adversary outputs two possible openings $\tilde{\textbf{V}}_0, \tilde{\textbf{V}}_1$ to values $y_0, y_1 \in \mathbb {Z}_{q}$ with respect to the same quadratic function f. From Eq. (1.3), this means that

$$\begin{aligned} \textbf{W}_f \textbf{C}^2 = y_0 \textbf{G}- \textbf{A}\tilde{\textbf{V}}_0 = y_1 \textbf{G}- \textbf{A}\tilde{\textbf{V}}_1, \end{aligned}$$

or equivalently, that $\textbf{A}(\tilde{\textbf{V}}_1 - \tilde{\textbf{V}}_0) = (y_1 - y_0) \textbf{G}$. When $y_1 \ne y_0$ and q is prime (so that $y_1 - y_0$ is invertible), this yields a gadget trapdoor [MP12] for $\textbf{A}$, which the reduction can use to sample a short non-zero SIS solution from $\textbf{A}^{-1}(\boldsymbol{0})$. We provide the full details (and extension to higher-degree polynomials) in Sect. 3.

Fast Verification with Preprocessing. It is easy to see that the above construction supports fast verification given preprocessing. For instance, consider the verification relation in Eq. (1.3). If the function f is known in advance, we can precompute the matrix $\textbf{W}_f = \sum _{i, j \in [\ell ]} \gamma _{ij} \textbf{W}_2^{(i, j)}$. If we do so, then the verification relation simply checks $\textbf{W}_f \textbf{C}^2 = f(\textbf{x}) \cdot \textbf{G}- \textbf{A}\tilde{\textbf{V}}$, which can be computed in time that depends only polylogarithmically on $\ell$.

Extending to Multiple Outputs. Using a similar technique as [WW23], we can also extend our construction above to functions with multiple outputs. To illustrate, suppose we have a commitment $\textbf{C}$ and a collection of T openings $\tilde{\textbf{V}}_1, \ldots , \tilde{\textbf{V}}_T$ to values $y_1, \ldots , y_T$ and with respect to functions $f_1, \ldots , f_T$. Then, for all $i \in [T]$, we have from Eq. (1.3) that $\textbf{W}_{f_i} \textbf{C}^2 = y_i \textbf{G}- \textbf{A}\tilde{\textbf{V}}_1$. To support openings to multiple outputs, we publish random vectors in the CRS, and define the “multi-output” verification relation to be

$$ \sum _{i \in [T]} \textbf{W}_{f_i} \textbf{C}^2 \textbf{G}^{-1}(\textbf{u}_i) {\mathop {=}\limits ^{?}} \sum _{i \in [T]} y_i \textbf{u}_i - \sum _{i \in [T]} \textbf{A}\tilde{\textbf{V}}_i \textbf{G}^{-1}(\textbf{u}_i). $$

The new opening is now $\sum _{i \in [T]} \tilde{\textbf{V}}_i \textbf{G}^{-1}(\textbf{u}_i)$ which remains short. Moreover, the multi-output scheme still supports preprocessing. This is because the left-hand-side of the verification relation is still a linear function in $\textbf{C}^2$ and can be preprocessed; formally, this is done by “vectorizing” the verification relation (see Remark 3.6). In this case, the verification time with preprocessing is independent of the input length $\ell$, but still dependent on the output dimension T (this is anyhow necessary since the verification algorithm needs to read the opened values). In the setting where the target values $y_1, \ldots , y_T$ are also known in advance, we can also precompute the target value $\sum _{i \in [T]} y_i \textbf{u}_i$. When both the functions and the outputs are preprocessed, the running time of the verification algorithm is polylogarithmic in both the input length $\ell$ and the output dimension T. Finally, security of the multi-output version still reduces to $(\ell ^2 + \ell )$-succinct SIS. We provide the full details in Sect. 3.1. Taken together, we obtain a functional commitment for constant-degree polynomials of degree d where the size of the CRS is $\ell ^{d + 1} \cdot \textsf{poly}(\lambda , d, \log \ell , \log T)$ and the proof/opening sizes are $\textsf{poly}(\lambda , d, \log \ell , \log T)$. Compared to [ACL+22], our construction achieves a shorter CRS (reducing from $\ell ^{2 d}$ to $\ell ^{d + 1}$) and relies on a less-structured assumption.

Generalizing to Module Lattices. Our functional commitment scheme described here generalizes directly to module lattices and ideal lattices. Security in turn relies on the hardness of $\ell$-succinct over module lattices (as opposed to integer lattices). We describe the generalization in the full version of this paper. For a security parameter $\lambda$ and using module lattices (along with a z-ary gadget matrix), we obtain a functional commitment scheme for constant-degree polynomials where the commitment and the opening for an input of length $\ell$ (and single output) is $\tilde{O}(\lambda \log \ell )$; this relies on $2^{\tilde{\Omega }(\lambda )}$ hardness of $O(\ell ^d)$-succinct module SIS. This matches the commitment size and the opening size of the functional commitment from [ACL+22] which relies on ideal lattices. As noted above, compared to [ACL+22], our construction reduces the CRS size from $\ell ^{2d} \cdot \textsf{poly}(\lambda , d, \log \ell )$ to $\ell ^{d + 1} \cdot \textsf{poly}(\lambda , d, \log \ell )$.

1.2.2 A Dual Functional Commitment for Boolean Circuits

Next, we turn our attention to the dual setting where the user commits to a function f and opens to an input $\textbf{x}$. This is the setting studied in [BNO21, dCP23]. While a functional commitment that supports general functions (e.g., [WW23, BCFL22]) can be used to obtain a dual functional commitment for general functions through the use of universal circuits, the generic transformation necessarily both imposes an a priori bound on the size (or description length) of the function. Here, we opt for a more direct construction that avoids the need for universal circuits. Our approach is essentially a hybrid of the dual functional commitment for bounded-depth Boolean circuits from [dCP23] (which has short commitments but openings whose size scales with the input length) and the succinct ABE scheme from [Wee23]. We show how to combine these techniques to obtain a dual functional commitment for bounded-depth Boolean circuits with short commitments and openings. As before, our starting point is the $\ell$-succinct SIS assumption, where we are given a trapdoor $\textbf{T}$ satisfying

$$\begin{aligned}{}[\textbf{I}_\ell \otimes \textbf{A}\mid \textbf{W}] \cdot \textbf{T}= \textbf{I}_\ell \otimes \textbf{G}. \end{aligned}$$

(1.5)

We again parse the trapdoor $\textbf{T}$ as where $\textbf{T}_{\textsf{open}}\in \mathbb {Z}_{q}^{\ell m \times \ell m}$ and $\textbf{T}_{\textsf{com}}\in \mathbb {Z}_{q}^{m \times \ell m}$. If we multiply both sides of Eq. (1.5) by $(\textbf{x}^{\scriptscriptstyle \textsf{T}}\otimes \textbf{I}_n)$ and use the fact that $(\textbf{x}^{\scriptscriptstyle \textsf{T}}\otimes \textbf{I}_n)(\textbf{I}_\ell \otimes \textbf{A}) = (1 \otimes \textbf{A})(\textbf{x}^{\scriptscriptstyle \textsf{T}}\otimes \textbf{I}_m) = \textbf{A}(\textbf{x}^{\scriptscriptstyle \textsf{T}}\otimes \textbf{I}_m)$, we have that

$$ [\textbf{A}(\textbf{x}^{\scriptscriptstyle \textsf{T}}\otimes \textbf{I}_m) ~|~ (\textbf{x}^{\scriptscriptstyle \textsf{T}}\otimes \textbf{I}_n) \textbf{W}] \cdot \begin{bmatrix} \textbf{T}_{\textsf{open}}\\ \textbf{T}_{\textsf{com}}\end{bmatrix} = \textbf{x}^{\scriptscriptstyle \textsf{T}}\otimes \textbf{G}. $$

Take any matrix $\textbf{W}_0 \in \mathbb {Z}_{q}^{n \times m}$. Then, we can write

$$\begin{aligned}{}[\textbf{A}\mid \textbf{W}_0 + (\textbf{x}^{\scriptscriptstyle \textsf{T}}\otimes \textbf{I}_n) \textbf{W}] \cdot \begin{bmatrix} -(\textbf{x}^{\scriptscriptstyle \textsf{T}}\otimes \textbf{I}_m) \textbf{T}_{\textsf{open}}\\ -\textbf{T}_{\textsf{com}}\end{bmatrix} = -\textbf{W}_0 \textbf{T}_{\textsf{com}}- \textbf{x}^{\scriptscriptstyle \textsf{T}}\otimes \textbf{G}. \end{aligned}$$

(1.6)

Let us define $\textbf{B}\mathrel {\mathop :}=-\textbf{W}_0 \textbf{T}_{\textsf{com}}\in \mathbb {Z}_{q}^{n \times {\ell m}}$. The CRS will contain the elements $(\textbf{A}, \textbf{W}, \textbf{T}_{\textsf{com}}, \textbf{T}_{\textsf{open}}, \textbf{W}_0, \textbf{B})$. Now, Eq. (1.6) essentially says we can “recode” the matrix $[\textbf{A}\mid \textbf{W}_0 + (\textbf{x}^{\scriptscriptstyle \textsf{T}}\otimes \textbf{I}_n) \textbf{W}]$ to $\textbf{B}- \textbf{x}^{\scriptscriptstyle \textsf{T}}\otimes \textbf{G}$. Following [dCP23], we now define the commitment to a function $f :\{0,1\}^\ell \rightarrow \{0,1\}$ as the matrix $\textbf{B}_f$ obtained by homomorphically evaluating f on $\textbf{B}$ using the lattice-based homomorphic evaluation machinery from [GSW13, BGG+14].² To recall, for every matrix $\textbf{B}\in \mathbb {Z}_{q}^{n \times \ell m}$, every function $f :\{0,1\}^\ell \rightarrow \{0,1\}$, and every input $\textbf{x}\in \{0,1\}^\ell$, there exist a matrix $\textbf{B}_f \in \mathbb {Z}_{q}^{n \times m}$ that depends only on $\textbf{B}$ and f, and a short matrix $\textbf{H}_{\textbf{B}, f, \textbf{x}} \in \mathbb {Z}_{q}^{\ell m \times m}$ such that

$$\begin{aligned} (\textbf{B}- \textbf{x}^{\scriptscriptstyle \textsf{T}}\otimes \textbf{G}) \cdot \textbf{H}_{\textbf{B}, f, \textbf{x}} = \textbf{B}_f - f(\textbf{x}) \cdot \textbf{G}\in \mathbb {Z}_{q}^{n \times m}. \end{aligned}$$

To open at a point $\textbf{x}\in \{0,1\}^\ell$ to the value $z = f(\textbf{x})$, the committer then computes

$$\begin{aligned} \textbf{V}= \begin{bmatrix} -(\textbf{x}\otimes \textbf{I}_m) \textbf{T}_{\textsf{open}}\\ -\textbf{T}_{\textsf{com}}\end{bmatrix} \cdot \textbf{H}_{\textbf{B}, f, \textbf{x}} \in \mathbb {Z}_{q}^{2\,m \times m}. \end{aligned}$$

Observe that the size of the opening is essentially independent of the input length $\ell$.³ In [dCP23], the opening is the full matrix $\textbf{H}_{\textbf{B}, f, \textbf{x}}$. Here, the trapdoor $\textbf{T}$ from the $\ell$-succinct SIS assumption allows us to “compress” the opening. The verification relation is then

$$\begin{aligned} \textbf{B}_f - z \textbf{G}{\mathop {=}\limits ^{?}} [\textbf{A}\mid \textbf{W}_0 + (\textbf{x}\otimes \textbf{I}_n) \textbf{W}] \textbf{V}. \end{aligned}$$

(1.7)

From Eq. (1.6), we see that

$$\begin{aligned}{}[\textbf{A}~|~ \textbf{W}_0 + (\textbf{x}^{\scriptscriptstyle \textsf{T}}\otimes \textbf{I}_n) \textbf{W}] \textbf{V}&= [\textbf{A}~|~ \textbf{W}_0 + (\textbf{x}^{\scriptscriptstyle \textsf{T}}\otimes \textbf{I}_n) \textbf{W}] \begin{bmatrix} -(\textbf{x}^{\scriptscriptstyle \textsf{T}}\otimes \textbf{I}_m) \textbf{T}_{\textsf{open}}\\ -\textbf{T}_{\textsf{com}}\end{bmatrix} \cdot \textbf{H}_{\textbf{B}, f, \textbf{x}} \\ &= (-\textbf{W}_0 \textbf{T}_{\textsf{com}}- \textbf{x}^{\scriptscriptstyle \textsf{T}}\otimes \textbf{G}) \cdot \textbf{H}_{\textbf{B}, f, \textbf{x}} \\ &= (\textbf{B}- \textbf{x}^{\scriptscriptstyle \textsf{T}}\otimes \textbf{G}) \cdot \textbf{H}_{\textbf{B}, f, \textbf{x}} \\ &= \textbf{B}_f - f(\textbf{x}) \cdot \textbf{G}. \end{aligned}$$

This yields a dual functional commitment for all (bounded-depth) Boolean circuits on $\ell$-length inputs where the size of the commitment and the opening are both $\textsf{poly}(\lambda , d^{1 / \varepsilon }, \log \ell )$, where d is the bound on the depth of the function. The CRS in our construction has size $\ell ^2 \cdot \textsf{poly}(\lambda , d^{1 / \varepsilon }, \log \ell )$. We note that this construction also supports preprocessing; namely, if the input $\textbf{x}$ is known in advance, we can precompute the matrix $[\textbf{A}~|~ \textbf{W}_0 + (\textbf{x}\otimes \textbf{I}_n) \textbf{W}]$ in Eq. (1.7). Security reduces to the $\ell$-succinct SIS with a sub-exponential noise bound $2^{\tilde{O}(n^\varepsilon )}$, where $\varepsilon > 0$ is a constant and n is the lattice dimension. We refer to Sect. 3.2 for the full construction and analysis.

1.2.3 Knowledge Assumptions, Extractable Functional Commitments, and Cryptanalysis

The authors of [ACL+22] showed that if we strengthen the binding property on a functional commitment for quadratic functions to an extractability property, then it can be used to obtain a succinct non-interactive argument for $\textsf{NP}$. More specifically, in an extractable functional commitment, the binding property is replaced by a stronger extractability requirement which says that for any efficient adversary that outputs a commitment $\sigma$ and an opening $\pi$ to the value y with respect to a function f, there exists an extractor that outputs an input x such that $f(x) = y$. Extractable functional commitments for quadratic functions can be used to obtain a succinct non-interactive argument (SNARG) for $\textsf{NP}$ (using the fact that satisfiability of quadratic systems is $\textsf{NP}$-complete).

In Sect. 4, we highlight some of the difficulties in constructing extractable functional commitments from lattices, and more generally, the challenges of formulating lattice-based knowledge assumptions. The difficulties stem from the following fundamental phenomenon about lattices, which has no analog in the pairing world: given sufficiently many independent short vectors in the kernel of a lattice $\textbf{A}$, we can recover a trapdoor for $\textbf{A}$ and efficiently sample short pre-images for any coset of $\textbf{A}$. (The pairing analogue would be recovering a trapdoor that allows computing discrete logs). In our attacks, we invoke this basic fact for a carefully crafted matrix $\textbf{A}$ derived from the verification equation of the functional commitment scheme.

Attack on Knowledge k-R-ISIS. As a warm-up, we describe a candidate attack on a matrix variant of the knowledge k-R-ISIS assumption from [ACL+22].⁴ Here, the adversary is given

where $\ell \gg m + n$ and $t \ge n+1$. The goal of the adversary is to sample $\textbf{c}\in \mathbb {Z}_{q}^t$ along with a low-norm $\textbf{v}\in \mathbb {Z}^m$ so that

$$\begin{aligned} \textbf{A}\textbf{v}= \textbf{D}\textbf{c}. \end{aligned}$$

One way to do this is to sample small integers $x_i$, and then compute $\textbf{v}= \sum _{i \in [\ell ]} x_i \textbf{z}_i$ and $\textbf{c}= \sum _{i \in [\ell ]} x_i \textbf{t}_i$. The knowledge assumption basically asserts that this is the only way to sample $(\textbf{c},\textbf{v})$. In particular, if an adversary samples a random low-norm $\textbf{v}$, then $\textbf{A}\textbf{v}$ will lie outside the column span of $\textbf{D}$ with high probability.

Our candidate attack uses Babai’s rounding algorithm to sample small fractional $x_i$’s such that $\textbf{v}= \sum _{i \in [\ell ]} x_i \textbf{z}_i \in \mathbb {Z}^m$ and $\textbf{c}= \sum _{i \in [\ell ]} x_i \textbf{t}_i \in \mathbb {Z}_{q}^t$ and satisfies $\textbf{A}\textbf{v}= \textbf{D}\textbf{c}$. It is a candidate attack in the sense that we do not know how to rule out an extractor that outputs the same distribution for $\textbf{v},\textbf{c}$ using small integer $x_i$’s. The attack is fairly simple (in hindsight): we first construct a basis for the lattice $\textbf{B}= [\textbf{A}~|~ \textbf{D}\textbf{G}]$ as follows:

$$ \left[ \textbf{A}~|~ \textbf{D}\textbf{G}\right] \cdot \underbrace{\left[ \begin{array}{ccc} \textbf{z}_1 &{} \cdots &{} \textbf{z}_{\ell } \\ -\textbf{G}^{-1}(\textbf{t}_1) &{} \cdots &{} -\textbf{G}^{-1}(\textbf{t}_{\ell }) \end{array} \right] }_{\textbf{T}} = \boldsymbol{0}\bmod q. $$

Since the $\textbf{z}_i$’s are independent Gaussians and the $\textbf{t}_i$’s are uniformly random, we (heuristically) assume that $\textbf{T}\in \mathbb {Z}^{(m + n) \times \ell }$ is full rank over the reals.⁵ Now, an adversary can start with an arbitrary (non-zero) solution $\textbf{y}\in \mathbb {Z}^{m + n}$ where $\textbf{B}\textbf{y}= \boldsymbol{0}\bmod q$, solves for the unique $\textbf{z}\in \mathbb {Q}^{m + n}$ where $\textbf{T}\textbf{z}= \textbf{y}\in \mathbb {Q}^{m + n}$, and then outputs the integer vector $\textbf{y}^*= \textbf{y}- \textbf{T}\cdot \left\lfloor \textbf{z} \right\rceil$. By construction $\textbf{B}\textbf{y}^*= \boldsymbol{0}\bmod q$ and moreover, $\left\| \textbf{y}^* \right\| \le \left\| \textbf{T}(\textbf{z}- \left\lfloor \textbf{z} \right\rceil ) \right\|$, which is small. From $\textbf{y}^*$, we can compute $\textbf{v},\textbf{c}$ as desired.

Attacks on Extractable Functional Commitments. Using a similar methodology, we obtain heuristic attacks on the extractability of our functional commitment for constant-degree polynomials described above as well as on a version of the [ACL+22] functional commitment for the particular case of linear functions. We note that [ACL+22] define their commitment over module and ideal lattices, so when describing our attack, we consider a specific translation of their scheme to the integer case. Our methodology for analyzing the extractability of functional commitments follows the general blueprint:

• 1. We start by writing down the key verification relation. In all lattice-based functional commitment constructions [ACL+22, WW23, dCP23, BCFL22], the verification relation consists of checking that the opening is a short solution to a linear system. We re-express the verification relation as finding a short non-zero vector in the kernel of some related lattice.

• 2. Using the components published in the CRS, we derive a basis for this related lattice. We now use the basis to jointly sample a (possibly short) commitment and a (short) opening that satisfies the main verification relation.

Importantly, the commitment and the opening are sampled without explicit knowledge of a specific input. We can apply this strategy both to our functional commitment for constant-degree polynomials as well as to an integer variant of the [ACL+22] construction:

• In the case of our functional commitment for quadratic functions, we can use the above procedure to sample a commitment and a set of valid openings that correspond to an unsatisfiable constraint system. For instance, we show that the attacker can efficiently come up with a commitment $\textbf{C}$ together with valid openings asserting that $x_1^2 = 0$ and $x_1 x_2 = 1$.

• When applied to our integer-variant of the [ACL+22] functional commitment for linear functions, we can use this strategy to efficiently sample a commitment together with an opening for an arbitrary linear function to an arbitrary vector $\textbf{y}$. In other words, for any (short) matrix $\textbf{M}$, we can construct an efficient algorithm that samples a commitment $\textbf{C}$ and an opening $\textbf{V}$ to any target vector $\textbf{y}$ under the linear function $\textbf{x}\mapsto \textbf{M}\textbf{x}$. Note that this sampler does not need an explicit $\textbf{x}$ to sample $(\textbf{C}, \textbf{V})$. If the commitment scheme is extractable, then there would exist an extractor that can output a short $\textbf{x}$ such that $\textbf{M}\textbf{x}= \textbf{y}$. But this is precisely solving the inhomogeneous SIS problem (with respect to a short matrix $\textbf{M}$; hardness of inhomogeneous SIS with low-norm matrices follows from the standard setting with uniform $\textbf{M}$ via the mapping $\textbf{M}\mapsto \textbf{G}^{-1}(\textbf{M})$). Thus, our attacks demonstrates that assuming (non-uniform) hardness of the standard inhomogeneous SIS assumption, the variant of [ACL+22] defined over the integers does not satisfy extractability (i.e., the existence of an efficient extractor for our adversarial strategy implies a non-uniform polynomial-time algorithm for inhomogeneous SIS). Note that due to the way we construct the basis for the related lattice, our approach can be used to (heuristically) break inhomogeneous SIS, but not necessarily SIS. We refer to Sect. 4.1 for more details.

We describe our methodology and attack algorithms in Sect. 4. We stress that our oblivious sampling attacks only apply to extractability of lattice-based functional commitments; all of the aforementioned schemes still plausibly satisfy the standard notion of binding security for functional commitments. We hope that our techniques will encourage further cryptanalysis of lattice-based knowledge assumptions (and also of the new falsifiable assumptions such as $\ell$-succinct SIS) that underlie succinct commitments and arguments from lattices.

1.3 Related Work

Interactive functional commitments were first introduced in [IKO07] (for linear functions) and extended to general functions in [BC12] for realizing (interactive) succinct arguments without relying on traditional probabilistically-checkable proofs. In the interactive setting, we can also obtain a functional commitment from any collision-resistant hash function via Kilian’s interactive succinct argument [Kil92]. This can be made non-interactive in the random oracle model [Mic00] through the Fiat-Shamir heuristic. Functional commitments are also generically implied by succinct non-interactive arguments (SNARKs), but constructions of SNARKs either rely on strong non-falsifiable assumptions [GW11] or rely on idealized models (e.g., the random oracle model or the generic group model). Our focus in this work is on non-interactive functional commitments in the plain model from falsifiable assumptions.

There have also been numerous constructions of functional commitments (and its specialization to vector and polynomial commitments) from standard pairing-based assumptions [LY10, KZG10, CF13, LRY16, LM19, TAB+20, GRWZ20, BCFL22] as well as assumptions over groups of unknown order such as RSA groups or class groups [CF13, LM19, CFG+20, AR20, TXN20]. We refer to [Nit21] for a survey of recent constructions. Our focus in this work is on functional commitments from lattice assumptions (similar to [PPS21, ACL+22, BCFL22, dCP23, WW23]). The work of [GVW15b] construct non-succinct functional commitments for arbitrary functions and fast verification from SIS; non-succinct functional commitments are often referred to as homomorphic commitments.

RAM Delegation. A RAM delegation scheme [KP16, BHK17, KPY19, CJJ21, KVZ21, KLVW23] allows a prover to compute a short digest of an input x and later on, convince the verifier that $M(x) = y$ for an arbitrary RAM program M with a proof whose size scales with $\textsf{poly}(\lambda , \log |x|, \log T)$, where T is the running time of the RAM computation. A RAM delegation scheme can be used to obtain a functional commitment for circuits by having the digest be over the pair (x, C), where x is the input and C is the circuit, and taking M to be the RAM program that evaluates C gate-by-gate. There is a slight syntactic mismatch here because in a functional commitment scheme, the user should be able to commit to the input x (resp., in the dual case, the circuit C) separately, and later on, open the commitment to the circuit C (resp., at the input x). However, if the underlying digest-computation algorithm has the property that the digest for the pair (x, C) can be derived from independent digests for x and C separately, then it is possible to obtain a functional commitment scheme for circuits. In recent RAM delegation schemes [CJJ21, KVZ21, KLVW23], the digest is just a Merkle hash of the inputs [Mer87], which satisfies this requirement.

Taken together, the RAM delegation schemes from [CJJ21, KVZ21] yields a functional commitments from circuits that satisfy the weaker notion of target binding security (where binding is only required to hold for honestly-generated commitments). The construction of Kalai et al.  [KLVW23] yields a functional commitment for general circuits satisfies the standard notion of evaluation binding for functional commitments.⁶ This yields a functional commitment scheme for all circuits from the plain LWE assumption; notably, this scheme has a transparent setup and $\textsf{poly}(\lambda , \log |x|, \log |C|)$ common reference string, commitment, and opening. The main limitation of the RAM delegation approaches is their heavy non-black-box use of cryptography. Namely, the constructions require the circuit description of cryptographic hash functions and lattice sampling algorithms. In this work, we focus on constructions that only make black-box use of cryptographic algorithms (and lattice sampling algorithms).

Relation to [Wee23]. The $\ell$-succinct SIS assumption we rely on in this work was recently introduced by [Wee23], who showed how to use it (specifically, its extension to $\ell$-succinct LWE) to construct succinct attribute-based encryption, reusable garbled circuits, and laconic functional encryption. The main technical result there is an attribute-based encryption scheme that achieves ciphertext overhead and key size $\textsf{poly}(\lambda ,d)$ (independent of both the attribute length and circuit size) for circuits of depth d under the $\ell$-succinct LWE assumption. These aforementioned applications exploit the fact that the trapdoor $[\textbf{I}_\ell \otimes \textbf{A}~|~ \textbf{W}]$ can be used to “compress” the homomorphic evaluation matrix $\textbf{H}_{\textbf{B}, f, \textbf{x}}$, which is also the approach we take for compressing our openings in our dual functional commitment scheme.

We refer to [Wee23] for more discussion on the $\ell$-succinct SIS and LWE assumptions, including reductions basing these assumptions on the evasive LWE assumption [Wee22, Tsa22]. In particular, $\ell$-succinct SIS is implied by both the $\textsf{BASIS}_{\textsf{struct}}$ assumption from [WW23] (the latter is in turn implied by matrix variants of k-R-$\textsf{ISIS}$, as shown in [WW23, §6]) and the evasive LWE assumption (plus LWE). That is, $\ell$-succinct SIS constitutes the “weakest” of recent non-standard lattice assumptions used in functional commitments as well as other advanced lattice-based cryptosystems.

Concurrent Work. Concurrent to this work, [FLV23, CLM23] gave new constructions of lattice-based SNARKs with a linear-size CRS based on the knowledge k-R-ISIS assumption from [ACL+22]. The construction of [FLV23] leverage the k-R-ISIS assumption to construct a polynomial commitment with a linear-size CRS; in conjunction with the knowledge variant of the k-R-ISIS assumption, they obtain a lattice-based preprocessing SNARK for $\textsf{NP}$ with a linear-size CRS and quasilinear prover complexity. The work of [CLM23] introduces the vanishing SIS problem and uses it to construct functional commitments for quadratic functions (and correspondingly, a preprocessing SNARK for $\textsf{NP}$). They provide two ways to instantiate their SNARK: in the plain model under the knowledge variant of the k-R-ISIS assumption, or in the random oracle model under the new, but falsifiable vanishing SIS assumption. The results we show in this work provide strong evidence against the plausibility of the knowledge k-R-ISIS assumption. It is an interesting question to study whether our approach can be used to directly break soundness of these new SNARK candidates.

2 Preliminaries

We write $\lambda$ to denote the security parameter. For a positive integer $n \in \mathbb {N}$, we write [n] to denote the set $\{ 1, \ldots , n \}$. For a positive integer $q \in \mathbb {N}$, we write $\mathbb {Z}_{q}$ to denote the integers modulo q. We use bold uppercase letters to denote matrices (e.g., $\textbf{A}, \textbf{B}$) and bold lowercase letters to denote vectors (e.g., $\textbf{u}$, $\textbf{v}$). We use non-boldface letters to refer to their components: $\textbf{v}= (v_1, \ldots , v_n)$. We write $\textbf{I}_\ell$ to denote the $\ell$-by-$\ell$ identity matrix.

We write $\textsf{poly}(\lambda )$ to denote a fixed function that is $O(\lambda ^c)$ for some $c \in \mathbb {N}$ and $\textsf{negl}(\lambda )$ to denote a function that is $o(\lambda ^{-c})$ for all $c \in \mathbb {N}$. For functions $f = f(\lambda ), g = g(\lambda )$, we write $g \ge O(f)$ to denote that there exists a fixed function $f'(\lambda ) = O(f)$ such that $g(\lambda ) > f'(\lambda )$ for all $\lambda \in \mathbb {N}$. We say an event occurs with overwhelming probability if its complement occurs with negligible probability. An algorithm is efficient if it runs in probabilistic polynomial time in its input length. We say that two families of distributions $\mathcal {D}_1 = \{ \mathcal {D}_{1, \lambda } \}_{\lambda \in \mathbb {N}}$ and $\mathcal {D}_2 = \{ \mathcal {D}_{2, \lambda } \}_{\lambda \in \mathbb {N}}$ are computationally indistinguishable if no efficient algorithm can distinguish them with non-negligible probability, and we denote this by writing $\mathcal {D}_1 {\mathop {\approx }\limits ^{c}}\mathcal {D}_2$. We say that $\mathcal {D}_1$ and $\mathcal {D}_2$ are statistically indistinguishable if the statistical distance $\varDelta (\mathcal {D}_1, \mathcal {D}_2)$ is bounded by a negligible function $\textsf{negl}(\lambda )$.

Tensor Products. For matrices $\textbf{A}\in \mathbb {Z}_{q}^{n \times m}$ and $\textbf{B}\in \mathbb {Z}_{q}^{k \times \ell }$, we write $\textbf{A}\otimes \textbf{B}$ to denote the tensor (Kronecker) product of $\textbf{A}$ and $\textbf{B}$. For a positive integer $i \in \mathbb {N}$, we write $\textbf{A}^{\otimes i}$ to denote tensoring $\textbf{A}$ with itself i times. For matrices $\textbf{A}, \textbf{B}, \textbf{C}, \textbf{D}$ where the products $\textbf{A}\textbf{C}$ and $\textbf{B}\textbf{D}$ are well-defined, the tensor product satisfies the following mixed-product property:

$$\begin{aligned} (\textbf{A}\otimes \textbf{B})(\textbf{C}\otimes \textbf{D}) = (\textbf{A}\textbf{C}) \otimes (\textbf{B}\textbf{D}). \end{aligned}$$

(2.1)

The following is a useful consequence of the mixed-product property. For a vector $\textbf{x}$ and a matrix $\textbf{A}$,

$$\begin{aligned} (\textbf{x}\otimes \textbf{I}) \textbf{A}= (\textbf{x}\otimes \textbf{I}) (1 \otimes \textbf{A}) = \textbf{x}\otimes \textbf{A}. \end{aligned}$$

(2.2)

Vectorization. For a matrix $\textbf{A}\in \mathbb {Z}_{q}^{n \times m}$, we write $\textrm{vec}(\textbf{A})$ to denote its vectorization (i.e., the vector formed by vertically stacking the columns of $\textbf{A}$ from leftmost to rightmost). We will use the following useful identity: for matrices $\textbf{A}, \textbf{B}, \textbf{C}$ where the product $\textbf{A}\textbf{B}\textbf{C}$ is well-defined, then

$$\begin{aligned} \textrm{vec}(\textbf{A}\textbf{B}\textbf{C}) = (\textbf{C}^{\scriptscriptstyle \textsf{T}}\otimes \textbf{A}) \cdot \textrm{vec}(\textbf{B}). \end{aligned}$$

Lattice Preliminaries. Throughout this work, we let $\chi$ denote a Gaussian width parameter. We review some preliminaries on lattice-based cryptography in the full version of this paper.

2.1 Functional Commitments

In this section, we recall the formal definition of a (succinct) functional commitment. Our definition is adapted from that of [WW23].

Definition 2.1

(Succinct Functional Commitment [WW23, Definition 4.1]). Let $\lambda$ be a security parameter. Let $\mathcal {F}= \{ \mathcal {F}_{\lambda } \}_{\lambda \in \mathbb {N}}$ be a family of efficiently-computable functions $f :\mathcal {X}^\ell \rightarrow \mathcal {Y}^T$ with domain $\mathcal {X}^\ell$ and range $\mathcal {Y}^T$; here $\ell = \ell (\lambda )$ and $T = T(\lambda )$ denote the input dimension and the output dimension, respectively. A succinct functional commitment for $\mathcal {F}$ is a tuple of efficient algorithms $\varPi _{\textsf{FC}}= (\textsf{Setup}, \textsf{Commit}, \textsf{Eval}, \textsf{Verify})$ with the following properties:

• $\textsf{Setup}(1^\lambda ) \rightarrow \textsf{crs}$: On input the security parameter $\lambda$, the setup algorithm outputs a common reference string $\textsf{crs}$.

• $\textsf{Commit}(\textsf{crs}, \textbf{x}) \rightarrow (\sigma , \textsf{st})$: On input the common reference string $\textsf{crs}$ and an input $\textbf{x}\in \mathcal {X}^\ell$, the commitment algorithm outputs a commitment $\sigma$ and a state $\textsf{st}$.

• $\textsf{Eval}(\textsf{st}, f) \rightarrow \pi _f$: On input a commitment state $\textsf{st}$ and a function $f \in \mathcal {F}$, the evaluation algorithm outputs an opening $\pi _f$.

• $\textsf{Verify}(\textsf{crs}, \sigma , f, \textbf{y}, \pi ) \rightarrow \{0,1\}$: On input the common reference string $\textsf{crs}$, a commitment $\sigma$, a function $f \in \mathcal {F}$, a value $\textbf{y}\in \mathcal {Y}^T$, and an opening $\pi$, the verification algorithm outputs a bit $b \in \{0,1\}$.

We now define several correctness and security properties on the functional commitment scheme:

• Correctness: For all security parameters $\lambda$, all functions $f \in \mathcal {F}$, and all inputs $\textbf{x}\in \mathcal {X}^\ell$,

  $$ \Pr \left[ \textsf{Verify}\big ( \textsf{crs}, \sigma , f, f(\textbf{x}), \pi _f \big ) = 1 : \begin{array}{c} \textsf{crs}\leftarrow \textsf{Setup}(1^\lambda ); \\ (\sigma , \textsf{st}) \leftarrow \textsf{Commit}(\textsf{crs}, \textbf{x}); \\ \pi _f \leftarrow \textsf{Eval}(\textsf{st}, f) \end{array} \right] = 1 - \textsf{negl}(\lambda ). $$

• Succinctness: There exists a universal polynomial $\textsf{poly}(\cdot )$ such that for all $\lambda \in \mathbb {N}$, $|\sigma | = \textsf{poly}(\lambda , \log \ell )$ and $\left| \pi _f \right| = \textsf{poly}(\lambda , \log \ell , T)$ in the correctness definition.

• Binding: We say $\varPi _{\textsf{FC}}$ satisfies statistical (resp., computational) binding if for all adversaries $\mathcal {A}$ (resp., efficient adversaries $\mathcal {A}$),

  $$ \Pr \left[ \textsf{Verify}(\textsf{crs}, \sigma , f, y_0, \pi _0) = 1 = \textsf{Verify}(\textsf{crs}, \sigma , f, y_1, \pi _1) \right] = \textsf{negl}(\lambda ), $$

  where $\textsf{crs}\leftarrow \textsf{Setup}(1^\lambda , 1^{\ell }, 1^d)$ and $(\sigma , f, (y_0, \pi _0), (y_1, \pi _1)) \leftarrow \mathcal {A}(1^\lambda , 1^\ell , 1^d, \textsf{crs})$.

Functional Commitments with Preprocessing. In many constructions of functional commitments, verifying an opening with respect to a function f requires time that scales with the running time of f and the size of the opening often scales with the output dimension T. In settings where the function f and the target $\textbf{y}$ are known in advance (e.g., f could encode a list of predicates and the output $\textbf{y}$ could be the all-ones vector, indicating that every predicate should be satisfied by the committed input)), it is sometimes possible to decompose the verification algorithm into a “slow” offline step that takes as input the function f and the target output $\textbf{y}$ and outputs a verification key $\textsf{vk}_{f, \textbf{y}}$. Importantly, $\textsf{vk}_{f, \textbf{y}}$ is independent of the commitment and the opening. Then, there is a fast online verification algorithm that uses the preprocessed verification key to validate the commitment and opening in time that is sublinear in the size of f and the number of outputs T.

In Remark 3.3, we note that it is also possible to preprocess the verification key when only the function f is known in advance. In this case, the online verification algorithm will need to run in time that grows with the output dimension T (since the verifier necessarily has to read the output in this case). Several recent schemes support fast verification with preprocessing [ACL+22, dCP23, BCFL22]. We define this below:

Definition 2.2

(Functional Commitment with Full Preprocessing). Let $\lambda$ be a security parameter. Let $\mathcal {F}= \{ \mathcal {F}_{\lambda } \}_{\lambda \in \mathbb {N}}$ be a family of efficiently-computable functions $f :\mathcal {X}^\ell \rightarrow \mathcal {Y}^T$ where each function f can be computed by a Boolean circuit of size at most $s = s(\lambda )$. Let $\varPi _{\textsf{FC}}= (\textsf{Setup}, \textsf{Commit}, \textsf{Eval}, \textsf{Verify})$ be a succinct functional commitment for $\mathcal {F}$. We say that $\mathcal {F}$ supports preprocessing if the verification algorithm can be decomposed into two efficient algorithms $(\textsf{Preprocess}, \textsf{OnlineVerify})$ with the following syntax:

• $\textsf{Preprocess}(\textsf{crs}, f, \textbf{y}) \rightarrow \textsf{vk}_{f, \textbf{y}}$: On input the common reference string $\textsf{crs}$, a function $f \in \mathcal {F}$, and an output $\textbf{y}\in \mathcal {Y}^T$, the preprocess algorithm outputs a verification key $\textsf{vk}_{f, \textbf{y}}$.

• $\textsf{OnlineVerify}(\textsf{vk}, \sigma , \pi ) \rightarrow \{0,1\}$: On input a verification key $\textsf{vk}$, a commitment $\sigma$, and an opening $\pi$, the online verification algorithm outputs a bit $b \in \{0,1\}$.

We require that

$$\begin{aligned} \textsf{Verify}(\textsf{crs}, \sigma , f, \textbf{y}, \pi ) \mathrel {\mathop :}=\textsf{OnlineVerify}(\textsf{Preprocess}(\textsf{crs}, f, \textbf{y}), \sigma , \pi ). \end{aligned}$$

In addition, we require the additional succinctness property:

• Fast Online Verification: There exists a universal polynomial $\textsf{poly}(\cdot )$ such that for all $\lambda \in \mathbb {N}$, for $\textsf{crs}\leftarrow \textsf{Setup}(1^\lambda )$, all functions $f \in \mathcal {F}$, and all outputs $\textbf{y}\in \mathcal {Y}^T$, the verification key $\textsf{vk}_{f, \textbf{y}}$ output by $\textsf{Preprocess}(\textsf{crs}, f, \textbf{y})$ satisfies $\left| \textsf{vk}_{f, \textbf{y}} \right| = \textsf{poly}(\lambda , \log s, \log T)$, and moreover, the running time of $\textsf{OnlineVerify}$ is $\textsf{poly}(\lambda , \log s, \log T)$.

Remark 2.3

(Function-Only Preprocessing). We can also consider functional commitments with a weaker function-only preprocessing where the preprocessing algorithm $\textsf{Preprocess}$ only takes the $\textsf{crs}$ and the function f as input (but not the output $\textbf{y}$) and outputs a preprocessed function key $\textsf{vk}_f$. Then, the online verification algorithm $\textsf{OnlineVerify}$ takes the verification key $\textsf{vk}_f$, the output $\textbf{y}\in \mathcal {Y}^T$, the commitment $\sigma$, and the opening $\pi$ as input. In this case, we require that the size of the verification key $\textsf{vk}_f = \textsf{poly}(\lambda , \log s)$, and the verification time to be $\textsf{poly}(\lambda , \log s, T)$. Notably, the online verification algorithm can now depend on the output dimension T (and this is required since the verification algorithm must read the output).

3 Functional Commitments with Fast Verification

In this section, we show how to construct a functional commitment for constant-degree polynomials that support fast verification. Security of our construction relies on the $\ell$-succinct short integer solutions problem from [Wee23], which we recall below:

Assumption 3.1

($\ell$-Succinct SIS [Wee23]). Let $\lambda$ be a security parameter and $n = n(\lambda ), m = m(\lambda ), q = q(\lambda )$, $\chi = \chi (\lambda )$, and $\beta = \beta (\lambda )$ be lattice parameters. We say that the $\ell$-succinct SIS assumption with parameters $(n, m, q, \chi , \beta )$ holds if for all efficient adversaries $\mathcal {A}$,

As suggested in [Wee23], we consider parameter settings for $(n, m, q, \beta )$ where $\textsf{SIS} _{n, m, q, \beta }$ hold and where $\chi = \textsf{poly}(\lambda , m, \ell )$.

Construction 3.2

(Functional Commitment for Constant-Degree Polynomials). Let $\lambda$ be a security parameter and $n = n(\lambda )$, $m = m(\lambda )$, $q = q(\lambda )$, $\chi = \chi (\lambda )$ be lattice parameters. Let $\ell = \ell (\lambda )$ be an input length parameter, ${d_{\textrm{max}}}= O(1)$ be a constant degree bound, $B_{\textsf{in}}= B_{\textsf{in}}(\lambda )$ be a bound on the magnitude of the inputs, and $B_{\textsf{out}}= B_{\textsf{out}}(\lambda )$ be a bound on the magnitude of the outputs. Let $L = \sum _{i \in [{d_{\textrm{max}}}]} \ell ^i$ and $B = B(\lambda )$ be a verification bound. Let $\mathcal {F}_\lambda$ be the set of functions $f :[-B_{\textsf{in}}, B_{\textsf{in}}]^\ell \rightarrow [-B_{\textsf{out}}, B_{\textsf{out}}]$ where f can be computed by a homogeneous polynomial⁷ with $B_{\textsf{in}}$-bounded coefficients and degree at most ${d_{\textrm{max}}}$. We associate a function $f \in \mathcal {F}_\lambda$ with a vector $\textbf{f}\in [-B_{\textsf{in}}, B_{\textsf{in}}]^{\ell ^d}$ for some $d \le {d_{\textrm{max}}}$ and define $f(\textbf{x}) \mathrel {\mathop :}=\textbf{f}^{\scriptscriptstyle \textsf{T}}\textbf{x}^{\otimes d}$. We construct a functional commitment $\varPi _{\textsf{FC}}= (\textsf{Setup}, \textsf{Commit}, \textsf{Eval}, \textsf{Verify})$ for $\mathcal {F}= \{ \mathcal {F}_{\lambda } \}_{\lambda \in \mathbb {N}}$ as follows:

• $\textsf{Setup}(1^\lambda )$: On input the security parameter $\lambda$, the setup algorithm samples $(\textbf{A}, \textbf{R}) \leftarrow \textsf{TrapGen}(1^n, q, m)$ and . Next, define the target matrix

  $$\begin{aligned} \textbf{P}= \begin{bmatrix} \textbf{I}_\ell \otimes \textbf{G}\\ \textbf{I}_\ell \otimes \textbf{W}_1 \\ \vdots \\ \textbf{I}_\ell \otimes \textbf{W}_{{d_{\textrm{max}}}- 1} \end{bmatrix} \in \mathbb {Z}_{q}^{L n \times \ell m} \quad \text {where} \quad \textbf{W}= \begin{bmatrix} \textbf{W}_1 \\ \vdots \\ \textbf{W}_{{d_{\textrm{max}}}} \end{bmatrix} \in \mathbb {Z}_{q}^{L n \times m}, \end{aligned}$$

  (3.1)

  where $\textbf{W}_i \in \mathbb {Z}_{q}^{\ell ^i n \times m}$. Then, compute $\textbf{T}\leftarrow \textsf{SamplePre}([\textbf{I}_L \otimes \textbf{A}~|~ \textbf{W}], \textbf{I}_L \otimes \textbf{R}, \textbf{P}, \chi ) \in \mathbb {Z}_{q}^{(L m + m) \times \ell m}$. Parse where $\textbf{T}_{\textsf{open}}\in \mathbb {Z}_{q}^{L m \times \ell m}$ and $\textbf{T}_{\textsf{com}}\in \mathbb {Z}_{q}^{m \times \ell m}$. Output the common reference string $\textsf{crs}= (\textbf{A}, \textbf{W}, \textbf{T}_{\textsf{com}}, \textbf{T}_{\textsf{open}})$.

• $\textsf{Commit}(\textsf{crs}, \textbf{x})$: On input the common reference string $\textsf{crs}= (\textbf{A}, \textbf{W}, \textbf{T}_{\textsf{com}}, \textbf{T}_{\textsf{open}})$ and an input $\textbf{x}\in [-B_{\textsf{in}}, B_{\textsf{in}}]^\ell$, the commit algorithm outputs the commitment $\sigma = \textbf{C}= \textbf{T}_{\textsf{com}}(\textbf{x}\otimes \textbf{I}_m) \in \mathbb {Z}_{q}^{m \times m}$ and the state $\textsf{st}= \textbf{x}$.

• $\textsf{Eval}(\textsf{crs}, \textsf{st}, f)$: On input the common reference string $\textsf{crs}= (\textbf{A}, \textbf{W}, \textbf{T}_{\textsf{com}}, \textbf{T}_{\textsf{open}})$, the state $\textsf{st}= \textbf{x}$, and a function $f = \textbf{f}\in \mathbb {Z}_{q}^{\ell ^d}$ (for some $d \le {d_{\textrm{max}}}$) with $B_{\textsf{in}}$-bounded coefficients, the evaluation algorithm first computes $\textbf{V}= \textbf{T}_{\textsf{open}}(\textbf{x}\otimes \textbf{I}_m)$. It then parses

  $$\begin{aligned} \textbf{V}= \begin{bmatrix} \textbf{V}_1 \\ \vdots \\ \textbf{V}_{d_{\textrm{max}}}\end{bmatrix} \in \mathbb {Z}_{q}^{L m \times m} \end{aligned}$$

  (3.2)

  where $\textbf{V}_i \in \mathbb {Z}_{q}^{\ell ^i m \times m}$. Let $\textbf{V}_1' \leftarrow \textbf{V}_1$ and for $i \in [d]$, let $\textbf{V}_i' \leftarrow (\textbf{x}\otimes \textbf{I}_{\ell ^{i - 1} m}) \textbf{V}_{i - 1}' + \textbf{V}_i \textbf{C}^{i - 1} \in \mathbb {Z}_{q}^{\ell ^i m \times m}$. Equivalently, in expanded form, we can write

  $$\begin{aligned} \textbf{V}_i' &= \textbf{V}_i \textbf{C}^{i - 1} + (\textbf{x}\otimes \textbf{I}_{\ell ^{i - 1} m}) \textbf{V}_{i - 1} \textbf{C}+ (\textbf{x}^{\otimes 2} \otimes \textbf{I}_{\ell ^{i - 2} m}) \textbf{V}_{i - 2} \textbf{C}^2 + \cdots + (\textbf{x}^{\otimes i - 1} \otimes \textbf{I}_{\ell m}) \textbf{V}_1 \\ &= \sum _{j \in [i]} (\textbf{x}^{\otimes i - j} \otimes \textbf{I}_{\ell ^{j} m}) \textbf{V}_j \textbf{C}^{j - 1} \end{aligned}$$

  Output the opening $\pi _f = \textbf{V}_f = (\textbf{f}^{\scriptscriptstyle \textsf{T}}\otimes \textbf{I}_m) \textbf{V}_d' \in \mathbb {Z}_{q}^{m \times m}$.

• $\textsf{Verify}(\textsf{crs}, \sigma , f, y, \pi )$: On input $\textsf{crs}= (\textbf{A}, \textbf{W}, \textbf{T}_{\textsf{com}}, \textbf{T}_{\textsf{open}})$, the commitment $\sigma = \textbf{C}\in \mathbb {Z}_{q}^{m \times m}$, the output $y \in [-B_{\textsf{out}}, B_{\textsf{out}}]$, a function $f = \textbf{f}\in \mathbb {Z}_{q}^{\ell ^d}$ (for some $d \le {d_{\textrm{max}}}$) with $B_{\textsf{in}}$-bounded coefficients, and the proof $\pi = \textbf{V}\in \mathbb {Z}_{q}^{m \times m}$, the verification algorithm first parses $\textbf{W}$ into $\textbf{W}_1, \ldots , \textbf{W}_{d_{\textrm{max}}}$ as in Eq. (3.1) and outputs 1 if

  $$\begin{aligned} \left\| \textbf{V} \right\| \le B \quad \text {and} \quad (\textbf{f}^{\scriptscriptstyle \textsf{T}}\otimes \textbf{I}_m) \textbf{W}_d \textbf{C}^d = y \cdot \textbf{G}- \textbf{A}\textbf{V}. \end{aligned}$$

  (3.3)

Remark 3.3

(Supporting Preprocessing). Similar to previous (non-succinct) homomorphic commitments [GVW15b] and succinct functional commitments [ACL+22, dCP23, BCFL22], our functional commitment Construction 3.2 supports fast verification in the preprocessing model. Note that since the output dimension is 1, we do not distinguish between function-only preprocessing (Remark 2.3) and full preprocessing (Definition 2.2). We define the preprocessing and online verification algorithms as follows:

• $\textsf{Preprocess}(\textsf{crs}, f)$: On input $\textsf{crs}= (\textbf{A}, \textbf{W}, \textbf{T}_{\textsf{com}}, \textbf{T}_{\textsf{open}})$ and the function $f = \textbf{f}\in \mathbb {Z}_{q}^{\ell ^d}$ for some $d \le {d_{\textrm{max}}}$, the preprocess algorithm outputs $\textsf{vk}_f = \textbf{F}_d = (\textbf{f}^{\scriptscriptstyle \textsf{T}}\otimes \textbf{I}_m) \textbf{W}_d \in \mathbb {Z}_{q}^{n \times m}$.

• $\textsf{OnlineVerify}(\textsf{vk}, \sigma , y, \pi )$: On input the verification key $\textsf{vk}= \textbf{F}_d$, the commitment $\sigma = \textbf{C}\in \mathbb {Z}_{q}^{m \times m}$, the value $y \in [-B_{\textsf{out}}, B_{\textsf{out}}]$, and the opening $\pi = \textbf{V}\in \mathbb {Z}_{q}^{m \times m}$, the online verification algorithm outputs 1 if

  $$\begin{aligned} \left\| \textbf{V} \right\| \le B \quad \text {and} \quad \textbf{F}_d \cdot \textbf{C}^d = y \cdot \textbf{G}- \textbf{A}\textbf{V}. \end{aligned}$$

By construction, $\left| \textbf{F}_d \right| = n m \log q$ and similarly, the online verification algorithm runs in time $\textsf{poly}(n, m, {d_{\textrm{max}}}, \log q)$. We can set the parameters for Construction 3.2, so $n, m, \log q$ scale polylogarithmically with the input dimension $\ell$.

Remark 3.4

(Supporting Non-homogeneous Polynomials). It is straightforward to extend a functional commitment for homogeneous polynomials (i.e., polynomials where every monomial has the same degree) to a functional commitment for inhomogeneous polynomials. Specifically, to support openings to inhomogeneous polynomials over inputs of dimension $\ell$, we instantiate a scheme that supports homogeneous polynomials over inputs of dimension $\ell + 1$. Then to commit to an input $\textbf{x}\in \mathbb {Z}_{q}^\ell$, the committer commits to the extended vector . Now, every inhomogeneous polynomial $f :\mathbb {Z}_{q}^\ell \rightarrow \mathbb {Z}_{q}$ of degree at most d can be described by a homogeneous polynomial $f' :\mathbb {Z}_{q}^{\ell + 1} \rightarrow \mathbb {Z}_{q}$ of degree d where $f'(\textbf{x}') = f(\textbf{x})$. Now, to open to an inhomogeneous polynomial f, the committer instead open to $f'$.

Correctness and Security Analysis. We provide the correctness and security analysis of Construction 3.2 in the full version of this paper.

3.1 Opening to Multiple Outputs

In this section, we describe how to extend Construction 3.2 to obtain a functional commitment scheme that supports succinct openings to multiple outputs (i.e., the size of the opening scales sub-linearly with the number of functions we open to). Our approach follows the approach from [WW23] for aggregating openings.

Construction 3.5

(Multi-output Functional Commitment for Constant-Degree Polynomials). Let $\lambda$ be a security parameter. Let $n, m, q, \chi , \ell , {d_{\textrm{max}}}, B_{\textsf{in}}, B_{\textsf{out}}, B$ be the same parameters as in Construction 3.2. Let $T = T(\lambda )$ be a bound on the number of outputs. Let $\mathcal {F}= \{ \mathcal {F}_\lambda \}_{\lambda \in \mathbb {N}}$ be the set of functions $f :[-B_{\textsf{in}}, B_{\textsf{in}}]^\ell \rightarrow [-B_{\textsf{out}}, B_{\textsf{out}}]^{T}$, where each function f can be described by a vector of homogeneous polynomials $(\textbf{f}_1, \ldots , \textbf{f}_T)$ with $B_{\textsf{in}}$-bounded coefficients and of the same degree $d \le {d_{\textrm{max}}}$:⁸

$$\begin{aligned} f(\textbf{x}) \mathrel {\mathop :}=\big ( \textbf{f}_1^{\scriptscriptstyle \textsf{T}}\textbf{x}^{\otimes d}, \ldots , \textbf{f}_T^{\scriptscriptstyle \textsf{T}}\textbf{x}^{\otimes d} \big ). \end{aligned}$$

We construct a functional commitment $\varPi _{\textsf{FC}}= (\textsf{Setup}, \textsf{Commit}, \textsf{Eval}, \textsf{Verify})$ for $\mathcal {F}= \{ \mathcal {F}_{\lambda } \}_{\lambda \in \mathbb {N}}$ as follows:

• $\textsf{Setup}(1^\lambda )$: Sample $\textbf{A}\in \mathbb {Z}_{q}^{n \times m}$, $\textbf{W}\in \mathbb {Z}_{q}^{L n \times m}$, $\textbf{T}_{\textsf{open}}\in \mathbb {Z}_{q}^{L m \times \ell m}$, and $\textbf{T}_{\textsf{com}}\in \mathbb {Z}_{q}^{m \times \ell m}$ using the same procedure as $\textsf{Setup}$ in Construction 3.2. Sample , and output the common reference string $\textsf{crs}= (\textbf{A}, \textbf{W}, \textbf{T}_{\textsf{com}}, \textbf{T}_{\textsf{open}}, \textbf{D})$.

• $\textsf{Commit}(\textsf{crs}, \textbf{x})$: Same as in Construction 3.2.

• $\textsf{Eval}(\textsf{crs}, \textsf{st}, f)$: On input $\textsf{crs}= (\textbf{A}, \textbf{W}, \textbf{T}_{\textsf{com}}, \textbf{T}_{\textsf{open}}, \textbf{D})$, the state $\textsf{st}= \textbf{x}$, and a function $f = (\textbf{f}_1, \ldots , \textbf{f}_T)$ where each $\textbf{f}_i \in \mathbb {Z}_{q}^{\ell ^d}$ is $B_{\textsf{in}}$-bounded and $d \le {d_{\textrm{max}}}$, the evaluation algorithm first computes an opening $\textbf{V}_{\textbf{f}_i} \in \mathbb {Z}_{q}^{m \times m}$ for $\textbf{f}_i$ using the same procedure as in Construction 3.2. Then, it outputs the opening $\pi _f = \textbf{v}_f$ where

  $$\begin{aligned} \textbf{v}_f = \sum _{i \in [T]} \textbf{V}_{\textbf{f}_i} \textbf{G}^{-1}(\textbf{d}_i) \in \mathbb {Z}_{q}^m, \end{aligned}$$

  and $\textbf{d}_i \in \mathbb {Z}_{q}^n$ denotes the $i^{\textrm{th}}$ column of $\textbf{D}$.

• $\textsf{Verify}(\textsf{crs}, \sigma , f, \textbf{y}, \pi )$: On input $\textsf{crs}= (\textbf{A}, \textbf{W}, \textbf{T}_{\textsf{com}}, \textbf{T}_{\textsf{open}}, \textbf{D})$, the commitment $\sigma = \textbf{C}\in \mathbb {Z}_{q}^{m \times m}$, the function $f = (\textbf{f}_1, \ldots , \textbf{f}_T)$ where each $\textbf{f}_i \in \mathbb {Z}_{q}^{\ell ^{d}}$ is $B_{\textsf{in}}$-bounded and $d \le {d_{\textrm{max}}}$, the output $\textbf{y}\in [-B_{\textsf{out}}, B_{\textsf{out}}]^T$, and the proof $\pi = \textbf{v}\in \mathbb {Z}_{q}^{m}$, the verification algorithm parses $\textbf{W}$ as in Eq. (3.1) and outputs 1 if

  $$\begin{aligned} \left\| \textbf{v} \right\| \le B \quad \text {and} \quad \sum _{i \in [T]} (\textbf{f}_i^{\scriptscriptstyle \textsf{T}}\otimes \textbf{I}_m) \textbf{W}_{d} \textbf{C}^{d} \textbf{G}^{-1}(\textbf{d}_i) = \textbf{D}\textbf{y}- \textbf{A}\textbf{v}, \end{aligned}$$

  (3.4)

  where $\textbf{d}_i \in \mathbb {Z}_{q}^n$ is the $i^{\textrm{th}}$ column of $\textbf{D}$.

Remark 3.6

(Supporting Preprocessing). Like Construction 3.2, Construction 3.5 supports full preprocessing (Definition 2.2) and function-only preprocessing (Remark 2.3). Here, we describe the approach for full preprocessing.

• $\textsf{Preprocess}(\textsf{crs}, f, \textbf{y})$: On input $\textsf{crs}= (\textbf{A}, \textbf{W}, \textbf{T}_{\textsf{com}}, \textbf{T}_{\textsf{open}}, \textbf{D})$, the function $f = (\textbf{f}_1, \ldots , \textbf{f}_T)$ where each $\textbf{f}_i \in \mathbb {Z}_{q}^{\ell ^{d}}$ is $B_{\textsf{in}}$-bounded and $d \le {d_{\textrm{max}}}$, and the output $\textbf{y}\in [-B_{\textsf{out}}, B_{\textsf{out}}]^T$, the preprocessing algorithm computes

  $$\begin{aligned} \textbf{F}&= \sum _{i \in [T]} \left( \big ( \textbf{G}^{-1}(\textbf{d}_i) \big )^{\scriptscriptstyle \textsf{T}}\otimes (\textbf{f}_i^{\scriptscriptstyle \textsf{T}}\otimes \textbf{I}_m) \textbf{W}_d \right) \in \mathbb {Z}_{q}^{n \times m^2} \end{aligned}$$

  (3.5)
  $$\begin{aligned} \textbf{y}^*&= \textbf{D}\textbf{y}\in \mathbb {Z}_{q}^n, \end{aligned}$$

  (3.6)

  and outputs the verification key $\textsf{vk}_{f, \textbf{y}} = (\textbf{F}, \textbf{y}^*)$.

• $\textsf{OnlineVerify}(\textsf{vk}, \sigma , \pi )$: On input the verification key $\textsf{vk}= (\textbf{F}, \textbf{y}^*)$, the commitment $\sigma = \textbf{C}\in \mathbb {Z}_{q}^{m \times m}$, and the opening $\pi = \textbf{v}\in \mathbb {Z}_{q}^{m}$, the online verification algorithm outputs 1 if

  $$\begin{aligned} \left\| \textbf{v} \right\| \le B \quad \text {and} \quad \textbf{F}\cdot \textrm{vec}(\textbf{C}^d) = \textbf{y}^*- \textbf{A}\textbf{v}. \end{aligned}$$

To show that this is correct, we apply vectorization to the main verification relation in Eq. (3.4):

$$ \textrm{vec}\left( \sum _{i \in [T]} (\textbf{f}_i^{\scriptscriptstyle \textsf{T}}\otimes \textbf{I}_m) \textbf{W}_{d} \textbf{C}^{d} \textbf{G}^{-1}(\textbf{d}_i) \right) = \underbrace{\sum _{i \in [T]} \left( \big ( \textbf{G}^{-1}(\textbf{d}_i) \big )^{\scriptscriptstyle \textsf{T}}\otimes (\textbf{f}_i^{\scriptscriptstyle \textsf{T}}\otimes \textbf{I}_m) \textbf{W}_d \right) }_{\textbf{F}} \textrm{vec}(\textbf{C}^d). $$

Then, the main verification relation in Eq. (3.4) becomes

$$\begin{aligned} \textbf{F}\cdot \textrm{vec}(\textbf{C}^d) = \textbf{D}\textbf{y}- \textbf{A}\textbf{v}= \textbf{y}^*- \textbf{A}\textbf{v}, \end{aligned}$$

and correctness reduces to that of Construction 3.5. By construction, $| \textsf{vk}_{f, \textbf{y}} | = (n m^2 + n) \log q$ and the running time of $\textsf{OnlineVerify}$ is $\textsf{poly}(n, m, {d_{\textrm{max}}}, \log q)$. As we show below, we can instantiate our scheme so that $n, m, \log q = \textsf{poly}(\lambda , \log \ell , \log T)$, and so the construction satisfies the required efficiency properties. Finally, the above analysis also applies to function-only preprocessing: namely, the preprocessed function key for a function $f = (\textbf{f}_1, \ldots , \textbf{f}_T)$ is the matrix $\textbf{F}$ from Eq. (3.5). In this case, the running time of verification becomes $\textsf{poly}(n, m, \log q, T)$.

Correctness and Security Analysis. We provide the correctness and security analysis as well as the parameter instantiation in the full version of this paper. We summarize the results in the following corollary:

Corollary 3.7

(Succinct Functional Commitment for Constant-Degree Polynomials). Let $\lambda$ be a security parameter, and let $\mathcal {F}= \{ \mathcal {F}_{\lambda } \}_{\lambda \in \mathbb {N}}$ be a family of functions $f :[-B_{\textsf{in}}, B_{\textsf{in}}]^\ell \rightarrow [-B_{\textsf{out}}, B_{\textsf{out}}]^T$ on inputs of length $\ell = \ell (\lambda )$ and magnitude $B_{\textsf{in}}= \textsf{poly}(\lambda )$, and outputs of length $T = T(\lambda )$ and magnitude $B_{\textsf{out}}= \textsf{poly}(\lambda )$, and where each function f can be described by a vector of T homogeneous polynomials with $B_{\textsf{in}}$-bounded coefficients and degree $d \le {d_{\textrm{max}}}= O(1)$. Then, under the L-succinct SIS assumption (with $L = O(\ell ^{{d_{\textrm{max}}}})$) and a polynomial norm bound, there exists a succinct functional commitment for $\mathcal {F}$. The commitment and opening have size $\textsf{poly}(\lambda , {d_{\textrm{max}}}, \log \ell , \log T)$ and the CRS has size $\ell ^{{d_{\textrm{max}}}+ 1} \cdot \textsf{poly}(\lambda , {d_{\textrm{max}}}, \log \ell , \log T)$. The functional commitment supports full preprocessing (Definition 2.2) and function-only preprocessing (Remark 2.3). With full preprocessing, the running time of the online verification algorithm is $\textsf{poly}(\lambda , {d_{\textrm{max}}}, \log \ell , \log T)$.

Remark 3.8

(Shorter Commitment and Openings). We can reduce the commitment size to $O(n^2 \log q)$ and the opening size to $O(n \log q)$ in the above construction by using a gadget matrix with a larger decomposition base (specifically, instead of considering a binary decomposition, we consider a z-ary gadget matrix where $z = q^{1 / c}$ for a large constant $c \in \mathbb {N}$). This coincides with the approach taken in [ACL+22]. In addition, we can further reduce the size of the commitment by using module lattices instead of integer lattices. We provide the details on extending to modules and using a z-ary gadget decomposition in the full version of this paper.

3.2 A Dual Construction for Committing to Functions

In this section, we construct a functional commitment that supports committing to a function $f :\{0,1\}^\ell \rightarrow \{0,1\}$ and then opening the commitment at a particular input $\textbf{x}\in \{0,1\}^\ell$. This is a dual notion of Definition 2.1, where the $\textsf{Commit}$ algorithm takes as input the function f and the $\textsf{Eval}$ algorithm takes as input an input vector $\textbf{x}$. We often refer to this variant of functional commitment as a “dual functional commitment.”

Here, we consider a construction for general Boolean functions f on inputs of length $\ell = \ell (\lambda )$ and computable by Boolean circuits with bounded depth $d = d(\lambda )$. Similar to [dCP23, WW23], we allow the length of the commitment and the openings to scale with $\textsf{poly}(\lambda , d, \log \ell )$. We can view our construction as a hybrid of the dual functional commitment from [dCP23] and the attribute-based encryption (ABE) scheme from [Wee23].

Like the construction of [dCP23], our functional commitment scheme satisfies a weaker notion of binding called “selective-input security” where the adversary is required to first commit to the point $\textbf{x}\in \{0,1\}^\ell$ to which it will construct an opening. The adversary has to commit to this input before seeing the public parameters. The security reduction will then program $\textbf{x}$ into the public parameters itself. This limitation to a selective notion of security is common to many related lattice-based primitives such as attribute-based encryption [GVW13, BGG+14, GVW15a, Wee23] and constrained PRFs [BV15, BTVW17]. We now give the formal definition of selective-input binding and then show how to use the $\ell$-succinct SIS assumption to construct a succinct dual functional commitment for Boolean circuits with succinct commitments, openings, and fast verification (in the preprocessing model).

Definition 3.9

(Selective-Input Binding Security). Let $\lambda$ be a security parameter, and let $\mathcal {F}= \{ \mathcal {F}_\lambda \}_{\lambda \in \mathbb {N}}$ be a family of efficiently-computable functions $f :\mathcal {X}^\ell \rightarrow \mathcal {Y}$. Let $\varPi _{\textsf{FC}}= (\textsf{Setup}, \textsf{Commit}, \textsf{Eval}, \textsf{Verify})$ be a (dual) functional commitment scheme for $\mathcal {F}$. We now define the selective-input binding game between an adversary $\mathcal {A}$ and a challenger:

• 1. At the beginning of the game, the adversary chooses an input $\textbf{x}\in \mathcal {X}^\ell$ and sends $\textbf{x}$ to the challenger.

• 2. The challenger samples $\textsf{crs}\leftarrow \textsf{Setup}(1^\lambda )$ and gives $\textsf{crs}$ to $\mathcal {A}$.

• 3. The adversary outputs a commitment $\sigma$, values $y_0, y_1 \in \mathcal {Y}$, and openings $\pi _0, \pi _1$.

• 4. The output of the experiment is $b = 1$ if $y_0 \ne y_1$ and $\textsf{Verify}(\textsf{crs}, \sigma , \textbf{x}, y_0, \pi _0) = 1 = \textsf{Verify}(\textsf{crs}, \sigma , \textbf{x}, y_1, \pi _1)$. Otherwise, the output of the experiment is $b = 0$.

The functional commitment scheme satisfies computational selective-input binding if for all efficient adversaries $\mathcal {A}$, $\Pr [b = 1] = \textsf{negl}(\lambda )$ in the above security game.

Construction 3.10

(Dual Functional Commitment for Boolean Circuits). Let $\lambda$ be a security parameter and $n = n(\lambda )$, $m = m(\lambda )$, $q = q(\lambda )$, and $\chi = \chi (\lambda )$ be lattice parameters. Let $\ell = \ell (\lambda )$ be an input length parameter, and $B = B(\lambda )$ be a bound. Let $\mathcal {F}_\lambda$ be a collection of functions $f :\{0,1\}^\ell \rightarrow \{0,1\}$ that can be computed by a Boolean circuit of depth at most $d = d(\lambda )$. We construct a dual functional commitment $\varPi _{\textsf{FC}}= (\textsf{Setup}, \textsf{Commit}, \textsf{Eval}, \textsf{Verify})$ for $\mathcal {F}= \{ \mathcal {F}_\lambda \}_{\lambda \in \mathbb {N}}$ as follows:

• $\textsf{Setup}(1^\lambda )$: On input the security parameter $\lambda$, the setup algorithm samples $(\textbf{A}, \textbf{R}) \leftarrow \textsf{TrapGen}(1^n, q, m)$ and . Sample $\textbf{T}\leftarrow \textsf{SamplePre}([\textbf{I}_\ell \otimes \textbf{A}~|~ \textbf{W}], \textbf{I}_\ell \otimes \textbf{R}, \textbf{G}_{n \ell }, \chi ) \in \mathbb {Z}_{q}^{(\ell m + m) \times \ell m}$. Parse where $\textbf{T}_{\textsf{open}}\in \mathbb {Z}_{q}^{\ell m \times \ell m}$ and $\textbf{T}_{\textsf{com}}\in \mathbb {Z}_{q}^{m \times \ell m}$. Finally, it samples , computes $\textbf{B}= -\textbf{W}_0 \textbf{T}_{\textsf{com}}\in \mathbb {Z}_{q}^{n \times \ell m}$ and outputs the common reference string $\textsf{crs}= (\textbf{A}, \textbf{W}, \textbf{T}_{\textsf{com}}, \textbf{T}_{\textsf{open}}, \textbf{W}_0, \textbf{B})$.

• $\textsf{Commit}(\textsf{crs}, f)$: On input $\textsf{crs}= (\textbf{A}, \textbf{W}, \textbf{T}_{\textsf{com}}, \textbf{T}_{\textsf{open}}, \textbf{W}_0, \textbf{B})$ and a function $f :\{0,1\}^\ell \rightarrow \{0,1\}$, the commit algorithm computes $\textbf{B}_f \leftarrow \textsf{EvalF}(\textbf{B}, f)$ and outputs the commitment $\sigma = \textbf{B}_f \in \mathbb {Z}_{q}^{n \times m}$ along with the state $\textsf{st}= f$.

• $\textsf{Eval}(\textsf{crs}, \textsf{st}, \textbf{x})$: On input $\textsf{crs}= (\textbf{A}, \textbf{W}, \textbf{T}_{\textsf{com}}, \textbf{T}_{\textsf{open}}, \textbf{W}_0, \textbf{B})$, the state $\textsf{st}= f$, and the input $\textbf{x}\in \{0,1\}^\ell$, the evaluation algorithm computes $\textbf{H}_{\textbf{B}, f, \textbf{x}} \leftarrow \textsf{EvalFX}(\textbf{B}, f, \textbf{x}) \in \mathbb {Z}_{q}^{\ell m \times m}$ and outputs

  $$\begin{aligned} \pi = \textbf{V}= \begin{bmatrix} -(\textbf{x}^{\scriptscriptstyle \textsf{T}}\otimes \textbf{I}_m) \textbf{T}_{\textsf{open}}\\ -\textbf{T}_{\textsf{com}}\end{bmatrix} \cdot \textbf{H}_{\textbf{B}, f, \textbf{x}} \in \mathbb {Z}_{q}^{2m \times m}. \end{aligned}$$

  (3.7)

• $\textsf{Verify}(\textsf{crs}, \sigma , \textbf{x}, y, \pi )$: On input $\textsf{crs}= (\textbf{A}, \textbf{W}, \textbf{T}_{\textsf{com}}, \textbf{T}_{\textsf{open}}, \textbf{W}_0, \textbf{B})$, a commitment $\sigma = \textbf{B}_f \in \mathbb {Z}_{q}^{n \times m}$, an input $\textbf{x}\in \{0,1\}^\ell$, an output $y \in \{0,1\}$, and an opening $\pi = \textbf{V}\in \mathbb {Z}_{q}^{2 m \times m}$, the verification algorithm outputs 1 if

  $$\begin{aligned} \left\| \textbf{V} \right\| \le B \quad \text {and} \quad \textbf{B}_f - y \textbf{G}= [\textbf{A}~|~ \textbf{W}_0 + (\textbf{x}^{\scriptscriptstyle \textsf{T}}\otimes \textbf{I}_n) \textbf{W}] \textbf{V}. \end{aligned}$$

  (3.8)

Remark 3.11

(Supporting Preprocessing). Similar to Constructions 3.2 and 3.5, Construction 3.10 also supports fast verification in the preprocessing model. Note that in the dual setting, we preprocess with respect to an input $\textbf{x}$ rather than a function f.

• $\textsf{Preprocess}(\textsf{crs}, \textbf{x})$: On input $\textsf{crs}= (\textbf{A}, \textbf{W}, \textbf{T}_{\textsf{com}}, \textbf{T}_{\textsf{open}}, \textbf{W}_0, \textbf{B})$ and the input $\textbf{x}\in \{0,1\}^\ell$, the preprocess algorithm outputs $\textsf{vk}_{\textbf{x}} = \textbf{F}_\textbf{x}= [\textbf{A}~|~ \textbf{W}_0 + (\textbf{x}^{\scriptscriptstyle \textsf{T}}\otimes \textbf{I}_n) \textbf{W}] \in \mathbb {Z}_{q}^{n \times 2m}$.

• $\textsf{OnlineVerify}(\textsf{vk}, \sigma , y, \pi )$: On input the verification key $\textsf{vk}= \textbf{F}_\textbf{x}\in \mathbb {Z}_{q}^{n \times 2m}$, the commitment $\sigma = \textbf{B}_f \in \mathbb {Z}_{q}^{n \times 2m}$, a value $y \in \{0,1\}$, and an opening $\pi = \textbf{V}\in \mathbb {Z}_{q}^{2 m \times m}$, the online verification algorithm outputs 1 if

  $$\begin{aligned} \left\| \textbf{V} \right\| \le B \quad \text {and} \quad \textbf{B}_f - y \textbf{G}= \textbf{F}_{\textbf{x}} \textbf{V}. \end{aligned}$$

Correctness and Security Analysis. We provide the correctness, security analysis, and parameter instantiation for Construction 3.10 in the full version of this paper. We summarize the instantiation in the following corollary:

Corollary 3.12

(Dual Functional Commitment for Bounded-Depth Boolean Circuits). Let $\lambda$ be a security parameter and let $\mathcal {F}= \{ \mathcal {F}_\lambda \}_{\lambda \in \mathbb {N}}$ be a family of functions $f :\{0,1\}^\ell \rightarrow \{0,1\}$ on inputs of length $\ell = \ell (\lambda )$ and which can be computed by Boolean circuits of depth at most $d = d(\lambda )$. Under the $\ell$-succinct SIS assumption with a sub-exponential norm bound $\beta = 2^{\tilde{O}(n^\varepsilon )}$ for some constant $\varepsilon > 0$ and lattice dimension $n = n(\lambda )$, there exists a dual functional commitment for $\mathcal {F}$. The functional commitment satisfies computational selective-input binding and supports preprocessing for fast verification (Definition 2.2). The size of the commitment and the opening have size $\textsf{poly}(\lambda , d^{1 / \varepsilon }, \log \ell )$ and the CRS has size $\ell ^2 \cdot \textsf{poly}(\lambda , d^{1 / \varepsilon }, \log \ell )$.

4 Cryptanalysis of Extractable Commitments

In this section, we describe some of the challenges in constructing extractable lattice-based functional commitments. In the full version of this paper, we show that Construction 3.2 is not an extractable functional commitment for quadratic functions. In this section, we show that assuming inhomogeneous SIS, the [ACL+22] approach does not yield an extractable functional commitment for linear functions. The attacks we develop work by using the components in the CRS to derive a basis for a lattice defined by the scheme’s verification relation. We then use the basis to obliviously sample a solution that satisfies the schemes’ verification relation without knowledge of a corresponding input. In one case, this can be used to sample a valid opening to an unsatisfiable set of quadratic constraints, while in the other case (Sect. 4.1), we can embed a SIS instance that the extractor must solve in order to output a valid input. We start with the definition of a extractable functional commitment.

Definition 4.1

(Extractability). Let $\lambda$ be a security parameter. We say that a functional commitment $\varPi _{\textsf{FC}}= (\textsf{Setup}, \textsf{Commit}, \textsf{Eval}, \textsf{Verify})$ for a function family $\mathcal {F}= \{ \mathcal {F}_{\lambda } \}_{\lambda \in \mathbb {N}}$ is extractable if for all efficient adversaries $\mathcal {A}$, there exists an efficient extractor $\mathcal {E}$ such that

$$ \Pr \left[ \begin{array}{c} \textsf{Verify}(\textsf{crs}, \sigma , f, y, \pi ) = 1 \text { and } \\ f(\textbf{x}) \ne y \end{array} : \begin{array}{c} \textsf{crs}\leftarrow \textsf{Setup}(1^\lambda ) \\ \big ( ( \sigma , f, y, \pi ), \textbf{x}\big ) \leftarrow (\mathcal {A}\Vert \mathcal {E})(1^\lambda , \textsf{crs}) \end{array} \right] = \textsf{negl}(\lambda ). $$

Here, we write $(\mathcal {A}\Vert \mathcal {E})(\cdot )$ to denote invoking algorithm $\mathcal {A}$ and the extractor $\mathcal {E}$ on the same input and randomness. The output of $\mathcal {A}$ is $(\sigma , f, y, \pi )$ and the output of $\mathcal {E}$ is $\textbf{x}$.

4.1 Analyzing the [ACL+22] Knowledge Assumption

In this section, we analyze one version of the k-$\textsf{ISIS}$ and knowledge k-$\textsf{ISIS}$ family of assumptions from [ACL+22]. While the original assumptions from [ACL+22] were defined over polynomial rings (and module/ideal lattices), we consider the analogous assumptions over the integers. Since ring multiplication is commutative whereas matrix multiplication is not, there are multiple (and similar) ways to translate the [ACL+22] family of assumptions to the integers. We describe one adaptation here, where we “sparsify by left multiplication.” We refer to this adaptation as the $\textsf{MatrixACLMT}$ construction.

Assumption 4.2

( $\textsf{MatrixACLMT}$ k-$\textsf{ISIS}$ Assumption for Linear Functions). Let $\lambda$ be a security parameter and let $(n, m, q, \chi , \ell , \beta )$ be lattice parameters. The $\textsf{MatrixACLMT}$ k-$\textsf{SIS}$ assumption says that for every efficient adversary $\mathcal {A}$, there exists a negligible function $\textsf{negl}(\cdot )$ such that

Assumption 4.3

( $\textsf{MatrixACLMT}$ Knowledge Assumption). Let $\lambda$ be a security parameter and let $(n, m, q, \chi , t, \ell , \alpha , \beta )$ be lattice parameters where $q^{n - t} = \textsf{negl}(\lambda )$ and $m \ge O(t \log q)$. The $\textsf{MatrixACLMT}$ knowledge assumption says that for every efficient adversary $\mathcal {A}$, there exists an efficient extractor $\mathcal {E}$ such that $\Pr [b = 1] = \textsf{negl}(\lambda )$, where $b \in \{0,1\}$ is the output of the following experiment:

where $\left( (\textbf{c}, \textbf{v}), \textbf{x}\right) \leftarrow (\mathcal {A}\Vert \mathcal {E})(1^\lambda , \textbf{A}, \textbf{D}, \{ (\textbf{t}_i, \textbf{z}_i) \}_{i \in [\ell ]})$ denotes that $\mathcal {A}$ and $\mathcal {E}$ are invoked on the same input and randomness, and $(\textbf{c}, \textbf{v})$ is the output of $\mathcal {A}$ while $\textbf{x}$ is the output of $\mathcal {E}$.

The $\textsf{MatrixACLMT}$ knowledge assumption essentially says that any efficient adversarial strategy that produces a short $\textbf{v}\in \mathbb {Z}_{q}^m$ where $\textbf{A}\textbf{v}\in \mathbb {Z}_{q}^t$ lies in the image of $\textbf{D}$ (i.e., $\textbf{A}\textbf{v}= \textbf{D}\textbf{c}$) can be explained as taking a short linear combination of the given preimages $\textbf{z}_1, \ldots , \textbf{z}_\ell$. Indeed, if $\textbf{c}= \sum _{i \in [\ell ]} x_i \textbf{t}_i$, then $\textbf{A}\left( \sum _{i \in [\ell ]} x_i \textbf{z}_i \right) = \textbf{D}\left( \sum _{i \in [\ell ]} x_t \textbf{t}_i \right) = \textbf{D}\textbf{c}$. The requirement $q^{n - t} = \textsf{negl}(\lambda )$ is necessary to prevent the basic oblivious sampling attack where the adversary samples a random short vector $\textbf{v}\in \mathbb {Z}_{q}^m$ and solves for a $\textbf{c}\in \mathbb {Z}_{q}^n$ satisfying $\textbf{A}\textbf{v}= \textbf{D}\textbf{c}$. Since the image of $\textbf{A}$ has $q^t$ elements and the image of $\textbf{D}$ has $q^n$ elements, all but a negligible fraction of the elements in the image of $\textbf{A}$ are contained in the image of $\textbf{D}$.

A Heuristic Oblivious Sampling Algorithm for Assumption 4.3. We start by describing an adversary for Assumption 4.3 that obliviously samples a short vector $\textbf{v}\in \mathbb {Z}_{q}^m$ such that $\textbf{A}\textbf{v}$ is in the image of $\textbf{D}$. While this by itself does not necessarily falsify Assumption 4.3, we will subsequently show that Assumptions 4.2 and 4.3 cannot simultaneously hold for a broad range of parameter settings (i.e., at least one of Assumption 4.2 or Assumption 4.3 is false).

Algorithm 4.4

(Candidate Oblivious Sampler for $\textsf{MatrixACLMT}$ ). Suppose $\ell \gg m + n$ in Assumption 4.3. Our heuristic oblivious sampling algorithm $\mathcal {A}$ for Assumption 4.3 works as follows:

• 1. Let , , and $\textbf{z}_i \leftarrow \textbf{A}_\chi ^{-1}(\textbf{D}\textbf{t}_i)$ be the challenge from Assumption 4.3. By construction,

  $$ \left[ \textbf{A}~|~ \textbf{D}\textbf{G}\right] \cdot \underbrace{\left[ \begin{array}{ccc} \textbf{z}_1 &{} \cdots &{} \textbf{z}_{\ell } \\ -\textbf{G}^{-1}(\textbf{t}_1) &{} \cdots &{} -\textbf{G}^{-1}(\textbf{t}_{\ell }) \end{array} \right] }_{\bar{\textbf{T}}} = \boldsymbol{0}\bmod q. $$

  Since $\textbf{t}_i$ and $\textbf{z}_i$ are sampled independently and assuming that $\ell \gg m + n$ is sufficiently large (e.g., setting $\ell = 2 (m + n)$ should suffice), we can heuristically assume that $\bar{\textbf{T}} \in \mathbb {Z}^{(m + n) \times \ell }$ is full rank over the reals.⁹ Thus, we can use $\bar{\textbf{T}}$ to derive an Ajtai-trapdoor $\textbf{T}$ for the matrix $\textbf{B}= [\textbf{A}~|~ \textbf{D}\textbf{G}]$ (e.g., by taking a subset of $m + n$ columns of $\bar{\textbf{T}}$ that are linearly independent over the reals).

• 2. Using $\textbf{T}$, the algorithm samples a short where . The commitment is then $\textbf{G}\textbf{c}$ and the opening is $\textbf{v}$. For instance, the algorithm might implement Babai’s rounding algorithm. Specifically, it starts with an arbitrary (non-zero) solution $\textbf{y}\in \mathbb {Z}^{m + n}$ where $\textbf{B}\textbf{y}= \boldsymbol{0}\bmod q$, solves for the unique $\textbf{z}\in \mathbb {Q}^{m + n}$ where $\textbf{T}\textbf{z}= \textbf{y}\in \mathbb {Q}^{m + n}$ and then outputs $\textbf{x}= \textbf{y}- \textbf{T}\cdot \left\lfloor \textbf{z} \right\rceil$. By construction $\textbf{B}\textbf{x}= \boldsymbol{0}\bmod q$ and moreover $\left\| \textbf{x} \right\| \le \left\| \textbf{T}(\textbf{z}- \left\lfloor \textbf{z} \right\rceil ) \right\|$, which is small.

The basic question is whether the solution $\textbf{x}$ derived by rounding off a long solution as in Algorithm 4.4 (or sampled through some alternative trapdoor sampling algorithm) can always be explained by a short linear combination of the basis vectors $\textbf{T}$. In the following, we show that assuming (non-uniform) hardness of inhomogeneous SIS and the matrix-ACLMT assumption for linear functions (Assumption 4.2), then no such extractor exists. One implication of this is that this particular adaptation of [ACL+22] to the integers is not an extractable functional commitment for linear functions.

Attacking the Matrix-ACLMT Commitment for Linear Functions. We now show how we can apply the approach in Algorithm 4.4 to break extractability for the linear functional commitment from [ACL+22] (when instantiated over the integers). We start by recalling their construction (over the integers):

Construction 4.5

(Functional Commitment for Linear Functions). Let $\lambda$ be a security parameter and $n, m, m', q, t, B, \chi$ be lattice parameters. Let $\ell = \ell (\lambda )$ be the input length. For a matrix $\textbf{M}\in \mathbb {Z}_{q}^{k \times \ell }$, let $f_{\textbf{M}} :\mathbb {Z}_{q}^{k \times \ell } \rightarrow \mathbb {Z}_{q}^k$ be the linear function $\textbf{x}\mapsto \textbf{M}\textbf{x}$. Let $\mathcal {F}_\lambda = \{ f_{\textbf{M}} \mid \textbf{M}\in \{0,1\}^{k \times \ell } \}$. We construct a functional commitment $\varPi _{\textsf{FC}}= (\textsf{Setup}, \textsf{Commit}, \textsf{Eval}, \textsf{Verify})$ for $\mathcal {F}= \{ \mathcal {F}_\lambda \}_{\lambda \in \mathbb {N}}$ as follows:

• $\textsf{Setup}(1^\lambda , 1^\ell )$: Sample matrices $(\textbf{A}, \textbf{R}_{\textbf{A}}) \leftarrow \textsf{TrapGen}(1^\lambda , n, m)$, , $\textbf{u}\leftarrow \mathbb {Z}_{q}^n$, and let $\textbf{t}_i \leftarrow \textbf{W}_i^{-1}\textbf{u}\in \mathbb {Z}_{q}^n$ for each $i \in [\ell ]$. For each $i \ne j$, sample $\textbf{z}_{i, j} \leftarrow \textsf{SamplePre}(\textbf{A}, \textbf{R}_{\textbf{A}}, \textbf{W}_i \textbf{t}_j, \chi )$. Let $\widehat{\textbf{W}}\in \mathbb {Z}_{q}^{\ell n \times n}$ to be the vertical stacking of the matrices $\textbf{W}_1, \ldots , \textbf{W}_\ell$:

  $$ \widehat{\textbf{W}}= \begin{bmatrix} \textbf{W}_1 \\ \vdots \\ \textbf{W}_\ell \end{bmatrix} \in \mathbb {Z}_{q}^{\ell n \times n}. $$

  Next, sample $(\textbf{B}, \textbf{R}_{\textbf{B}}) \leftarrow \textsf{TrapGen}(1^\lambda , t, m')$ and a matrix . Sample $\textbf{z}_i' \leftarrow \textsf{SamplePre}(\textbf{B}, \textbf{R}_{\textbf{B}}, \textbf{D}\textbf{t}_i, \chi )$ for each $i \in [\ell ]$. Output the common reference string $\textsf{crs}= \big ( \textbf{A}, \textbf{B}, \textbf{D}, \textbf{u}, \{ \textbf{W}_i \}_{i \in [\ell ]}, \{ \textbf{z}_{i, j} \}_{i \ne j}, \{ \textbf{z}_i' \}_{i \in [\ell ]} \big )$.

• $\textsf{Commit}(\textsf{crs}, \textbf{x})$: On input $\textsf{crs}= \big ( \textbf{A}, \textbf{B}, \textbf{D}, \textbf{u}, \{ \textbf{W}_i \}_{i \in [\ell ]}, \{ \textbf{z}_{i, j} \}_{i \ne j}, \{ \textbf{z}_i' \}_{i \in [\ell ]} \big )$ and an input vector $\textbf{x}\in \mathbb {Z}_{q}^\ell$, the commit algorithm outputs the commitment $\textbf{c}= \sum _{i \in [\ell ]} x_i \textbf{t}_i \in \mathbb {Z}_{q}^n$ and the state $\textsf{st}= \textbf{x}$.

• $\textsf{Eval}(\textsf{crs}, \textsf{st}, f_{\textbf{M}})$: On input $\textsf{crs}= \big ( \textbf{A}, \textbf{B}, \textbf{D}, \textbf{u}, \{ \textbf{W}_i \}_{i \in [\ell ]}, \{ \textbf{z}_{i, j} \}_{i \ne j}, \{ \textbf{z}_i' \}_{i \in [\ell ]} \big )$, a commitment state $\textsf{st}= \textbf{x}$, and a function $f_{\textbf{M}}$ for some matrix $\textbf{M}\in \mathbb {Z}_{q}^{k \times \ell }$, the evaluation algorithm computes $\widehat{\textbf{v}}_i \leftarrow \sum _{j \ne i} x_j \textbf{z}_{i, j}$ for each $i \in [\ell ]$ and defines $\widehat{\textbf{v}}\in \mathbb {Z}_{q}^{\ell m}$ and $\hat{\textbf{z}}\in \mathbb {Z}_{q}^{\ell m'}$ as follows:

  $$ \widehat{\textbf{v}}= \begin{bmatrix} \widehat{\textbf{v}}_1 \\ \vdots \\ \widehat{\textbf{v}}_\ell \end{bmatrix} \in \mathbb {Z}_{q}^{\ell m} \quad \text {and} \quad \hat{\textbf{z}}= \begin{bmatrix} \textbf{z}_1' \\ \vdots \\ \textbf{z}_\ell ' \end{bmatrix}. $$

  It outputs the opening

  $$ \textbf{v}= \begin{bmatrix} (\textbf{M}\otimes \textbf{I}_m) \widehat{\textbf{v}}\\ (\textbf{x}^{\scriptscriptstyle \textsf{T}}\otimes \textbf{I}_{m'}) \textbf{z}_i' \end{bmatrix} \in \mathbb {Z}_{q}^{km + m'}. $$

• $\textsf{Verify}(\textsf{crs}, \sigma , f_\textbf{M}, y, \pi )$: On input $\textsf{crs}= \big ( \textbf{A}, \textbf{B}, \textbf{D}, \textbf{u}, \{ \textbf{W}_i \}_{i \in [\ell ]}, \{ \textbf{z}_{i, j} \}_{i \ne j}, \{ \textbf{z}_i' \}_{i \in [\ell ]} \big )$, a commitment $\sigma = \textbf{c}\in \mathbb {Z}_{q}^{n}$, a function $f_{\textbf{M}} :\mathbb {Z}_{q}^{k \times \ell } \rightarrow \mathbb {Z}_{q}^k$ where $\textbf{M}\in \mathbb {Z}_{q}^{k \times \ell }$, a value $\textbf{y}\in \mathbb {Z}_{q}^k$, and an opening $\pi = \textbf{v}\in \mathbb {Z}_{q}^{(km + m') \times m}$, the verification algorithm outputs 1 if

  $$\begin{aligned} \left\| \textbf{v} \right\| \le B \quad \text {and} \quad \begin{bmatrix} \textbf{I}_k \otimes \textbf{A}&{} \boldsymbol{0}\\ \boldsymbol{0}&{} \textbf{B}\end{bmatrix} \cdot \textbf{v}= \begin{bmatrix} (\textbf{M}\otimes \textbf{I}_n) \widehat{\textbf{W}}\\ \textbf{D}\end{bmatrix} \cdot \textbf{c}- \begin{bmatrix} \textbf{y}\otimes \textbf{u}\\ \boldsymbol{0}\end{bmatrix}. \end{aligned}$$

  (4.1)

Correctness. Correctness follows by the same argument as in [ACL+22], adapted to operate over the integers. We give a sketch here and refer to [ACL+22] for more details. Let $\textsf{crs}= \big ( \textbf{A}, \textbf{B}, \textbf{D}, \textbf{u}, \{ \textbf{W}_i \}_{i \in [\ell ]}, \{ \textbf{z}_{i, j} \}_{i \ne j}, \{ \textbf{z}_i' \}_{i \in [\ell ]} \big )$ be a CRS sampled via the $\textsf{Setup}$ algorithm. Suppose $\textbf{c}= \sum _{i \in [\ell ]} x_i \textbf{t}_i$ is a commitment to a short input $\textbf{x}\in \mathbb {Z}_{q}^\ell$. Suppose $\textbf{v}$ is an opening to a function $f_{\textbf{M}}$ where $\textbf{M}\in \mathbb {Z}_{q}^{k \times \ell }$ is a matrix with small entries. By construction, if the entries of $\textbf{M}$ and $\textbf{x}$ are short, then so is $\textbf{v}$. Consider now the main verification relation. First, for each $i \in [\ell ]$,

$$ \textbf{W}_i \textbf{c}= \sum _{j \in [\ell ]} x_j \textbf{W}_i \textbf{t}_j = x_i \textbf{u}+ \sum _{j \ne i} x_j \textbf{A}\textbf{z}_{i, j} = x_i \textbf{u}+ \textbf{A}\widehat{\textbf{v}}_i. $$

Equivalently, this means $\widehat{\textbf{W}}\textbf{c}= \textbf{x}\otimes \textbf{u}+ (\textbf{I}_\ell \otimes \textbf{A}) \widehat{\textbf{v}}$. Consider now the main verification relation:

$$\begin{aligned} (\textbf{M}\otimes \textbf{I}_n) \widehat{\textbf{W}}\textbf{c}&= (\textbf{M}\otimes \textbf{I}_n) (\textbf{x}\otimes \textbf{u}) + (\textbf{M}\otimes \textbf{I}_n) (\textbf{I}_\ell \otimes \textbf{A}) \widehat{\textbf{v}}\\ &= (\textbf{M}\textbf{x}\otimes \textbf{u}) + (\textbf{I}_k \otimes \textbf{A}) (\textbf{M}\otimes \textbf{I}_m) \widehat{\textbf{v}}\\ \textbf{D}\textbf{c}&= \sum _{i \in [\ell ]} x_i \textbf{D}\textbf{t}_i = \textbf{B}\cdot \left( \sum _{i \in [\ell ]} x_i \textbf{z}_i' \right) = \textbf{B}\cdot (\textbf{x}^{\scriptscriptstyle \textsf{T}}\otimes \textbf{I}_{m'}) \hat{\textbf{z}}. \end{aligned}$$

For a sufficiently-large bound B, the verification relations hold and correctness follows.

Extractability. By an analogous argument as in [ACL+22], we can show that under Assumptions 4.2 and 4.3 (with suitable parameter instantiations), if an efficient adversary can produce a commitment $\sigma = \textbf{c}$ along with a valid opening $\pi = \textbf{v}$ to a short value $\textbf{y}\in \mathbb {Z}_{q}^t$ with respect to a linear function $f_\textbf{M}$ with short $\textbf{M}\in \mathbb {Z}_{q}^{k \times \ell }$, then there exists an efficient extractor that outputs a short $\textbf{x}\in \mathbb {Z}_{q}^\ell$ where $\textbf{M}\textbf{x}= \textbf{y}$. We give a sketch of the general approach here and refer to [ACL+22] for a formal argument:

• Suppose there exists an efficient adversary $\mathcal {A}$ is able to come up with a commitment $\textbf{c}\in \mathbb {Z}_{q}^n$ and a short opening that satisfies Eq. (4.1). This means that $\textbf{B}\textbf{v}_2 = \textbf{D}\textbf{c}$. By Assumption 4.3, there exists an efficient extractor $\mathcal {E}$ that outputs a short $\textbf{x}\in \mathbb {Z}_{q}^\ell$ such that $\textbf{c}= \sum _{i \in [\ell ]} x_i \textbf{t}_i$.

• If the extracted $\textbf{x}$ satisfies $\textbf{M}\textbf{x}= \textbf{y}$, then the extractor is successful. Consider the case where $\textbf{M}\textbf{x}\ne \textbf{y}$. If this happens with non-negligible probability, we can construct an adversary $\mathcal {B}$ that uses the extractor $\mathcal {E}$ to break Assumption 4.2:

  • 1. Algorithm $\mathcal {B}$ receives $\left( \textbf{A}, \textbf{u}, \{ \textbf{W}_i \}_{i \in [\ell ]}, \{ \textbf{z}_{i, j} \}_{i \ne j} \right)$ from the challenger for Assumption 4.2.

  • 2. It samples $(\textbf{B}, \textbf{R}_{\textbf{B}}) \leftarrow \textsf{TrapGen}(1^\lambda , t, m')$, , and $\textbf{z}_i' \leftarrow \textsf{SamplePre}(\textbf{B}, \textbf{R}_{\textbf{B}}, \textbf{D}\textbf{t}_i, \chi )$ for each $i \in [\ell ]$ as in the real scheme. The reduction algorithm constructs the common reference string $\textsf{crs}= \big ( \textbf{A}, \textbf{B}, \textbf{D}, \textbf{u}, \{ \textbf{W}_i \}_{i \in [\ell ]}, \{ \textbf{z}_{i, j} \}_{i \ne j}, \{ \textbf{z}_i' \}_{i \in [\ell ]} \big )$ and gives $\textsf{crs}$ to $\mathcal {A}$.

  • 3. After $\mathcal {A}$ outputs a commitment $\textbf{c}$ and opening , algorithm $\mathcal {B}$ runs the extractor $\mathcal {E}$ on the same input as $\mathcal {A}$ to obtain a short input $\textbf{x}\in \mathbb {Z}_{q}^\ell$. Suppose $\textbf{M}\textbf{x}= \textbf{y}' \ne \textbf{y}$. Then algorithm $\mathcal {A}$ computes an opening by computing $\textsf{Eval}(\textsf{crs}, \textbf{x}, f_{\textbf{M}})$. By correctness, $\textbf{v}'$ is short and moreover satisfies the following verification relation from Eq. (4.1):

    $$\begin{aligned} (\textbf{I}_k \otimes \textbf{A}) \textbf{v}_1' = (\textbf{M}\otimes \textbf{I}_n) \widehat{\textbf{W}}\textbf{c}- \textbf{M}\textbf{x}\otimes \textbf{u}\end{aligned}$$

    (4.2)

    Since $\textbf{v}$ is also a valid opening, we have that

    $$\begin{aligned} (\textbf{I}_k \otimes \textbf{A}) (\textbf{v}_1 - \textbf{v}_1') = (\textbf{y}' - \textbf{y}) \otimes \textbf{u}. \end{aligned}$$

    Since $\textbf{y}- \textbf{y}' \ne \boldsymbol{0}$, there is at least one non-zero “block” where $\textbf{A}(\textbf{v}_{1, i} - \textbf{v}_{1, i}') = (y_i' - y_i) \textbf{u}$ and $y_i' \ne y_i$. Since $\textbf{y}, \textbf{y}'$ are both short, this yields a valid solution to Assumption 4.2.

An Attack on Construction 4.5. To conclude, we describe a (heuristic) attack that breaks extractability of Construction 4.5. Our approach takes the following template:

• 1. Given the CRS for the functional commitment scheme, we construct an efficient adversary $\mathcal {A}$ that can obliviously sample an opening to an arbitrary vector $\textbf{y}\in \mathbb {Z}_{q}^k$ with respect to a function $f_{\textbf{M}}$ where $\textbf{M}= [\textbf{M}_{\textsc {l}}~|~ \boldsymbol{0}^{k \times \ell _1}]$ and $\textbf{M}_{\textsc {l}}\in \mathbb {Z}_{q}^{k \times \ell _2}$ is short.

• 2. Extractability of the functional commitment now says that there exists an efficient extractor that outputs a short $\textbf{x}\in \mathbb {Z}_{q}^{\ell _1 + \ell _2}$ such that $\textbf{M}\textbf{x}= \textbf{y}$.

• 3. Since the oblivious sampler is agnostic to the choice of $\textbf{M}_{\textsc {l}}$ (as long as it is short), we can embed an (inhomogeneous) SIS instance into $\textbf{M}_{\textsc {l}}$. In this case, an extractor for algorithm $\mathcal {A}$ is able to solve inhomogeneous SIS with respect to $\textbf{M}$, and by extension, $\textbf{M}_{\textsc {l}}$.

We defer the details to the the full version of this paper. Taken together, our analysis shows that under the inhomogeneous SIS assumption, either Assumption 4.2 or Assumption 4.3 must be false, and correspondingly, the functional commitment scheme in Construction 4.5 is not extractable.