1 Introduction↩︎

Solving systems of linear equations is one of the most fundamental problems in mathematics and computer science. Over a field, we can efficiently solve this via Gaussian elimination in polynomial time. The problem, however, becomes considerably harder when the equations are noisy: given \(m\) equations of the form \(\langle\boldsymbol{a}_i, \boldsymbol{s}\rangle +e_i=b_i\) where \(e_i\) is an unknown error term, recovering the secret \(\boldsymbol{s}\) is no longer straightforward. The difficulty of solving these noisy linear equations depends on the structure of the error distribution, and understanding precisely when efficient recovery is possible remains a central question in both learning theory and cryptography.

Two of the most well-studied average-case instantiations of noisy linear equations are the Learning With Errors (LWE) problem, introduced by Regev [1], and its close cousin, the Learning Parity with Noise (LPN) problem [2]; both serve as central hardness assumptions in modern cryptography. In LWE, one samples \((\boldsymbol{a}, b) \in \mathbb{Z}_q^n \times \mathbb{Z}_q\) by choosing \(\boldsymbol{a} \leftarrow \mathbb{Z}_q^n\) uniformly, an error \(e \leftarrow \Psi\) (typically a discrete Gaussian of width \(r < q\)), and setting \(b = \langle \boldsymbol{a}, \boldsymbol{s} \rangle + e \bmod q\). The decision problem is to distinguish such samples from uniform over \(\mathbb{Z}_q^n \times \mathbb{Z}_q\). The LPN problem is most commonly studied over \(\mathbb{Z}_2\) with Bernoulli noise, or more generally over modulus \(q\) with sparse (low Hamming-weight) noise, and has a closely related structure. Most lattice-based cryptosystems rely on LWE’s conjectured intractability against classical and quantum algorithms [1], [3]–[6], while LPN’s hardness rests on decades of cryptanalysis [7]–[13], offering competitive efficiency despite fewer constructions [14], [15].

Variants of these problems are considered to balance security with efficiency of cryptographic primitives. Different choices of modulus, noise distribution, or structural constraints (such as sparsity) can lead to primitives with faster key generation, smaller ciphertexts, or reduced computational overhead, while still relying on problems which are believed to have same hardness [16], [17]. In this work, we focus on LWE and LPN with sparsity constraints, where the coefficient vectors \(\boldsymbol{a}\in\mathbb{Z}_q^n\) are required to have only \(k\) non-zero entries for a parameter \(k<n\). The motivation for this sparsity is that the samples can be computed and stored with a roughly \(O(n/k)\) factor improvement in efficiency. Hardness of sparse LPN over \(\mathbb{Z}_2\) and variants have been studied for as long as forty years in average-case complexity and have intimate connections to constraint satisfaction problems [18]–[22]. Sparse variants of LWE/LPN over large moduli \(q\) (where \(q\) is at least polynomial in the security parameter) are useful for designing efficient advanced cryptographic primitives, including FHE but remain underexplored. We summarize the current known attacks for sparse variants below.

The task in analyzing the hardness of these sparse variants is to determine the computational complexity as a function of \(m\), i.e. the number of samples \((\boldsymbol{a},b)\). For \(m\leq n\), the random and the planted noisy instances are statistically indistinguishable. Raghavendra, Rao and Schramm [23] showed that sparse LPN over \(\mathbb{Z}_2\) can be solved in \(n^{O(l)}\) time when \(m\) is a quantity of the form \(l\left(\frac{n}{l}\right)^{k/2}\log^{c(k)}(n)\) using a degree \(l\) “Sum of squares” method for \(l\geq k/2\). An improved (and the best known) bound of the form \(l\left(\frac{n}{l}\right)^{k/2}\log{n}\) for \(m\) with the same time complexity can be obtained using the “Kikuchi method” by Wein, Alaoui, and Moore [24] (independently by Hastings [25]).¹ Schmidhuber, O’Donnell, Kothari, and Babbush [27] gave a quantum algorithm that achieves a quartic speedup in time (i.e. \(n^{l/4}\cdotp\text{poly}(n)\)) over the Kikuchi method for certain choices of the sample complexity \(m\), while using exponentially less space.

Despite the presence of numerous other variants of LWE, sparse LWE was not studied until a recent work by Jain, Lin, and Saha [28]. Assuming hardness of sparse LWE, they construct secret key Linearly Homomorphic Encryption (LHE) schemes with slightly super-constant/constant overheads, and secret key homomorphic encryption for arbitrary constant-degree polynomials with slightly super-constant/constant overheads. They also perform some cryptanalysis on sparse LWE by suggesting two attacks for sparse LWE, namely the sparse vector in kernel attack and the dense minor attack. On analyzing the feasibility of these attacks for \(k\geq\Omega(\log n)\) and \(m = \text{poly}(n)\), it turns out that these attacks will take exponential time in \(n\) with high probability. Hence, the authors conjecture that sparse LWE with sparsity \(k\geq\Omega(\log n)\) and polynomially many samples \(m = \text{poly}(n)\) is as hard as the standard LWE with dimension \(n'=\Theta(n)\) and polynomially many samples.

Subsequently, Bangachev et al. [29] give improved reductions from dense LWE to sparse LWE, and similarly from dense LPN to sparse LPN. Their reductions aim to establish \(n^{\Omega(k)}\)-hardness of sparse LWE under the assumption that dense LWE requires exponential time, but still incur an additional \(1 / \log k\) multiplicative factor in the exponent.

Our Contributions. In this work we provide algorithms for solving the analogue of sparse LPN over general rings \(R\) with \(\left\lvert R \right\rvert>2\), which we call \({k}-\text{LIN}(R)\). Here the task is to determine whether a system of \(k\)-sparse linear equations over a finite ring \(R\) (having randomly chosen left-hand sides) has random right-hand sides or having a planted secret assignment with a noise distribution \(\Psi\). We obtain analogous results of tradeoff between the sample complexity and runtime as those for sparse LPN.

We also have a simpler algorithm for the distinguishing problem with a better time complexity, and also a better sample complexity than above when \(\left\lvert R \right\rvert=\omega(n/l)\).

As can be seen, the parameter \(l\) in the above theorem trades sample complexity for time. In particular, we obtain tradeoffs between the sample complexity \(m\) and time complexity for sparse LWE and sparse LPN over higher modulus \(q\). As an interesting case, if either \(k=O(\log n/\log\log \left\lvert R \right\rvert)\) or we are allowed \(m = n^{\Omega(\log\log \left\lvert R \right\rvert)}\) samples, we can choose \(l\) appropriately so that the time complexity is \(\exp({\delta n})\) for arbitrarily small \(\delta > 0\). Assuming standard LWE does not have an arbitrarily small exponential time, our result also establishes the tightness of the conjecture on the hardness of sparse LWE by [28].

Moreover, the algorithms in the above theorems are applicable for a wide class of noise distributions \(\Psi\). For the ring \(\mathbb{Z}_q\), apart from the discrete Gaussian noise in LWE or the ‘low Hamming weight’ noise in LPN, the distinguishing problem is solvable for a large class of other plausible noise distributions. For example, one might consider a distribution where zero error is allowed only with probability \(1/q\), otherwise the error is rejection sampled again according to the discrete Gaussian. Another example can be an addition of noises, one from the discrete Gaussian and another from the LPN distribution noise, which was recently proposed in a bid for new hardness on noisy linear equations [30]. In the sparse regime, our algorithms attack the problem for these noise distributions as well.

For Theorem 1 we extend the Kikuchi method used by [24] for \({k}-\text{LIN}(\mathbb{Z}_2)\). This involves formulating a large graph corresponding to the \({k}-\text{LIN}(R)\) instance, called the Kikuchi Graph. We determine whether the instance is random or planted based on the spectral norm of the adjacency matrix of this graph. For Theorem 2, we collect all subsamples of the original instance that have non-zero coefficients only on the first \(l\) variables, and then distinguish by naively checking all \(\left\lvert R \right\rvert^l\) assignments on this sub-instance.

In [28], Jain, Lin and Saha had defined sparse LWE in a manner which allows equations to be at most \(k\)-sparse instead of exactly \(k\)-sparse ². We analyse this variant for general rings as well, which we call \({k}-\text{ALIN}(R)\). Intuitively, the distinguishing problem should be easier in this case, as left-hand sides here can have very few or even no non-zero entries. For large \(\left\lvert R \right\rvert\), the above approach itself can work, however when \(\left\lvert R \right\rvert\) is small, we can achieve a much better complexity.

[28] had also given a reduction from standard LWE on \(k\) dimensions to (at most) \(k\)-sparse LWE on \(n\geq k\) dimensions. It is believed that distinguishing standard LWE takes \(2^{\Omega(k)}\) time given arbitrary many samples. Our result above can be seen as a step towards matching this hardness result for (at most) \(k\)-sparse LWE.

Independent Work. Independent of our work, Kocurek and Manohar [31] have studied the problem of refuting random and semirandom instances of \({k}-\text{LIN}(R)\)³. For this task, they define Kikuchi graphs for finite fields and abelian groups that are similar to our construction. Their sample-time tradeoffs are also similar to ours. However, our objective is different from the refutation task; ours is the task of distinguishing a random vs a planted instance. It turns out that the statistic they use for the refutation task, the value of an instance (maximum fraction of satisfiable constraints), cannot be extended to the distinguishing task when the noise distribution for the planted case has a high probability of introducing an error, i.e., has a low probability of making zero error. The statistic we use, which we call the advantage (Definition 6), is able to handle error distributions which satisfy a much milder condition than the one [31] need, and is thereby more widely applicable.

Moreover, they construct separate Kikuchi constructions depending on the sparsity \(k\) being even or odd, and also depending on the ring being a field or non-field, with significantly more involved construction in the odd sparsity case.

Our Kikuchi construction is able to mitigate both these issues; it is more amenable to the distinguishing task, and is a unified and simplified construction for all rings \(R\) and both sparsity parities when \(\left\lvert R \right\rvert>2\). Further, we are able to construct a simpler distinguisher which has a significantly lower runtime than that of their simple refutation algorithm when the size of the ring \(R\) is large.

We elaborate on these aspects in Subsection 8.1.

Organization. Section 2 gives a high level overview of our spectral Kikuchi method. Section 3 introduces some basic notations, standard results, definitions of the \({k}-\text{LIN}(R)\) problem and variants. Section 4 describes our Kikuchi graph construction for \({k}-\text{LIN}(R)\). In Section 5, we utilize the spectral norm of the Kikuchi graph to distinguish planted vs random \({k}-\text{LIN}(R)\) instances. In Section 6, we describe our simpler algorithm for distinguishing \({k}-\text{LIN}(R)\) instances. In Section 7 we deal with the ‘at most’ \(k\)-sparse version, called \({k}-\text{ALIN}(R)\), and give a simple algorithm to distinguish a planted vs random version of this problem. Finally, in Section 8 we discuss how our techniques and results compare with the works [31] and [28].

2 Overview of the Kikuchi Method↩︎

In this section, we provide a high-level overview of our Kikuchi construction (Section 4) and the spectral method to distinguish planted vs random \({k}-\text{LIN}(R)\) instances (Section 5). We first summarize how this technique was used for the \(k\)-XOR problem (\(k\)-sparse LWE/LPN for \(\mathbb{Z}_2\)), [24] (and independently [25]), and then discuss the modifications we needed to make it work for general rings.

Let us review the steps of the Kikuchi method for \(\mathbb{Z}_2\):

1. Each \(k\)-sparse equation is converted into a set of \(2\)-sparse equations, i.e., equations in two variables. This is done by assigning variables to \(l\)-sized subsets of \([n]\) where \(l\geq k/2\) is a parameter. For each original equation of the form \(C: \sum_{j\in S}{x_j}=b\), we write down equations \(C': y_T + y_{T'}=b\) for all possible \(l\)-sized subsets \(T,T'\subseteq [n]\) such that their symmetric difference equals \(S\). For every vector \(\boldsymbol{s}\in\mathbb{Z}_2^n\), one can define a natural vector \(\boldsymbol{z}\in\mathbb{Z}_2^{\binom{[n]}{l}}\) such that \(\boldsymbol{s}\) satisfies \(C\) iff \(\boldsymbol{z}\) satisfies \(C'\).

2. We note that such sets of \(2\)-sparse equations correspond to a graph with \(\binom{[n]}{l}\) as nodes and an edge between each pair of variables that appear in an equation. The weight of the edge is the value \((-1)^b\), where \(b\) is the RHS of the equation.

3. For the \(k\)-XOR problem an assignment \(\boldsymbol{x}\in\mathbb{Z}_2^n\) has a function called the advantage (or value) associated with it. This advantage is defined in such a way that it is equal (up to scaling) to the quadratic form associated with the adjacency matrix of the graph defined in the previous item. Hence the optimal advantage can be directly related to the spectral norm of the adjacency matrix.

4. Distinguishing an instance as random or planted is done on the basis of spectral norm of the adjacency matrix of this graph. Appropriate tail bounds on the spectral norm are proved to show that it will be unambiguously separated in the two cases. The spectral norm of the expected adjacency matrix is \(0\) in the random case, and in the planted case is of the order of the average degree of the graph, which in turn is proportional to the number of samples of the \(k\)-XOR instance. Thus in order to get tail bounds which are separated in the two cases, it is essential that there are sufficiently many samples.

Now we discuss the specific modifications we made to generalize this for a ring \(R\):

1. To successfully convert a \(k\)-sparse equation to a collection of specific \(2\)-sparse equations, there are a couple of challenges in the \(\left\lvert R \right\rvert>2\) regime that we mitigate. Firstly, the LHS of an equation here consists of a \(k\)-sparse vector \(\boldsymbol{a}\in R^n\) instead of just the non-zero indices for \(\mathbb{Z}_2\). Accordingly, the 2-sparse equations will have to be defined over variables indexed by the subset of \(R^n\) which has \(l\)-sparse vectors. Secondly, for defining the \(2\)-sparse constraints in this space, we will generalize the notion of choosing pairs satisfying a symmetric difference: we choose all pairs \((\boldsymbol{u},\boldsymbol{v})\) such that \(\boldsymbol{v}-\boldsymbol{u} = \boldsymbol{a}\).

2. We want to have \(\mathbb{C}\)-valued signs for each edge pair, so that we could utilize spectral method for random matrices. So the sign of \((\boldsymbol{u},\boldsymbol{v})\) is \(\chi(b)\) for the canonical character map of (the underlying additive group of) \(R\), \(\chi : R \to \mathbb{C}\). Our generalization of symmetric difference is asymmetric and yields a directed graph. To apply the spectral method, it is desirable that the adjacency matrix of the graph be Hermitian. We enable this by adding edges \(\boldsymbol{v}\xrightarrow{\chi(-b)}\boldsymbol{u}\) for every original edge \(\boldsymbol{u}\xrightarrow{\chi(b)}\boldsymbol{v}\) in the graph.

3. We define a new notion of advantage of an assignment. For \(R=\mathbb{Z}_q\) this captures the ‘extent’ to which the assignment violates a constraint (unlike the \(\mathbb{Z}_2\) case where this can only capture whether a constraint got satisfied). We then show that it is equal (up to scaling) to the quadratic form of the (Hermitian) matrix from the previous item.

4. Like the \(\mathbb{Z}_2\) case, we can compute the spectral norm of the adjacency matrix, and prove appropriate tail bounds to ensure a separation between the spectral norms in the random vs planted instances. The method we employed for the tail bounds slightly deviates for that in the case of \(\mathbb{Z}_2\), say in [27]. In the latter, the upper tail bound for the random case was obtained using Matrix Chernoff bounds for Rademacher series, and the lower tail bound for the planted case was obtained using properties of Skellam distribution. We use the Matrix Bernstein inequality to get both the tail bounds.

3 Preliminaries↩︎

3.1 Notations↩︎

Let \(\mathbb{N}, \mathbb{R}, \mathbb{C}\) denote the set of naturals, reals, complex numbers respectively. Let \(\iota = \sqrt{-1}\). For \(n\in\mathbb{N}\), \([n] := \{1,2,\ldots,n\}\). For \(0\leq r\leq n\), \(\binom{[n]}{r}\) denotes the set of all \(r\)-size subsets of \([n]\). For a set \(S\), \(\text{Unif}(S)\) denotes the uniform distribution on \(S\). For \(a\in\mathbb{C}\), \(\text{Re}(a)\) denotes its real part, \(a^*\) denotes its complex conjugate. \(\omega_q := e^{\frac{2\pi\iota}{q}}\) denotes the \(q\)^th primitive root of unity.

For a vector \(\boldsymbol{x}\), unless stated otherwise, \(x_j\) denotes the \(j\)^th coordinate of \(\boldsymbol{x}\). For a matrix \(A\), \(\left\lVert A \right\rVert\) denotes its spectral norm. \(A^{\dagger}\) denotes the conjugate transpose of \(A\). \(\boldsymbol{O}\) denotes a null matrix, and \(\boldsymbol{0}\) denotes a null vector.

For a function \(f:\mathbb{N}\to\mathbb{N}\), the notation \(\widetilde{O}(f(n))\) denotes \(O(f(n)\cdot\texttt{poly}(\log f(n)))\) for some polynomial \(\texttt{poly}(\cdot)\).

In this paper, a ring \(R\) is assumed to be finite, commutative, and to have a multiplicative identity \(1\in R\). For \(t\leq n\), \(R^n_t\) denotes the subset of \(R^n\) consisting of all vectors with exactly \(t\) coordinates in \(R\setminus\{0\}\), and \(R^n_{\leq t}\) is the subset of \(R^n\) consisting of all vectors with at most \(t\) coordinates in \(R\setminus\{0\}\). For \(\boldsymbol{x},\boldsymbol{y}\in R^n\), \(\langle \boldsymbol{x}, \boldsymbol{y} \rangle := x_1y_1 + \ldots +x_ny_n\) denotes the sum of their coordinate-wise products (the ring product operation).

For a vector \(\boldsymbol{x} \in R^n\), we denote \(\boldsymbol{x}^{\odot l}\in R^{R^n_l}\) as the vector whose \(\boldsymbol{u}\textsuperscript{th}\) coordinate (for \(\boldsymbol{u}\in R^n_l\)) is given by \(x^{\odot l}_{\boldsymbol{u}} := \langle \boldsymbol{u}, \boldsymbol{x} \rangle\).

For a directed graph \(\mathcal{G}\), let \(\text{out-deg}_{\mathcal{G}}(T)\) denote the number of outgoing edges of a vertex \(T\) of \(\mathcal{G}\), and let \(D(\mathcal{G})\) denote the maximum outgoing degree of \(\mathcal{G}\). We may skip writing \(\mathcal{G}\) in these notations when the graph is clear in the context.

3.2 Canonical Character of an Abelian Group↩︎

For a ring \(R\), its underlying additive group is finite and abelian, so it can be assumed to be group isomorphic to \(\mathbb{Z}_{q_1}\times\ldots\times\mathbb{Z}_{q_t}\). Let \(\psi : (R,+) \to \mathbb{Z}_{q_1}\times\ldots\times\mathbb{Z}_{q_t}\) be this group isomorphism, which we can find in \(\widetilde{O}(\left\lvert R \right\rvert)\) time. Define the canonical character of \(R\) as the group homomorphism \[\begin{align} \chi_R : &(R,+) \to \left(\mathbb{C},\cdot\right) \\ &x \mapsto \omega_{q_1}^{\psi(x)_1}\cdots\omega_{q_t}^{\psi(x)_t} \end{align}\]

We write \(\chi_R\) as simply \(\chi\) when the ring is clear in the context.

3.3 Concentration Inequalities↩︎

Let us state tail bound results for random variables (both scalar and matrix) which we will use in this work.

The Matrix Bernstein Inequality bounds the norm of a sum of random Hermitian matrices (see, e.g., [32]).

3.4 \({k}-\text{LIN}(R)\)↩︎

We now state definitions and problems related to sparse systems of linear equations over a ring.

For a \({k}-\text{LIN}(R)\) or \({k}-\text{ALIN}(R)\) instance \(\mathcal{I}\), we view \((\boldsymbol{a},b)\in\mathcal{I}\) as a \(R\)-linear homogeneous equation in \(n\) variables \(x_1,\ldots,x_n\): \(\sum_{j\in[n]}{a_{j}x_j} = b\).

Next, we define a notion of advantage of an assignment for an instance.

When \(R = \mathbb{Z}_2\), Definition 6 relates to the more popular notion of fraction of satisfied constraints by an assignment; indeed \(\text{adv}_{\mathcal{I}}(\boldsymbol{x})\) is simply the fraction of satisfied minus the fraction of violated constraints.

When \(R=\mathbb{Z}_q\), the advantage takes into account the ‘extent’ to which a constraint is violated. For \(q>2\), if \(\boldsymbol{x}\) violates \((\boldsymbol{a},b)\) (i.e. \(b\ne\langle \boldsymbol{a}, \boldsymbol{x} \rangle\)), \(b-\langle \boldsymbol{a}, \boldsymbol{x} \rangle\) can take any value in \(\mathbb{Z}_q^*\). For \(i\in[m]\), let \(b_i = \langle \boldsymbol{a}_i, \boldsymbol{x} \rangle + e_i\) (i.e. \(e_i\) is the error term for \(\boldsymbol{x}\) with respect to \(i\textsuperscript{th}\) constraint in the linear equation version; w.l.o.g., \(-q/2\leq e_i\leq q/2\)). We can rewrite the advantage as follows: \[\begin{align} \texttt{adv}_{\mathcal{I}}(\boldsymbol{x}) = \frac{1}{m}\sum_{i\in[m]}\cos{\left(\frac{2\pi\left\lvert e_i \right\rvert}{q}\right)} = 1 - \frac{2}{m}\left(\sum_{i\in[m]}\sin^2{\left(\frac{\pi\left\lvert e_i \right\rvert}{q}\right)}\right) \label{advantage32interpretation} \end{align}\tag{1}\] The \(\sin(\cdot)\) function increases in the range of \(\left\lvert e_i \right\rvert\), so in some sense, each term in the summand measures the ‘extent’ to which \(\boldsymbol{x}\) violates \((\boldsymbol{a}_i,b_i)\).
Now we will define random and planted versions of \({k}-\text{LIN}(R)\) and \({k}-\text{ALIN}(R)\). To do this for \({k}-\text{ALIN}(R)\) we first define a distribution for choosing left-hand sides, generalizing the distribution described in [28].

3.4.1 Sparse LWE and Sparse LPN.↩︎

We first recall the discrete Gaussian distribution on the integers and \(\mathbb{Z}_q\).

Let us state a couple of observations related to the discrete Gaussian, which shall be useful later.

We now recall the \(k\)-sparse LWE problem from [28].

The standard decisional LWE problem is identical to \(k-\text{ALWE}_{n,m,q,r}\) problem for \(k=n\).

We also define a sparse version of the Learning Parity with Noise(LPN) problem for higher modulus, which (the non-sparse version) was defined in [33].

Let us compute \(\mathop{\mathrm{\mathbb{E}}}[\chi(\zeta_{\mathbb{Z}_q,\mu})]\) which will be useful for us.

4 A Kikuchi Graph Construction↩︎

In this section, our objective is to distinguish a random instance of \({k}-\text{LIN}(R)\) from a planted such instance.

We will develop the insight of viewing a \(k\)-sparse \(R\)-linear equation as the edges of a graph in a large vertex space. Given a \({k}-\text{LIN}(R)\) instance \(\mathcal{I}\), we wish to produce a directed graph, namely \(\mathcal{K}_l(\mathcal{I})\)(for some parameter \(l\)). This technique was introduced for the \(k\)-XOR problem by Wein. et. al. [24] (and implicitly by Hastings [25]). Having a graph representative of the instance allows us to use spectral properties of the graph for the distinguishing problem.

For a head start, here is some intuition on how this is done: Let us consider a transformed space whose dimensions are indexed by \(R^n_{k/2}\) (assume for simplicity for now that \(k\) is even). Then an equation over indeterminates \(\{x_i\}_{i\in[n]}\) \[C: {a_{i_1}}x_{i_1} + \ldots + {a_{i_k}}x_{i_k} = b_i\] can be converted to an equation over indeterminates \(\{y_{\boldsymbol{u}}\}_{\boldsymbol{u}\in R^{n}_{k/2}}\) \[C': y_{\boldsymbol{v}} - y_{\boldsymbol{u}} = b_i\] where \(\boldsymbol{u},\boldsymbol{v}\) satisfy \[u_{j} = \begin{cases} -a_{j} &\text{ for j=i_1,\ldots,i_{k/2} } \\ 0&\text{ otherwise} \end{cases}\;\;\;v_{j} = \begin{cases} a_{j} &\text{ for j=i_{k/2+1},\ldots,i_{k} } \\ 0&\text{ otherwise} \end{cases}\] The rationale behind this conversion is this: For \(\boldsymbol{s}\in R^n\), consider \(\boldsymbol{s}^{\odot k/2}\in R^{R^n_{k/2}}\). As mentioned in Section 3, this is defined as follows: \(s^{\odot k/2}_{\boldsymbol{u}} := \sum_{j\in[n]}u_js_j\). Then \(\boldsymbol{s}\) satisfies equation \(C\) iff \(\boldsymbol{s}^{\odot k/2}\) satisfies \(C'\).

Now we can define a graph over the vertex set \(R^n_{k/2}\), where \(C'\) can be viewed as an edge \(\boldsymbol{u}\rightarrow \boldsymbol{v}\) with a sign that can be a function of \(b_i\). We will define this sign to be \(\chi(b_i)\); this will make the graph’s adjacency matrix complex valued and will enable us to utilize the well-studied spectral theory of Hermitian matrices.

The above choice of non-zero indices for \(\boldsymbol{u},\boldsymbol{v}\) is only one of \(\binom{k}{k/2}\) possible choices; we can choose any of the \(k/2\) indices for \(\boldsymbol{u}\). Furthermore, note that the following generalizations can also be made:

• We need not restrict ourselves to \((k/2)\) non-zero indices, we can have \(l\) non-zero indices in \(\boldsymbol{u},\boldsymbol{v}\) for an appropriate \(l\geq k/2\).

• We also have some freedom to choose the values \(u_j, v_j\), for instance we could have defined \(u_{i_1} = 1-a_{i_1}, v_{i_1} = 1\) and still maintained that \(\boldsymbol{s}\) satisfies \(C\) iff \(\boldsymbol{s}^{\odot k/2}\) satisfies \(C'\).

For a constraint \((\boldsymbol{a},b)\in\mathcal{I}\), how many corresponding edges does \(\mathcal{K}_l(\mathcal{I})\) have? Before venturing to compute this, let us rewrite Construction 18 in a way that is more amenable to computing this.

We will now compute \(\theta^{(n,l,k)}\) which is the number of edges added in \(\mathcal{K}_l(\mathcal{I})\) corresponding to the constraint \((\boldsymbol{a},b)\in\mathcal{I}\).

Let \(r_{1a}, r_{1b}, r_{2a}, r_{2b}, r_{2c}\) denote the number of indices on which conditions 1(a), 1(b), 2(a), 2(b), 2(c) are applied respectively. It can be seen that the following must be satisfied: \[\begin{align} &r_{1a} + r_{1b} + r_{2a} + r_{2b} + r_{2c} = n\;\;\;(\text{total32indices}) \tag{2} \\ &r_{1b} + r_{2a} + r_{2c} = l\;\;\;(\text{non-zero entries of }\boldsymbol{u}) \tag{3}\\ &r_{1b} + r_{2b} + r_{2c} = l\;\;\;(\text{non-zero entries of }\boldsymbol{v}) \tag{4}\\ &r_{2a} + r_{2b} + r_{2c} = k\;\;\; (\text{non-zero entries of }\boldsymbol{a})\tag{5} \end{align}\]

If \(r_{2c} = r \in \{0,1,\ldots,k\}\), we obtain \(r_{2a}=r_{2b}=(k-r)/2\) from 3 , 4 , 5 , \(r_{1b} = l-(k+r)/2\) from 3 , \(r_{1a} = n-l-(k-r)/2\) from 2 . For indices \(j\) of condition 1(b), we have \((\left\lvert R \right\rvert-1)=\left\lvert R \right\rvert-1\) choices of \((u_j,v_j)\), and for indices \(j\) of condition 2(c), we have \(\left\lvert R \right\rvert-2\) choices of \((u_j,v_j)\).

Thus we get the number of constraints for each original constraint as: ⁴ \[\begin{align} \theta^{(n,l,k)} = 2\sum_{r=0}^t\binom{k}{r}(\left\lvert R \right\rvert-2)^r\binom{k-r}{(k-r)/2}\binom{n-k}{l-(k+r)/2}(\left\lvert R \right\rvert-1)^{l-(k+r)/2} \label{theta} \end{align}\tag{6}\]

Note that in 6 , only the terms where \(r\) has same parity as \(k\) are positive.

We can obtain two lower bounds for \(\theta^{(n,l,k)}\). One of them will come from the summand of \(r=0\) or \(r=1\), depending on whether \(k\) is even or odd, respectively.

\[\begin{align} \text{Assuming \ceil{k/2}\leq l\leq n-\floor{k/2}, }\;\;\theta^{(n,l,k)} \geq \frac{2^{k-1}}{(k+1)}\binom{n-k}{l-\ceil{k/2}}(\left\lvert R \right\rvert-1)^{l-\floor{k/2}} \label{theta32lower32bound95r610} \end{align}\tag{7}\]

The other bound will come from the \(r=k\) summand term.

\[\begin{align} \text{Assuming k\leq l\leq n, }\;\;\theta^{(n,l,k)} \geq 2^{1-k}\binom{n-k}{l-k}(\left\lvert R \right\rvert-1)^{l} \label{theta32lower32bound32r61k} \end{align}\tag{8}\]

Depending on whether \(\left\lvert R \right\rvert\) is small or large, we will use these bounds for our analysis.

5 Distinguishing by spectral method over Kikuchi Graphs↩︎

The Kikuchi Graph \(\mathcal{K}_l(\mathcal{I})\) can be naturally associated with its adjacency matrix (for simplicity, we use the same notation to denote the adjacency matrix)⁵. By Construction 18, for every edge \(\boldsymbol{u}\xrightarrow{\chi(b)}\boldsymbol{v}\), we have the edge \(\boldsymbol{v}\xrightarrow{\chi(-b)}\boldsymbol{u}\) present in the graph. Therefore \(\mathcal{K}_l(\mathcal{I})\) is Hermitian.

Our certificate to determine whether \(\mathcal{I}\) is planted or random will be the spectral norm of \(\mathcal{K}_l(\mathcal{I})\). To give some intuition for this, let us relate the optimal advantage of \(\mathcal{I}\) with the spectral norm of \(\mathcal{K}_l(\mathcal{I})\).

Proposition 7 gives some evidence that estimating the spectral norm of \(\left\lVert \mathcal{K}_l(\mathcal{I}) \right\rVert\) may be helpful for distinguishing a random vs planted instance. One consequence of this proposition is that we can hope \(\left\lVert \mathcal{K}_l(\mathcal{I}) \right\rVert\) to be high when \(\mathcal{I}\) is planted. We will show that this is indeed the case with high probability. Moreover, to separate the random instance using this quantity, we also need to show that \(\left\lVert \mathcal{K}_l(\mathcal{I}) \right\rVert\) is low with high probability when \(\mathcal{I}\) is random. The rest of the argument in this section is about proving tail bounds for \(\left\lVert \mathcal{K}_l(\mathcal{I}) \right\rVert\) in both cases.

5.1 Independent Summands of \(\mathcal{K}_l(\mathcal{I})\)↩︎

Firstly for a \({k}-\text{LIN}(R)\) instance \(\mathcal{I}= \{(\boldsymbol{a}_i,b_i)\}_{i\in[m]}\) we write \(\mathcal{K}_l(\mathcal{I})\) as a sum of independent Hermitian matrices: \[\begin{align} \mathcal{K}_l(\mathcal{I}) &= \sum_{i\in[m]}\boldsymbol{K}_i \\ \boldsymbol{K}_i(\boldsymbol{u},\boldsymbol{v}) &:= \begin{cases} \chi(b_i) & \text{if }\boldsymbol{v}-\boldsymbol{u} = \boldsymbol{a}_i \\ \chi(-b_i) & \text{if }\boldsymbol{u}-\boldsymbol{v} = \boldsymbol{a}_i \\ 0 & \text{otherwise} \end{cases} \label{eqn:Xi} \end{align}\tag{9}\]

By definition, \(\boldsymbol{K}_i\) are Hermitian, and independent as the constraints in \(\mathcal{I}\) are independent.

We now prepare to establish some key properties of \(\boldsymbol{K}_i\). Observe that the graph corresponding to \(\boldsymbol{K}_i\) is a collection of disjoint chains (see illustration in Figure 1). This is because the graph corresponding to \(\boldsymbol{K}_i\) never contains constraints \((\boldsymbol{u},\boldsymbol{v},\chi(b_i))\) and \((\boldsymbol{u}',\boldsymbol{v}',\chi(b_i))\) with (\(\boldsymbol{u} = \boldsymbol{u}'\;\land\;\boldsymbol{v} \neq \boldsymbol{v}'\)), or (\(\boldsymbol{u} \neq \boldsymbol{u}'\;\land\;\boldsymbol{v} = \boldsymbol{v}'\)).

Let us prove an upper bound on the spectral norm of the adjacency matrix of a signed graph. This is a generalization of the well known spectral norm bound of an unsigned graph.

The following upper bound for \(\left\lVert \boldsymbol{K}_i \right\rVert\) follows as a corollary of Observation 21 and Lemma 1.

Next, we state a result regarding sum of squares of \(\{\boldsymbol{K}_i\}_{i\in[m]}\). Looking ahead, this will be useful to compute the variance statistic corresponding to \(\mathcal{K}_l(\mathcal{I})\). The key observation is that \(\boldsymbol{K}_i^2\) can be viewed as an adjacency matrix of a graph that captures “2-hops” of the original graph of \(\boldsymbol{K}_i\).

Let us now obtain an upper bound on \(D(\mathcal{K}_l(\mathcal{I}))\), for which we use the distribution of the ‘left-hand sides’, i.e. the fact that \(\boldsymbol{a}_i\xleftarrow{\text{iid}}\text{Unif}(R^n_k)\). Recall that this is the setting in both the random and planted instances.

5.2 An upper bound for the random instance↩︎

We will show that when \(\mathcal{I}\) is a random \({k}-\text{LIN}(R)\) instance, an upper bound on \(\left\lVert \mathcal{K}_l(\mathcal{I}) \right\rVert\) holds with high probability. To establish this, let us apply the Matrix Bernstein inequality to our case.

We start with analysing the summands \(\boldsymbol{K}_i\)’s further when \(\mathcal{I}\) is a random instance.

With this, the antecedent of Theorem 6 is satisfied (taking \(\boldsymbol{X}_i = \boldsymbol{K}_i\)) with \(\left\lVert \boldsymbol{K}_i \right\rVert \leq 2\) (from Corollary 1) for all \(i\in[m]\). Also, from Lemma 2, we have \[\begin{align} \label{X95i32sigma2} \sigma^2 = \left\| \sum_{i\in[m]} \mathbb{E}\left[\boldsymbol{K}_i^{2}\right] \right\| \leq 2 D(\mathcal{K}_l(\mathcal{I})) \end{align}\tag{10}\]

Now we choose an appropriate value of \(t\) to limit the probability in Theorem 6 to be an inverse polynomial of \(N = \left\lvert R^n_l \right\rvert = \binom{n}{l}(\left\lvert R \right\rvert-1)^l\), say \(N^{-\epsilon}\) for some choice of \(\epsilon > 0\). Thus we must satisfy \[\begin{align} &N \cdot \exp\!\left( \frac{-t^{2}/2}{2D(\mathcal{K}_l(\mathcal{I})) + 2t/3} \right) \leq N^{-\epsilon} \label{quadratic32in32t} \end{align}\tag{11}\]

By simplifying 11 we have the following upper bound for the maximum eigenvalue:

When the left-hand sides \(\boldsymbol{a}_i\xleftarrow{\text{iid}}\text{Unif}(R^n_k)\) (which is the case for a random instance), Proposition 8 gives us that \(D(\mathcal{K}_l(\mathcal{I}))\) is upper bounded by \((1+\delta)\Delta\) with high probability, where \(\Delta = \frac{m\theta^{(n,l,k)}}{N}\) is the average out-degree of \(\mathcal{K}_l(\mathcal{I})\), and \(\delta>0\) is a constant. We can now combine Corollary 2 and Proposition 8 to get an upper bound on the spectral norm with respect to \(\Delta\). We would like to choose \(\Delta\) (which in turn means choosing the number of constraints \(m\) in \(\mathcal{I}\)) so that we get \(\left\lVert \mathcal{K}_l(\mathcal{I}) \right\rVert \leq \delta \Delta\). Observe that in ?? we can impose \[\Delta \geq \frac{16\delta + 12}{3\delta^2} (1+\epsilon)\ln N\] to get this desired bound for all \(\delta>0\). Also, the probability of failure in Proposition 8 is upper bounded by \(N^{-\epsilon}\) for this choice.

Finally let us restate this result in terms of the parameters of \(\mathcal{I}\).

Here we will use the lower bounds of \(\theta^{(n,l,k)}\) from 7 , 8 depending on the value of \(\left\lvert R \right\rvert\) and \(l\).

If \(\left\lvert R \right\rvert = O(n/l)\), then 7 will give a better bound than 8 . On the other hand, if \(\left\lvert R \right\rvert = \omega(n/l)\), 8 gives a better bound.

5.3 A lower bound for the planted instance↩︎

Recall that the only difference in a planted instance from a random instance of \({k}-\text{LIN}(R)\) is that the ‘right-hand side’ \(b_i\in R\) of a constraint \((\boldsymbol{a}_i,b_i)\) is correlated with \(\boldsymbol{a}_i\).

We will impose a mild assumption on the noise distribution \(\Psi\) for the planted instance: the quantity \(\rho := \mathop{\mathrm{\mathbb{E}}}[\chi(\Psi)]\in\mathbb{R}\setminus\{0\}\).⁷

The heart of our analysis will still be the Matrix Bernstein inequality, but with a slightly different set of matrices. This is because Lemma 4 (\(\mathop{\mathrm{\mathbb{E}}}[\boldsymbol{K}_i] = \boldsymbol{O}\)) will no longer hold for the same definition of \(\boldsymbol{K}_i\) when \(\mathcal{I}\) is planted. Let us calculate \(\mathop{\mathrm{\mathbb{E}}}[\boldsymbol{K}_i]\).

Notice that \(\sum_{i\in[m]}A_{\boldsymbol{s},\boldsymbol{a}_i}\) can be viewed as a signed adjacency matrix of an appropriate graph. This graph has the same edges as in \(\mathcal{K}_l(\mathcal{I})\) but with different signs. Analogous to the spectral norm of an adjacency matrix being lower bounded by the average degree of the graph, we will set a lower bound for the spectral norm of \(\sum_{i\in[m]}A_{\boldsymbol{s},\boldsymbol{a}_i}\) which will be useful later.

Let us now define \(\widetilde{\boldsymbol{K}_i} := \boldsymbol{K}_i - \mathop{\mathrm{\mathbb{E}}}[\boldsymbol{K}_i] = \boldsymbol{K}_i - \rho A_{\boldsymbol{s},\boldsymbol{a}_i}\). By definition, \(\mathop{\mathrm{\mathbb{E}}}[\widetilde{\boldsymbol{K}_i}] = \boldsymbol{O}\). Let us also obtain a bound on its spectral norm.

To apply the Matrix Bernstein inequality, we are left to compute \[\sigma^2 := \left\| \sum_{i\in[m]} \mathbb{E}\left(\widetilde{\boldsymbol{K}_i}^{2}\right) \right\|\] \[\begin{align} \sigma^2 &= \left\| \sum_{i\in[m]} \mathbb{E}\left(\left(\boldsymbol{K}_i - \rho A_{\boldsymbol{s},\boldsymbol{a}_i}\right)^2\right) \right\| \;\;= \left\| \sum_{i\in[m]} \left(\mathbb{E}\left(\boldsymbol{K}_i^2\right) - \rho^2 A_{\boldsymbol{s},\boldsymbol{a}_i}^2\right) \right\| \\ &\leq \left\| \sum_{i\in[m]} \mathbb{E}\left(\boldsymbol{K}_i^2\right)\right\| + \left\lvert \rho \right\rvert^2 \left\|\sum_{i\in[m]}A_{\boldsymbol{s},\boldsymbol{a}_i}^2 \right\| \\ &\leq 2(1+\left\lvert \rho \right\rvert^2)D(\mathcal{K}_l(\mathcal{I})) \;\;(\text{using Lemma~\ref{variance32bound} and same idea for }A_{\boldsymbol{s},\boldsymbol{a}_i}^2) \end{align}\]

Like the random case, we need to choose an appropriate value of \(t\) to limit the probability in Theorem 6 to be essentially an inverse polynomial of \(N = \left\lvert R^n_l \right\rvert = \binom{n}{l}(\left\lvert R \right\rvert-1)^l\), say \(N^{-\epsilon}\) for some choice of \(\epsilon > 0\). Thus we must satisfy \[\begin{align} &N \cdot \exp\!\left( \frac{-t^{2}/2}{2\left(1+\left\lvert \rho \right\rvert^2\right)D(\mathcal{K}_l(\mathcal{I})) + 2(1+\left\lvert \rho \right\rvert)t/3} \right) \leq N^{-\epsilon} \label{quadratic32in32t32for32planted32case} \end{align}\tag{13}\]

It can be seen that 13 is satisfied for (denote \(Z = (1+\epsilon)\ln N\) in below equation) \[\begin{align} t \geq \frac{2}{3}\left( (1+\left\lvert \rho \right\rvert)Z + \sqrt{ \big((1+\left\lvert \rho \right\rvert)Z\big)^2 + 9\left(1+\left\lvert \rho \right\rvert^2\right) D(\mathcal{K}_l(\mathcal{I})) Z }\right) \label{t32threshold32for32planted32case} \end{align}\tag{14}\]

Like the random case, the next step would have been to bound \(D(\mathcal{K}_l(\mathcal{I}))\). Fortunately, we can again assume \(D(\mathcal{K}_l(\mathcal{I}))\leq (1+\gamma)\Delta\) from Proposition 8; even when \(\mathcal{I}\) is planted, since \(\boldsymbol{a}_i\xleftarrow{\text{iid}}\text{Unif}(R^n_k)\).

So, let us now proceed to get an upper bound on \(\left\lVert \sum_{i\in[m]}\widetilde{\boldsymbol{K}_i} \right\rVert\) with respect to \(\Delta\). Like before, we would like to choose \(\Delta\) so that we get \(\left\lVert \sum_{i\in[m]}\widetilde{\boldsymbol{K}_i} \right\rVert \leq \gamma \Delta\). Observe that in equation 14 we can impose \[\Delta \geq \frac{12(1+\left\lvert \rho \right\rvert^2)(1+\gamma)+4\gamma(1+\left\lvert \rho \right\rvert)}{3\gamma^2}(1+\epsilon)\ln N\] to get this desired bound for all \(\gamma>0\). Again, the failure probability of Proposition 8 is bounded by \(N^{-\epsilon}\) for this choice.

We now have \(\left\lVert \sum_{i\in[m]}\widetilde{\boldsymbol{K}_i} \right\rVert \leq \gamma\Delta\). How do we proceed to get a lower bound for \(\left\lVert \sum_{i\in[m]}{\boldsymbol{K}_i} \right\rVert = \left\lVert \mathcal{K}_l(\mathcal{I}) \right\rVert\)? \[\begin{align} \left\lVert \mathcal{K}_l(\mathcal{I}) \right\rVert &= \left\lVert \sum_{i\in[m]}{\boldsymbol{K}_i} \right\rVert \;\geq \left\lVert \sum_{i\in[m]}{\mathop{\mathrm{\mathbb{E}}}[\boldsymbol{K}_i}] \right\rVert - \left\lVert \sum_{i\in[m]}\widetilde{\boldsymbol{K}_i} \right\rVert \\ &\geq \left\lvert \rho \right\rvert\left\lVert \sum_{i\in[m]}{A_{\boldsymbol{s},\boldsymbol{a}_i}} \right\rVert - \gamma\Delta \;\;(\text{from Lemma \ref{X95i32expected32value32for32planted32case}}) \\ &\geq \left\lvert \rho \right\rvert\Delta - \gamma\Delta \;\;(\text{from Proposition \ref{eigenvalue32lower32bound32for32signed32adjacency32matrix}}) \end{align}\]

Finally let us restate this result in terms of the parameters of \(\mathcal{I}\). Once again we will use the lower bounds of \(\theta^{(n,l,k)}\) from 7 , 8 ; the better result can be used depending on whether \(\left\lvert R \right\rvert = O(n/l)\) or \(\left\lvert R \right\rvert = \omega(n/l)\).

5.4 Distinguishing between a planted and a random instance↩︎

Corollaries 3, 4 and Corollaries 5, 6 together suggest that we can solve the decisional \({k}-\text{LIN}(R)\) problem with high probability if we had the ability to approximate the maximum eigenvalue of \(\mathcal{K}_l(\mathcal{I})\). For this, we need to ensure that the thresholds established in these corollaries are separated. In particular, we must have \((\left\lvert \rho \right\rvert - \gamma)\Delta > \delta\Delta\), which can be easily achieved by setting, say, \(\gamma = \delta = \left\lvert \rho \right\rvert/4\).

We can then use a standard eigenvalue estimation technique, say the Power Iteration method, to approximate \(\left\lVert \mathcal{K}_l(\mathcal{I}) \right\rVert\). Note that \(\mathcal{K}_l(\mathcal{I})\) is a \(N\times N\) matrix for \(N = \binom{n}{l}(\left\lvert R \right\rvert-1)^l\). Moreover, it is a sparse matrix since each row has at most \(D(\mathcal{K}_l(\mathcal{I})) = O(\Delta)\) non-zero entries, where \(\Delta = O(\ln N)\) suffices for our purpose. Thus, the Power Iteration takes \(\widetilde{O}(N) = \widetilde{O}\left(\binom{n}{l}(\left\lvert R \right\rvert-1)^l\right)\) time to converge.

An important aspect of this distinguisher is that it works for any (nice enough) noise distribution of the planted instance. The sample complexity required by the algorithm is inversely proportional to \(\left\lvert \rho \right\rvert^2\) where \(\rho = \mathop{\mathrm{\mathbb{E}}}[\chi(\Psi)]\). The sample and time complexities do not depend on any other property of the noise distribution. Also, as long as \(\left\lvert \rho \right\rvert\) is sufficiently large (say at least inverse polynomial in \(n\)), it won’t affect the sample complexity by a lot. As immediate consequences of Corollaries 7, 8 we have algorithms for solving \(k\)-sparse LWE and sparse LPN over modulus \(q\).

For sparse LWE, we can compute \(1/\rho^2 \leq e^{2\pi r^2/q^2}\) (Observation 9.1). Since the width \(r\) for the LWE distribution is chosen to be less than \(q\), this dependency will only contribute a constant term.

For sparse LPN, \(\rho = 1 - \frac{q\mu}{q-1}\) from Definition 16. (For \(\mu\rightarrow \frac{q-1}{q}\), the planted distribution approaches the random distribution.)

5.5 A quantum speedup↩︎

In essence, to distinguish a random \({k}-\text{LIN}(R)\) instance from a planted one, the Kikuchi method performs estimation of the spectral norm of a sparse Hermitian matrix in a space of dimension \(N = \binom{n}{l}(\left\lvert R \right\rvert-1)^l\). For any known classical method, such as the power iteration, eigenvalue estimation requires matrix multiplications, so it is unlikely for the time complexity to go below \(\widetilde{\Omega}(N)\).

However, with quantum algorithmic techniques, we can do better. We can use the same idea as given by Schmidhuber et. al. in [27] for \(R = \mathbb{Z}_2\): Using a guiding state created from the \({k}-\text{LIN}(R)\) instance, we are able to determine whether the eigenspace corresponding to eigenvalues \(\geq \lambda\) (for some threshold \(\lambda > 0\)) is non-empty. This enjoys a speedup on Power iteration which can be from quadratic to quartic depending on the choice of parameter \(l\). We elaborate on this intuition in Appendix 10. For even more details, the reader may refer to Appendix C of [27].

6 A Simple Algorithm↩︎

In this section, we describe another algorithm for distinguishing whether a \({k}-\text{LIN}(R)\) instance is random or planted. This algorithm is simpler than the spectral method and outperforms the latter when \(\left\lvert R \right\rvert\) is large, specifically \(\left\lvert R \right\rvert = \omega(n/l)\); like the spectral method, \(l\) here is a parameter used for sample-time complexity tradeoff. This algorithm in essence, is the dense-minor attack proposed in [28]. It is also similar to the simple refutation algorithm proposed in Section 8 of [31], but is more efficient since we process only one dense minor instead of all \(\binom{n}{l}\) dense minors⁸. We describe this in Algorithm 2.

Essentially, the algorithm distinguishes by (naively) computing the advantage for a sub-instance \(\mathcal{I}'\) of \(\mathcal{I}\). This is efficient enough for us as it only needs to check for assignments \(\boldsymbol{x}\) having only first \(l\) coordinates non-zero. In particular, Algorithm 2 takes time \(O(mn + \left\lvert R \right\rvert^l\left\lvert \mathcal{I}' \right\rvert k\log\left\lvert R \right\rvert)\) time since this is the time taken by steps 1 and 2.

Firstly we state that \(\mathcal{I}'\) defined in step 1 of the algorithm has sufficiently many constraints. This can be shown via a routine calculation.

We proceed by assuming \(\mathcal{I}'\) has \(m'\geq \frac{l\ln(\left\lvert R \right\rvert n)}{\left\lvert \rho \right\rvert^2}\) constraints, where \(\rho := \mathop{\mathrm{\mathbb{E}}}[\chi(\Psi)]\ne0\) for noise \(\Psi\). For \(\boldsymbol{x}\in R^n\), let us denote \(\texttt{adv}_{\boldsymbol{x}} := \frac{1}{\left\lvert \mathcal{I}' \right\rvert}\sum\limits_{(\boldsymbol{a},b)\in\mathcal{I}'}\chi\left(b-\langle \boldsymbol{a}, \boldsymbol{x} \rangle\right)\).

We first analyze the random case. If \(\mathcal{I}\) is random, for every \((\boldsymbol{a},b)\in\mathcal{I}'\), \(b\) is uniformly random in \(R\), and so is \(b-\langle \boldsymbol{a}, \boldsymbol{x} \rangle\) for an arbitrary \(\boldsymbol{x}\in R^n\). From Observation 2, we have \(\mathop{\mathrm{\mathbb{E}}}\left[\chi(b-\langle \boldsymbol{a}, \boldsymbol{x} \rangle)\right]=0\). So \[\begin{align} \forall\;\boldsymbol{x}\in R^n,\;&\mathop{\mathrm{\mathbb{E}}}[\texttt{adv}_{\boldsymbol{x}}] = \frac{1}{m'}\sum\limits_{(\boldsymbol{a},b)\in\mathcal{I}'}\mathop{\mathrm{\mathbb{E}}}\left[\chi(b-\langle \boldsymbol{a}, \boldsymbol{x} \rangle)\right] = 0 \\ \Rightarrow &\Pr\left[\left\lvert \texttt{adv}_{\boldsymbol{x}} \right\rvert > \left\lvert \rho \right\rvert/2\right] < 2e^{-m'\left\lvert \rho \right\rvert^2/8} \tag{15} \\ \Rightarrow&\Pr\left[\texttt{adv} > \left\lvert \rho \right\rvert/2\right] < 2\left\lvert R \right\rvert^le^{-m'\left\lvert \rho \right\rvert^2/8} \leq 2n^{-l/8} \tag{16} \end{align}\] where the second inequality follows from applying Hoeffding inequality (Theorem 5) over random variables \(\{\chi(b-\langle \boldsymbol{a}, \boldsymbol{x} \rangle)\}_{(\boldsymbol{a},b)\in\mathcal{I}'}\), and the last inequality follows by a union bound over all \(\boldsymbol{x}\in R^n\) having non-zero entries only on first \(l\) coordinates.

Now let us see what happens in the planted case. Suppose \(\mathcal{I}\) is planted with respect to the secret vector \(\boldsymbol{s}\in R^n\). Let \(\boldsymbol{s}'\in R^n\) be defined as follows: \[\begin{align} s'_j = \begin{cases} s_j\;\text{if }j\leq l\\ 0\;\text{if }j>l \end{cases} \end{align}\]

Then for every \((\boldsymbol{a},b)\in\mathcal{I}'\), \(b = \langle \boldsymbol{a}, \boldsymbol{s} \rangle+e = \langle \boldsymbol{a}, \boldsymbol{s}' \rangle+e\) such that \(\mathop{\mathrm{\mathbb{E}}}[\chi(e)]=\rho\).

Thus \[\begin{align} &\mathop{\mathrm{\mathbb{E}}}[\texttt{adv}_{\boldsymbol{s}'}] = \frac{1}{m'}\sum\limits_{(\boldsymbol{a},b)\in\mathcal{I}'}\mathop{\mathrm{\mathbb{E}}}\left[\chi(b-\langle \boldsymbol{a}, \boldsymbol{s}' \rangle)\right] = \frac{1}{m'}\sum\limits_{(\boldsymbol{a},b)\in\mathcal{I}'}\mathop{\mathrm{\mathbb{E}}}\left[\chi(e)\right] = \rho \\ \Rightarrow &\Pr\left[\texttt{adv} < \left\lvert \rho \right\rvert/2\right] \leq \Pr\left[\left\lvert \texttt{adv}_{\boldsymbol{s}'} \right\rvert < \left\lvert \rho \right\rvert/2\right] \\ &\leq \Pr\left[\left\lvert \texttt{adv}_{\boldsymbol{s}'}-\rho \right\rvert > \left\lvert \rho \right\rvert/2\right] < 2e^{-m'\rho^2/8} \leq 2(\left\lvert R \right\rvert n)^{-l/8}\;\;(\text{using Theorem~\ref{thm:Hoeffding}}) \end{align}\]

Hence we get the following result:

7 Distinguishing random vs planted \({k}-\text{ALIN}(R)\) instances↩︎

Let us also analyze the distinguishing problem for \({k}-\text{ALIN}(R)\), i.e. when the left-hand sides are at most \(k\)-sparse and follow the distribution in Definition 7. As it may seem intuitively, we will get substantially better time and sample complexities in this version of the problem compared to \({k}-\text{LIN}(R)\).

Firstly, it can be seen that Algorithm 2 will work just as well if \(\mathcal{I}\) is a \({k}-\text{ALIN}(R)\) instance. Hence the problem enjoys the sample-time complexity tradeoff as laid out in Theorem 14.

We now describe another strategy. Recall from Observation 8 that the probability of sampling \(\boldsymbol{0}\in R^n\) as a left-hand side is \(p_0 = \left\lvert R \right\rvert^{-k}\). What if we have enough samples \(m\) in \(\mathcal{I}\) so that there are \(m'\geq l\ln n/\left\lvert \rho \right\rvert^2\) constraints in \(\mathcal{I}\) of the form \((\boldsymbol{0},b)\)? Let us call this collection \(\mathcal{I}'=\{(\boldsymbol{0},b)\}\subseteq\mathcal{I}\). Similar to Algorithm 2, we can compute \[\begin{align} \texttt{adv} = \frac{1}{m'}\sum_{(\boldsymbol{0},b)\in\mathcal{I}'}\chi(b) \end{align}\] If \(\mathcal{I}\) is random, we have \[\begin{align} &\mathop{\mathrm{\mathbb{E}}}[\texttt{adv}] = \frac{1}{m'}\sum\limits_{(\boldsymbol{0},b)\in\mathcal{I}'}\mathop{\mathrm{\mathbb{E}}}\left[\chi(b)\right] = 0 \\ \Rightarrow&\Pr\left[\left\lvert \texttt{adv} \right\rvert > \left\lvert \rho \right\rvert/2\right] < 2e^{-m'\left\lvert \rho \right\rvert^2/8} \leq 2n^{-l/8}\;\;(\text{using Theorem~\ref{thm:Hoeffding}}) \label{eqn:adv32random32alin} \end{align}\tag{17}\] On the other hand, if \(\mathcal{I}\) is planted, for \((\boldsymbol{0},b)\in\mathcal{I}'\) we have \(b = e\xleftarrow{\text{iid}}\Psi\) such that \(\mathop{\mathrm{\mathbb{E}}}[\chi(e)]=\rho\). \[\begin{align} &\mathop{\mathrm{\mathbb{E}}}[\texttt{adv}] = \frac{1}{m'}\sum\limits_{(\boldsymbol{0},b)\in\mathcal{I}'}\mathop{\mathrm{\mathbb{E}}}\left[\chi(b)\right] = \frac{1}{m'}\sum\limits_{(\boldsymbol{0},b)\in\mathcal{I}'}\mathop{\mathrm{\mathbb{E}}}\left[\chi(e)\right] = \rho \\ \Rightarrow &\Pr\left[\left\lvert \texttt{adv} \right\rvert < \left\lvert \rho \right\rvert/2\right] \leq \Pr\left[\left\lvert \texttt{adv}-\rho \right\rvert > \left\lvert \rho \right\rvert/2\right] < 2e^{-m'\rho^2/8} \leq 2n^{-l/8}\;\;(\text{using Theorem~\ref{thm:Hoeffding}}) \end{align}\] Hence, like the dense minor idea, we can distinguish on the basis of whether \(\left\lvert \texttt{adv} \right\rvert\leq \left\lvert \rho \right\rvert/2\).

We know that the probability of a left-hand side being \(\boldsymbol{0}\) is \(p_0 = \left\lvert R \right\rvert^{-k}\), so a standard application of Chernoff bound (Theorem 4) gives that we need \(m\geq 2\left\lvert R \right\rvert^k\left\lvert \rho \right\rvert^{-2}(l\ln n)\) samples to obtain the required number of \((\boldsymbol{0},b)\) samples (\(m'\geq\left\lvert \rho \right\rvert^{-2}l\ln n\)) with probability at least \(1-n^{-\Omega(l)}\).

Finally, the time complexity of this strategy is \(\widetilde{O}\left(\left\lvert \rho \right\rvert^{-2}\left\lvert R \right\rvert^k\right)\) as all we need to do is collect all samples with left-hand sides \(\boldsymbol{0}\) and compute the sum of the corresponding (real parts of) right-hand sides.

Once again, we can choose the best algorithm depending on whether \(\left\lvert R \right\rvert = \omega(n/l)\) (Theorem 15) or \(\left\lvert R \right\rvert = O(n/l)\) (Theorem 16).

8 Discussion↩︎

8.1 Comparison with [31]↩︎

Independent of our work, Kocurek and Manohar [31] have studied the problem of refuting random and semirandom instances of \({k}-\text{LIN}(R)\)¹⁰. For this task, they define Kikuchi graphs for finite fields and abelian groups that are similar to our construction. Their sample-time tradeoffs are also similar to ours. However, our objective is different from the refutation task; ours is the task of distinguishing a random vs a planted instance. The reason why their methods cannot be extended to our problem is that the statistic they use, the value of an instance (maximum fraction of satisfiable constraints) doesn’t allow us to distinguish the random instance from the planted instance when the noise in the planted distribution is too high. Our distinguishing statistic, the advantage (Definition 6), doesn’t suffer from this problem. As we have seen in Subsection 5.4, the advantage can help us distinguish the two cases for any noise distribution satisfying a mild condition.

Moreover, they construct separate Kikuchi constructions depending on the sparsity \(k\) being even or odd, and also depending on the ring being a field or non-field, with significantly more involved construction in the odd sparsity case.

Our Kikuchi construction is able to mitigate both these issues; it is more amenable to the distinguishing task, and is a unified and simplified construction for all rings \(R\) and both sparsity parities when \(\left\lvert R \right\rvert>2\). Further, we are able to construct a simpler distinguisher which has a significantly lower runtime than that of their simple refutation algorithm when the size of the ring \(R\) is large.

Let us elaborate on these aspects:

8.1.1 Distinguishing random vs planted instances for any planted noise↩︎

In the task of refutation of a \({k}-\text{LIN}(R)\) instance \(\mathcal{I}\), the goal is to output a certificate that a given instance is highly unsatisfiable, meaning no assignment can satisfy more than a certain fraction of the constraints. To solve the task of refuting a random/semirandom \({k}-\text{LIN}(R)\) instance \(\mathcal{I}\), the algorithm of [31] returns a certificate \(\texttt{alg-val}(\mathcal{I})\in[0,1]\) with the following guarantees:

1. \(\texttt{alg-val}(\mathcal{I})\geq\texttt{val}(\mathcal{I})\), where \(\texttt{val}(\mathcal{I})\) is the maximum fraction of satisfied constraints by any assignment.

2. If \(\mathcal{I}\) is random, then \(\texttt{alg-val}(\mathcal{I})\leq \frac{1}{\left\lvert R \right\rvert}+\varepsilon\) for an arbitrary small \(\varepsilon>0\) with high probability, which is close to the expected value \(\left(\mathop{\mathrm{\mathbb{E}}}\left[\texttt{val}(\mathcal{I})\right] = \frac{1}{\left\lvert R \right\rvert}\right)\).

3. The algorithm requires \(m\geq \varepsilon^{-2}O(n)\left((\left\lvert R \right\rvert-1)n/l\right)^{k/2-1}\) samples for the refutation task.

To utilize their algorithm for the distinguishing task, a natural thought is to utilize Item 1 of above for the planted case, hoping that \(\texttt{val}(\mathcal{I})\) will be high for the planted case. However, we elaborate below why this will not hold for noise distributions with low probability (\(\sim 1/q\)) of zero error, and so for those cases we won’t be able to use their construction for the distinguishing task. We also elaborate how our construction mitigates this.

Let us see what the quantity \(\texttt{val}(\mathcal{I})\) looks like if \(\mathcal{I}\) is a planted instance with respect to a secret assignment \(\boldsymbol{s}\in R^n\) and noise distribution \(\Psi\) on \(R\). For any sample \((\boldsymbol{a},b)\in\mathcal{I}\), we have \(b=\langle \boldsymbol{a}, \boldsymbol{s} \rangle+e\) for \(e\xleftarrow{\text{iid}}\Psi\), so the probability that \(\boldsymbol{s}\) satisfies the constraint \((\boldsymbol{a},b)\) is \(\Psi(0)\). This in turn means that the expected number of satisfied constraints by \(\boldsymbol{s}\) is \(\Psi(0)\), and \(\mathop{\mathrm{\mathbb{E}}}[\texttt{val}(\mathcal{I})]\geq\Psi(0)\).

This will actually suffice to solve (distinguish) the sparse LPN problem over the ring \(\mathbb{Z}_q\), as \(\Psi(0) = 1-\mu\) (see Definition 16) which can be assumed to be non-negligibly larger than the expected value in the random case \(1/q\) (say \(\mu\geq\frac{q-1}{q}-\frac{1}{n^d}\) for some constant \(d>0\)). Due to this, the \(\varepsilon\) parameter will contribute a factor of \(n^{2d}\) in the sample complexity cost. Note that this matches our result for sparse LPN (Theorem 13).

For sparse LWE, \(\Psi = \Psi_{\mathbb{Z}_q,r}\) for which \(\Psi_{\mathbb{Z}_q,r}(0) = O(1/r)\) when the width \(r\) is super constant (from Observation 13). For instance, if \(r=q/10\), we must have \[\texttt{alg-val}(\mathcal{I})\leq 1/q+\varepsilon < \Psi(0) = 10/q\;\Rightarrow \varepsilon < 9/q\] In this case, \(\varepsilon\) contributes a factor of \(q^2\) to the sample complexity, making the total contribution of the modulus \(q^{k/2+1}\). In contrast, our result (Theorem 12) has a factor of \(q^{k/2}\) in the sample complexity.

But what if the noise distribution is slightly perturbed, so that the mass at \(0\in\mathbb{Z}_q\) is \(1/q\)? Indeed, we can have a noise \(\Psi'\) resembling the discrete gaussian, except that \(\Psi'(0)=1/q\), and \(\Psi'(j)=\Psi_{\mathbb{Z}_q,r}(j)+\Psi_{\mathbb{Z}_q,r}(0)/(q-1)-1/(q(q-1))\) for \(j\in\mathbb{Z}_q\setminus\{0\}\). In this case, distinguishing on the basis of \(\texttt{val}(\mathcal{I})\) is not possible.

On the other hand, our distinguisher examines a different quantity \(\texttt{adv}(\mathcal{I})\) (recall Definition 6) to separate the random and planted instances. In the random case, this quantity has expectation \(0\). For the planted case we have \(\mathop{\mathrm{\mathbb{E}}}\left[\texttt{adv}(\mathcal{I})\right] \geq \mathop{\mathrm{\mathbb{E}}}\left[\text{adv}_{\mathcal{I}}(\boldsymbol{s})\right] = \mathop{\mathrm{\mathbb{E}}}[\text{Re}\left(\chi(\Psi')\right)] =: \rho'\). To estimate \(\rho'\), firstly note that \(\rho := \mathop{\mathrm{\mathbb{E}}}[\chi(\Psi_{\mathbb{Z}_q,r})] \geq e^{-\pi r^2/q^2} \geq e^{-\pi/4}\) when \(r<q/2\) (Observation 14). Then \[\begin{align} \rho' := \mathop{\mathrm{\mathbb{E}}}[\text{Re}\left(\chi(\Psi')\right)] &= \sum_{j\in\mathbb{Z}_q}e^{2\pi\iota j/q}\Psi'(j)\;\;\;(\text{note that \Psi'(j)=\Psi'(-j)}) \\ &= 1/q + \sum_{j\in\mathbb{Z}_q\setminus\{0\}}e^{2\pi\iota j/q}\left(\Psi_{\mathbb{Z}_q,r}(j)+\Psi_{\mathbb{Z}_q,r}(0)/(q-1)-1/(q(q-1))\right) \\ &= \rho - \left(\Psi_{\mathbb{Z}_q,r}(0)-1/q\right)\left(q/(q-1)\right) \\ &\geq \rho - 2/r\;= \Omega(1) \end{align}\] Hence, in this case, \(\rho'\) is still a constant, and the same sample complexity as for sparse LWE suffices for the distinguishing task. In fact, our method is oblivious to the noise distribution \(\Psi\), as long as it satisfies a mild condition (\(\mathop{\mathrm{\mathbb{E}}}[\text{Re}\left(\chi(\Psi)\right)]\in(0,1]\)).

In Observation 3.6 of [31], Kocurek and Manohar relate the value of the instance with a quadratic form of their Kikuchi construction. One key aspect of their Kikuchi construction (for their case of even \(k\), \(R\) finite field) is that for a constraint \((\boldsymbol{a},b)\in\mathcal{I}\), they consider all edges \((\boldsymbol{u},\boldsymbol{v})\in R^n_l\) such that \(\boldsymbol{v}-\boldsymbol{u} = \beta\boldsymbol{a}\) for all \(\beta\in R\setminus\{0\}\). This is equivalent to adding constraints \((\beta\boldsymbol{a},\beta b)\in\mathcal{I}\) for all \(\beta\in R\setminus\{0\}\) for each original constraints. Informally, equation 18 below captures the contribution of this constraint to the quadratic form for some assignment \(\boldsymbol{x}\in R^n\): \[\begin{align} \sum_{\beta\in R\setminus\{0\}}\chi\left(\beta b-\beta\langle \boldsymbol{a}, \boldsymbol{x} \rangle\right) = \sum_{\beta\in R\setminus\{0\}}\chi\left(\beta\left(b-\langle \boldsymbol{a}, \boldsymbol{x} \rangle\right)\right) = \begin{cases} (\left\lvert R \right\rvert-1)\;\text{ if }b=\langle \boldsymbol{a}, \boldsymbol{x} \rangle \\ -1\text{ if }b\ne\langle \boldsymbol{a}, \boldsymbol{x} \rangle \end{cases} \label{eqn:informal32contri32of32constraint32to32quadtratic32form} \end{align}\tag{18}\]

So the extent of the noise (how far is \(b\) from \(\langle \boldsymbol{a}, \boldsymbol{x} \rangle\)) is not captured in the quadratic form.

On the other hand, we only keep edges of the form \(\boldsymbol{v}-\boldsymbol{u} = \pm\boldsymbol{a}\). By this, we will achieve the appropriate contribution of this constraint in the advantage:

\[\begin{align} \sum_{\beta\in \{\pm1\}}\chi\left(\beta b-\beta\langle \boldsymbol{a}, \boldsymbol{x} \rangle\right) = 2\text{Re}\left(\chi\left(b-\langle \boldsymbol{a}, \boldsymbol{x} \rangle\right)\right) \end{align}\]

We show in Proposition 7 how the quadratic form of our Kikuchi construction relates to our notion of advantage.

8.1.2 A unified construction↩︎

[31] produce separate Kikuchi constructions and analyses depending on the sparsity parameter \(k\) being odd or even, and also depending on the ring \(R\) being a field or \(\mathbb{Z}_{q_1}\times\ldots\times\mathbb{Z}_{q_t}\).

• Given a left-hand side \(\boldsymbol{a}\in R^n_k\), their construction for even \(k\) only considers edges \((\boldsymbol{u},\boldsymbol{v})\in R^n_l\times R^n_l\) wherein the symmetric difference of supports of \(\boldsymbol{u}\) and \(\boldsymbol{v}\) equal to the support of \(\boldsymbol{a}\) (see Remark 19). Such pairs will not exist when \(k\) is odd. So for odd \(k\), they revert to a much more involved setup which includes partitioning \(\mathcal{I}\) into multiple sub-instances, building a Kikuchi graph for each sub-instance (which differs from the even case), and performing a further processing step of deleting edges from high-degree vertices before taking the spectral norm.

  In our construction, we do not restrict our edges to satisfy the above restriction for even \(k\). This means that when \(\left\lvert R \right\rvert>2\), it is possible that for \(\boldsymbol{v}-\boldsymbol{u}=\boldsymbol{a}\), we have \(u_j,v_j,a_j\ne 0\) for some \(j\in[n]\) (condition 2(c) of Construction 20). This also allows valid pairs \((\boldsymbol{u},\boldsymbol{v})\) for \(\boldsymbol{a}\in R^n_k\) when \(k\) is odd and \(\left\lvert R \right\rvert>2\).

• When \(R\) is the abelian group \(G = \mathbb{Z}_{q_1}\times\ldots\times\mathbb{Z}_{q_t}\), they reduce the instance to a quotient group \(G/H\) which is either small, is of prime order (i.e. a field) or does not have small subgroups. This helps them to save a factor of \(\left\lvert R \right\rvert\) in their sample complexity dependence. Here too, their Kikuchi matrix (for even \(k\) too) differs from the field case.

  For reasons stated above, our construction does not consider edges of the form \(\boldsymbol{v}-\boldsymbol{u}=\beta\boldsymbol{a}\) for \(\beta\in R\setminus\{0\}\setminus\{\pm1\}\), which helped them (when \(R\) was a field) save a factor of \(\left\lvert R \right\rvert\) in their sample complexity. Thus using our construction for non-fields as well does not increase dependence on \(\left\lvert R \right\rvert\) in our sample complexity.

We also remark that our analysis works when \(R\) is any ring apart from a finite field or \(\mathbb{Z}_{q_1}\times\ldots\times\mathbb{Z}_{q_t}\), i.e. any arbitrary multiplication operation on the ring is allowed.

8.1.3 Other Differences↩︎

• They use the Trace Moment method to bound the spectral norm of the Kikuchi matrix, as they deal with the semirandom instance, where the left-hand sides are arbitrary. Since we deal with instances where the left-hand sides are also random (in both random and planted instances), we use the Matrix Bernstein inequality whose analysis is simpler.

• They give a simpler algorithm for the refutation task which outperforms the Kikuchi method when \(\left\lvert R \right\rvert\) is large, specifically \(\left\lvert R \right\rvert=\omega(n/l)\). This algorithm takes same time as their Kikuchi method which is \((\left\lvert R \right\rvert n)^{O(l)}\). This algorithm involves checking all assignments in \(R^l\) for each \(\binom{n}{l}\) \(l\)-sized subsets of \([n]\).

  We too give a simple algorithm in the large \(\left\lvert R \right\rvert\) case, which takes time \(\widetilde{O}\left(\rho^{-2}\left(\left(\frac{\alpha n}{l}\right)^{k+1} + \left\lvert R \right\rvert^l\right)\right)\). We are able to achieve this significant advantage in time, as processing a fixed \(l\)-sized subset suffices for the task of distinguishing a random vs planted instance.

8.2 Comparison with [28]↩︎

Jain, Lin and Saha in [28] introduced the sparse LWE problem over the ring \(\mathbb{Z}_p\) for a prime \(p\). There is an ambiguity in their definition, as they mention that each sample has exactly \(k\)-non-zero entries, yet each non-zero entry is sampled uniformly from \(\mathbb{Z}_p\) rather than \(\mathbb{Z}_p^*\). In this work, we have defined and analyzed both versions (\({k}-\text{LIN}(R)\) and \({k}-\text{ALIN}(R)\)).

They attempt to claim hardness of sparse LWE, both by a reduction from standard LWE, and via a conjecture. We now discuss the implications of our algorithms on these hardness assumptions.

8.2.1 On hardness of \(k-\text{ALWE}_{n,m,p,r}\) assuming hardness of LWE↩︎

Over the ring \(R=\mathbb{Z}_p\), they show a reduction from standard LWE over dimension \(k\) to \(k\)-sparse LWE over dimension \(n\geq k\) (Theorem 5.1 of [28]) for the at most \(k\)-non-zero entries version, i.e. \(k-\text{ALWE}_{n,m,p,r}\) as per our notation in Definition 15. The reduction preserves the number of samples \(m\). It is a standard assumption in cryptography that solving standard LWE on dimension \(k\) takes time \(2^{\Omega(k)}\) time given arbitrary many samples (even as many as \(p^{O(k)}\)). Based on this assumption, their result establishes that with these many samples, solving \(k-\text{ALWE}_{n,m,p,r}\) also takes \(2^{\Omega(k)}\) time.

On the other hand, in Section 7 we show that solving \(k-\text{ALWE}_{n,m,p,r}\) is achievable in \(\widetilde{O}\left(p^k\right)\) time given enough (\(m=\widetilde{O}\left(p^k\right)\)) samples. So when the number of samples is large and the modulus \(p\) is small, our result is towards matching the hardness assumption for \(k-\text{ALWE}_{n,m,p,r}\) from their reduction.

8.2.2 On conjectured hardness of \(k-\text{LWE}_{n,m,p,r}\), \(k-\text{ALWE}_{n,m,p,r}\)↩︎

As an interesting case, let us analyze the sample complexity required by our dense minor algorithm (see Theorem 14) if we allow a time of \(2^{\delta n}\) for an arbitrarily small \(\delta>0\). We have roughly \(m\geq \left(\frac{n}{l}\right)^k\) samples required for a time of roughly \((n/l)^k + p^l\). We must have \[\begin{align} &(n/l)^k + p^l \approx 2^{\delta n} \;\;\;\Rightarrow l \approx \frac{\delta n}{\log p} \\ \Rightarrow &m= O\left(\left(\log p\right)^{k}\right) \text{ samples are sufficient} \end{align}\] In particular, if \(k = O(\log n/\log\log p)\) then polynomially many samples suffice. If \(k = O(\log n)\), then we require \((\log p)^{O(\log n)}\) samples which is polynomial for constant modulus \(p\), and slightly more than polynomial for \(p = O\left(\text{exp}(n)\right)\).

Conjecture 7.1 in [28] suggests that \(k-\text{LWE}_{n,m,p,r}\) is as hard as standard LWE over \(\Theta(n)\) dimension, \(\text{poly}(n)\) samples and the same modulus and width parameters, when the sparsity \(k = \Omega(\log n)\) and \(m = \text{poly}(n)\). Assuming hardness of standard LWE, the algorithm from the Kikuchi method nearly closes the gap of this conjecture, either when the sparsity is slightly less, or the polynomial samples requirement is slightly relaxed.

9 Facts on Discrete Gaussian↩︎

Recall the discrete Gaussian distribution \(\Psi_{\mathbb{Z}_q,r}\) on \(R=\mathbb{Z}_q\) with width parameter \(r\) (Definition 12). We will state a couple of facts regarding this distribution which we use.

Recall the Poisson Summation Formula for \(f:\mathbb{R}\to\mathbb{R}\) where \(\hat{f}\) denotes its Fourier transform: \[\sum_{x\in\mathbb{Z}} f(x) = \sum_{y\in\mathbb{Z}} \hat{f}(y)\]

9.1 Estimating \(\Psi_{\mathbb{Z}_q,r}(0)\)↩︎

We have \[\Psi_{\mathbb{Z}_q,r}(0)\;= \frac{\sum\limits_{x\in q\mathbb{Z}}e^{-\pi x^2/r^2}}{\sum\limits_{x\in \mathbb{Z}}e^{-\pi x^2/r^2}}\;= \frac{\sum\limits_{x\in \mathbb{Z}}e^{-\pi (q/r)^2x^2}}{r\sum\limits_{x\in \mathbb{Z}}e^{-\pi r^2x^2}}\] where the last equality holds by applying the Poisson summation formula on the denominator. When \(1<r<q\), both summations in the numerator and denominator can be bounded by constants. Thus \(\Psi_{\mathbb{Z}_q,r}(0) = \Theta(1/r)\).

9.2 Estimating \(\mathop{\mathrm{\mathbb{E}}}[\chi(\Psi_{\mathbb{Z}_q,r})]\)↩︎

For \(e\leftarrow\Psi_{\mathbb{Z}_q,r}\), we then have \(\rho = \mathop{\mathrm{\mathbb{E}}}[\chi(e)]= \mathop{\mathrm{\mathbb{E}}}[\omega_q(e)]\). This means that \(r\in[0,\infty]\) is the (unique) solution to the equation \[\begin{align} \rho &= \mathop{\mathrm{\mathbb{E}}}[\eta_i] = \frac{\sum_{j\in\mathbb{Z}_q}\omega_q^j\sum_{x\in q\mathbb{Z}+j}{e^{-\pi x^2/r^2}}}{\sum_{x\in\mathbb{Z}}{e^{-\pi x^2/r^2}}} \\ &= \frac{\sum_{x\in\mathbb{Z}}{\omega_q^xe^{-\pi x^2/r^2}}}{\sum_{x\in\mathbb{Z}}{e^{-\pi x^2/r^2}}} = \frac{\sum_{x\in\mathbb{Z}}{\cos\left(\frac{2\pi x}{q}\right)e^{-\pi x^2/r^2}}}{\sum_{x\in\mathbb{Z}}{e^{-\pi x^2/r^2}}}\label{rho32equation32for32Gaussian32distribution} \end{align}\tag{19}\]

Let us obtain a lower bound for 19 . For \(g(x) = \cos\left(\frac{2\pi x}{q}\right)e^{-\pi x^2/r^2}\),
\(\hat{g}(y) = \frac{r}{2} \left( e^{-\pi r^2 \left(y - \frac{1}{q}\right)^2} + e^{-\pi r^2 \left(y + \frac{1}{q}\right)^2} \right)\) and for \(h(x) = e^{-\pi x^2/r^2}\), \(\hat{h}(y) = re^{-\pi r^2y^2}\). Using these in 19 , we obtain \[\begin{align} \rho = \frac{\sum_{y\in\mathbb{Z}} \hat{g}(y)}{\sum_{y\in\mathbb{Z}} \hat{h}(y)} = \frac{e^{-\pi r^2/q^2}\sum_{y\in\mathbb{Z}}\cosh{\left(\frac{2\pi r^2 y}{q}\right)}e^{-\pi r^2y^2}}{\sum_{y\in\mathbb{Z}} e^{-\pi r^2 y^2}} \geq e^{-\pi r^2/q^2} \end{align}\]

In our results, we see that the sample complexity required for both distinguishing methods using Kikuchi graphs depends inverse polynomially on \(\rho\). Since the width \(r\) for the LWE distribution is chosen to be less than \(q\), this dependency will only contribute a constant term.

10 A quantum speedup↩︎

Some Notation. \(\boldsymbol{x}^\dagger\) denotes the conjugate transpose of a vector \(\boldsymbol{x}\). \(\ket{\boldsymbol{x}}\) denotes the unit vector in the direction of \(\boldsymbol{x}\) and \(\bra{\boldsymbol{x}} := \ket{\boldsymbol{x}}^\dagger\). For a matrix \(A\), \(\left\lVert A \right\rVert_{\max} := \max_{i,j}\left\lvert A_{ij} \right\rvert\).
In essence, to solve decisional \({k}-\text{LIN}(R)\), the Kikuchi method performs estimation of the spectral norm of a sparse Hermitian matrix in a space of dimension \(N = \binom{n}{l}(\left\lvert R \right\rvert-1)^l\). For any known classical method, such as the power iteration, eigenvalue estimation requires matrix multiplications, so it is unlikely for the time complexity to go below \(\widetilde{\Omega}(N)\). However, with quantum algorithmic techniques, we can do better.

A Hamiltonian \(H\) on \(t\) qubits is a Hermitian matrix of dimension \(2^t\). \(H\) is called \(s\)-sparse if each row and each column of \(H\) has at most \(s\) non zero entries. Throughout the discussion, we shall assume the normalization constraint that \(\|H\|_{\max} \leq 1\). Approximating the spectral norm of a sparse Hamiltonian is well studied in quantum computing. Indeed, for a local Hamiltonian (which is a special case of sparse hamiltonian), this problem is QMA complete. However, if we are provided with a guiding state \(\ket{\gamma}\), i.e. a state that has good overlap with a unit eigenvector \(\ket{v}\) corresponding to the maximum absolute eigenvalue, i.e. \((\braket{\gamma |v})^2\) is large, the problem can be easier. If we are provided with a guiding state having \(1/\texttt{poly}(t)\) overlap with the leading eigenvector, then Gharibian and Le Gall [34] show that the problem is BQP-complete.

Schmidhuber et al. [27] provide a quantum algorithm to solve the Guided Sparse Hamiltonian problem by combining standard quantum algorithmic techniques of Hamiltonian simulation, phase estimation and amplitude estimation. We define the problem and state their result below. For details, the reader may refer to their paper.

10.1 Guided Sparse Hamiltonian Problem↩︎

The input Hamiltonian \(H\) is assumed to be given in the form of quantum oracle access by providing oracles \(O_H\) and \(O_F\). \(O_H\) is called the adjacency matrix oracle, which on input \((i,j)\) (for \(i,j\in[2^t]\)) gives the entry \(H_{ij}\) of \(H\) up to rounding. \(O_F\) is the adjacency list oracle, which on input \((i,r)\) (for \(i\in[2^t], r\in[s]\)) either returns the index of the \(r\)^th non-zero entry in the \(i\)^th row, or indicates that there are less than \(r\) non-zero entries in \(i\)^th row.

The advantage of having oracle access to \(H\) in this manner is that we do not have to store the Hamiltonian \(H\) that may possibly be of large dimension; rather we can access it “on the fly” when required.

For a \({k}-\text{LIN}(R)\) instance \(\mathcal{I}\) of dimension \(n\) and \(m\) samples, the associated Hermitian matrix \(\mathcal{K}_l(\mathcal{I})\) has the following parameters associated with it:

1. \(2^t = N = \binom{n}{l}(q^l\), so \(t = O(l\log n)\)

2. Its sparsity \(s=\Delta = \frac{m\theta^{(n,l,k)}}{\binom{n}{l}(q^l} = O(\log N) = O(l\log n)\) for the separation in spectral norm for random vs planted case (from Propositions 9, 11)

3. \(\lambda > (1+O(1))\rho\Delta\), say \(\lambda = 3/2\rho\Delta\) (lower bound of spectral norm for planted case)

4. \((1-\alpha)\rho\Delta = (1-O(1))\rho\Delta\), say \(\alpha = 1/2\) (upper bound of spectral norm for random case)

Additionally, the oracles \(O_H\) and \(O_F\) can be efficiently computed using Construction 18.

From point 3. of Definition 24, \(\gamma^2\) is the parameter which corresponds to the overlap of the guiding state \(\ket{\Psi}\). If \(\gamma\) is less than inverse polynomial, then from points 1 and 2 of Theorem 17, \(1/\gamma\) is the dominating factor for the time (i.e. gate) complexity.

Note that if \(\ket{\Psi}\) is a random unit vector, then its overlap (with high probability) to the cutoff eigenspace (corr. to \(\Pi_{\geq\lambda}\) that in the worst case is of small dimension) will be inversely proportional to the dimension with high probability, i.e. \[\gamma^2 = \Omega\left( \frac{1}{\binom{n}{l}(\left\lvert R \right\rvert-1)^l} \right)\] in our setting. This already yields a quantum algorithm with complexity \(\frac{\text{poly}(n)}{\gamma} = \text{poly}(n)\cdotp\sqrt{\binom{n}{l}(\left\lvert R \right\rvert-1)^l}\), a (nearly) quadratic speedup over the classical algorithm.

The other key observation of [27] is the ability to prepare a better guiding state, one which has overlap of \(\Omega\left( \frac{1}{\sqrt{\binom{n}{l}(\left\lvert R \right\rvert-1)^l}}\right)\) with the cutoff-eigenspace.

10.2 Intuition for Guiding State↩︎

Again, we give a brief intuition behind the better guiding state; the details of the proofs will be analogous to Appendix C of [27].

Suppose for an instance \(\mathcal{I}= \{(\boldsymbol{a}_i,b_i)\}_{i\in[m]}\) we construct \(l/k\) copies of the following state:

\[\ket{\gamma(\mathcal{I})} := \frac{1}{\sqrt{m}} \sum_i \chi(b_i) \ket{\boldsymbol{a}_i} \in \mathbb{C}^{R^n_k}\]

This state correlates well (better than random) with the planted assignment \(\ket{\boldsymbol{s}} = \frac{1}{\sqrt{n}}\sum_i \chi(s_i)\ket{i}\) :

\[|\braket{\boldsymbol{s}^{\otimes \ell}| \gamma(\mathcal{I})^{\otimes \ell/k}}|^2 = \left( \braket{\boldsymbol{s}^{\otimes k}| \gamma(\mathcal{I})} \right)^{2 \ell / k} \approx \left(\frac{\rho\cdotp m}{n^kq^k}\right)^{\ell / k}\]

If \(m \approx \Theta(((\left\lvert R \right\rvert-1)n)^{k/2})\) then the overlap \(\sim ((\left\lvert R \right\rvert-1)n)^{-l/2}\), which is a quadratic improvement from that of a random guiding state. The actual guiding state is approximately a symmetrized and a normalized version of \(\ket{\gamma(\mathcal{I})}\). Also, the other technical challenge is to show a high overlap with the cutoff eigenspace of \(\mathcal{K}_l(\mathcal{I})\) rather than with \(\boldsymbol{s}\). These issues are handled in detail in Appendix C of [27].

References↩︎

---

1. The Kikuchi method is inspired from Kikuchi free energy, a marginal approximation to Gibbs free energy [26]↩︎

2. although in their Introduction, they mention that an equation has exactly \(k\) non-zero entries↩︎

3. a semirandom instance is when the left-hand sides of a \({k}-\text{LIN}(R)\) instance can be arbitrarily chosen, but the right-hand sides are uniformly and independently chosen↩︎

4. in this equation we use the convention that if \(s\) is not a non-negative integer or \(s>t\), then \(\binom{t}{s}=0\)↩︎

5. if there are parallel edges, we add their signs in the corresponding matrix entry↩︎

6. \(D(\mathcal{K}_l(\mathcal{I}))\) does not depend on \(\{b_i\}_{i}\) as the latter only contribute to signs of the edges↩︎

7. the noise for sparse LWE, sparse LPN and other nice distributions shall satisfy this assumption.↩︎

8. for the refutation task, the latter was required↩︎

9. assuming \(k\ll l\), ignoring \(\rho\) and logarithmic terms for simplicity↩︎

10. a semirandom instance is when the left-hand sides of a \({k}-\text{LIN}(R)\) instance can be arbitrarily chosen, but the right-hand sides are uniformly and independently chosen↩︎