{"id":"c203af64-26ef-4f65-8e0c-5febd490f0a6","arxiv_id":"2411.12512","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"A new reduction shows k-sparse LWE and LPN in dimension n inherit nearly the full hardness of dense LWE and LPN in a much smaller dimension.","lead":"This paper proves that solving noisy linear equations with sparse random coefficients is essentially as hard as solving the standard dense versions, up to near-optimal slack. The result transfers exponential-time hardness from dense LWE and LPN to sparse variants, and yields the first tensor-completion lower bound from worst-case lattice assumptions.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 2.1 is false: Algorithm 2 does not sample uniformly from Preimage_G(F), so the reduction's distributional correctness (Theorem 4.2) fails.","rationale":"The reader's weakest_assumption was Lemma 2.2 (uniformity of preimage size), which is a separate and, as far as the proof goes, correct statement. The actual load-bearing flaw is in Lemma 2.1, the preimage sampling lemma. The proof of Lemma 2.1 conflates injectivity of the random path for each output with equal probabilities; the algorithm's case-dependent sampling sets have different sizes, producing non-uniform outputs. The explicit counterexample with h=2, q=2, k=5, F=(1,1) shows two valid preimage elements with the same multiset of rows receiving different probabilities. Since Algorithm 5's distributional correctness (Theorem 4.2) depends directly on this lemma, the main reduction is not proven. A correct reduction might exist with a different sampling procedure, but as written the paper's central claim is unsupported. Hence the verdict should move from ACCEPT to REJECT.","tokens_in":99730,"tokens_out":27463,"duration_ms":244128,"concrete_test":"Implement Algorithm 2 exactly as specified for h=2, q=2, k=5, F=(1,1), with row indices Z1=1, Z2=2, X=3, Y=4. Enumerate all possible random paths and compute the probability of each output tuple, or sample 10^6 times and compare empirical frequencies. The tuples O1=(3,1,4,2,1) and O3=(1,2,3,4,1) should be equally likely if the sampler were uniform, but they will differ by a factor of 4/3 (1/512 vs 1/384). Confirming this disproves Lemma 2.1 and shows the distributional guarantee of the reduction is invalid.","verdict_should_be":"REJECT","load_bearing_attack":"The central reduction relies on Lemma 2.1, which claims Algorithm 2 outputs a uniformly random element of Preimage_G(F). The proof (Claim 5.2) only establishes that each output corresponds to a unique realization of the algorithm's randomness; it does not show all realizations have equal probability. In Algorithm 2, case 2 samples uniformly from an allowed set of size h + |S_t|(q-1), while case 3 samples uniformly from size hq; these sizes differ, so different paths have different probabilities. Concretely, take h=2, q=2, k=5, F=(1,1). Let Z1,Z2 denote the two zero rows, X=(1,0), Y=(0,1). The tuple O1=(X,Z1,Y,Z2,Z1) is output with probability (1/4)^4 * (1/2) = 1/512, while O3=(Z1,Z2,X,Y,Z1), a permutation of the same multiset, is output with probability (1/4)^3 * (1/3) * (1/2) = 1/384. Both are in Preimage_G(F); a uniform sampler must give them equal probability. Hence Lemma 2.1 is false. Lemma 5.8 uses Algorithm 2 for uniform word decoding, and Algorithm 5 builds on that to produce uniformly random k-sparse rows. Without uniform preimage sampling, the output distribution is not randomsupport(n,k,D), so Theorem 4.2 and the main reduction (Theorem 1.1) are unsupported.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper presents a polynomial-time reduction from standard dense noisy linear equations over Z/qZ in dimension ℓ = k log n / poly(log k, log q, log log n) to k-sparse noisy linear equations in dimension n, with the number of samples preserved up to a 1-o(1) factor and the noise distribution preserved. From this it derives near-optimal hardness lower bounds for k-sparse LPN and k-sparse LWE under standard dense hardness assumptions, and it gives a reduction from k-sparse LWE to noisy tensor completion. The proof is built around a gadget matrix and a word/sentence decoding procedure, with Lemmas 2.1–2.3 as the key sampling primitives.","tokens_in":100009,"tokens_out":8870,"duration_ms":84984,"significance":"If correct, this would be a significant and clean result: it nearly closes the gap between dense and sparse noisy linear equations, transfers hardness to applications in learning theory and cryptography, and gives the first hardness evidence for noisy tensor completion based on worst-case lattice assumptions. The paper is constructive, with explicit algorithms and detailed parameter instantiations, and it is unusually versatile (decision/search/refutation, arbitrary support distributions, variable support sizes). The main caveat is that the distributional core of the proof currently rests on a false lemma.","major_comments":[{"comment":"Lemma 2.1 is false as stated. Algorithm 2 samples from sets of different sizes in cases 2 and 3, so different preimage tuples receive different probabilities. Claim 5.2 only proves that each output corresponds to a unique random tape, not that the corresponding random outcomes are equally likely. Concretely, take h=2, q=2, k=5, and F=(1,1). The rows of G are the zero rows 1,2, the row (1,0) at index 3, and the row (0,1) at index 4. The tuples (3,1,4,2,1) and (1,2,3,4,1) are both in Preimage_G(F), but the algorithm outputs the first with probability (1/4)^4·(1/2) = 1/512 and the second with probability (1/4)^3·(1/3)·(1/2) = 1/384. Since both are valid preimages, the output distribution of Algorithm 2 is not uniform.","section":"§5.2, Lemma 5.8 and Theorem 4.2"},{"comment":"Because Algorithm 2 is not a uniform preimage sampler, Lemma 5.8(2) and the distributional statement of Theorem 4.2(2) do not follow. In the proof of Lemma 5.8, the factor 1/|Preimage_G(F)| is cancelled after conditioning on F; this step is valid only if Algorithm 2 samples uniformly from the preimage, which the counterexample above disproves. Consequently the output of Algorithm 5 is not shown to be distributed as randomsupport(n,k,D), and the main reduction (Theorem 4.1 and Corollaries 5.13–5.15) currently lacks a valid distributional analysis. The authors would need to replace Algorithm 2 with a genuinely uniform preimage sampler and re-prove Lemma 5.8.","section":"§5.2, Lemma 5.8 and Theorem 4.2"}],"minor_comments":[{"comment":"The distribution randomsupport(n,k,D) is used in Section 1 but only defined in Section 3.1; please move the definition earlier or add a forward reference at first use.","section":"§3.1"},{"comment":"The phrase 'indexing one of the zero rows' is ambiguous when q>2, since every block b=0 gives h zero rows; a short comment explaining the index convention (index = b·h + j) would make the algorithm easier to read.","section":"§5.1.1, Algorithm 2"},{"comment":"The folklore decision algorithm states a runtime of roughly 2^{O(sqrt(q)·(q n)^{k/2})}, but the exact dependence on q through the number of groups is not made explicit; please state the constant/exponent precisely.","section":"§4.3"}],"recommendation":"major_revision","confidential_remarks":"The flaw in Lemma 2.1 is load-bearing, but I believe it is likely repairable by replacing Algorithm 2 with a sequential DP-based conditional sampler that is genuinely uniform; however, the current version cannot be accepted. I did not find additional independent issues in the random-walk uniformity proof of Lemma 2.2, but I did not verify every estimate in Sections 5.4–7."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is an important paper with a broken central lemma. The dense-to-sparse reduction for LWE/LPN is exactly the kind of result the community wants, and the tensor completion application is a genuine new consequence. But the proof of Lemma 2.1 does not survive contact with a concrete example, and everything downstream of it (Theorem 4.2, and hence the main theorem) is unsupported as written.\n\nThe word/sentence decomposition is clever, and the pointwise random-walk bound in Lemma 5.6 is plausibly the right technique for the preimage-size uniformity. The paper is honest about what it proves, and the parameter choices are careful. Credit where due: if the sampling lemma were true, the trade-offs would be near-optimal and the applications to DNF learning and homomorphic encryption would follow cleanly.\n\nThe problem: Algorithm 2 does not sample uniformly from Preimage_G(F). Claim 5.2 only establishes that each output corresponds to a unique realization of the algorithm's randomness; it never shows all realizations have equal probability. They do not. In Algorithm 2, case 2 samples uniformly from a set of size h + |S_t|(q-1), while case 3 samples from hq; these differ, so different paths receive different weights.\n\nConcretely, take h=2, q=2, k=5, F=(1,1). Let Z1,Z2 be the zero rows and X=(1,0), Y=(0,1). Then O1=(X,Z1,Y,Z2,Z1) is output with probability (1/4)^4*(1/2) = 1/512, while O3=(Z1,Z2,X,Y,Z1), a permutation of the same multiset, is output with probability (1/4)^3*(1/3)*(1/2) = 1/384. Both lie in Preimage_G(F), so a uniform sampler must give equal probabilities. It does not.\n\nThis is not a cosmetic gap. Algorithm 4 relies on Lemma 2.1 for its \"uniform output\" claim, and Algorithm 5 builds on that to produce randomsupport(n,k,D). Without uniform preimage sampling, the sparse instances produced by the reduction are not distributed as the standard sparse LWE/LPN distribution, so the decision/search/refutation reductions do not map one distribution to the other. Theorem 4.2 and the main theorem are therefore unsupported.\n\nIs this repairable? Possibly. One could replace the ad-hoc sampler with a proper conditional sampler using the DP of Algorithm 3, or add a rejection step that reweights by the path probability. But as submitted, the paper needs real work, not copy-editing.\n\nBottom line: the paper deserves a serious referee because the high-level idea and the application are valuable, and the flaw might be fixable, but I would not accept it in this form.","headline":"The paper's main reduction hangs on a false uniformity lemma; the idea is fresh and the application is real, but the core distributional claim does not hold as written.","tokens_in":100563,"tokens_out":6431,"would_cite":false,"duration_ms":56964,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q17","68Q25","94A60"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper presents a polynomial-time reduction that transfers dense LPN/LWE hardness to k-sparse noisy linear equations, preserving sample count up to a 1-o(1) factor and yielding sparse lower bounds that nearly match the trivial…","keywords":["noisy linear equations","learning parity with noise","learning with errors","sparse linear equations","average-case hardness","tensor completion","gadget matrix","random walk mixing"],"falsifier":"Run the paper's dynamic program for the binary word gadget at small parameters, say $h=10$, $q=2$, $k=60$, and compare $|\\mathrm{Preimage}(0)|$ with $|\\mathrm{Preimage}(e_1)|$; if the ratio falls outside the promised $1\\pm\\eta$ interval, the uniformity lemma that carries the reduction is false.","tokens_in":99506,"feed_emoji":"🔐","tokens_out":12226,"duration_ms":106627,"temperature":0.7,"pith_summary":"The paper tries to establish that hardness of the standard, dense versions of LPN and LWE transfers to their $k$-sparse variants with almost no loss, closing a gap that has stood since sparse LPN was introduced. The main reduction maps a dense equation in dimension $\\ell = k\\log n/\\mathsf{poly}(\\log k,\\log q,\\log\\log n)$ to a uniformly random $k$-sparse equation in dimension $n$, preserving the number of samples up to a $1-o(1)$ factor and the noise distribution. Assuming dense LWE takes $2^{\\Omega(\\ell)}$ time, $k$-sparse LWE takes $n^{\\Omega(k/(\\log k(\\log k+\\log\\log n)))}$ time; assuming dense LPN takes $2^{\\Omega(\\ell/\\log\\ell)}$ time, $k$-sparse LPN takes $n^{\\Omega(k/(\\log k(\\log k+\\log\\log n)^2))}$ time. Both exponents nearly match the brute-force $n^{O(k)}$ algorithms. A corollary gives the first worst-case-lattice-based lower bound for noisy tensor completion, via a direct map from sparse LWE samples to random entries of a noisy low-rank tensor.","feed_headline":"k-sparse LWE inherits dense LWE hardness almost for free","feed_subtitle":"A polynomial-time reduction preserves sample count and noise, so standard LPN/LWE conjectures give near-tight sparse lower bounds.","key_machinery":"The load-bearing object is the word gadget $G$, whose rows are all vectors $c\\,e_i$ for $i\\in[h]$ and $c\\in\\mathbb{Z}/q\\mathbb{Z}$, and the sentence gadget $A$ whose rows are all $s$-long concatenations of rows of $G$. A dense vector is split into $s$ words; each word is decoded by sampling uniformly from its preimage under $G$ (a $k$-tuple of rows summing to the word), and the $k$ columns of the resulting $s\\times k$ array become the support positions of a $k$-sparse row. Three primitives make this exact: efficient uniform preimage sampling, dynamic-programming computation of preimage sizes, and a pointwise random-walk bound showing all words have nearly equal preimage counts once $k\\ge 4h(\\log h+\\log q+\\log(1/\\eta))$. The near-equal preimage counts are what guarantee decoded rows are distributed as uniformly random $k$-sparse rows, and full rank of $A$ is what lets the search reduction recover the original secret.","core_discovery":"On the paper's own terms, the central claim is a reduction: any solver for $k$-sparse noisy linear equations over $\\mathbb{Z}/q\\mathbb{Z}$ in dimension $n$ yields a solver for the standard dense problem in dimension $\\ell = k\\log n/\\mathsf{poly}(\\log q,\\log k,\\log\\log n)$, with the number of samples shrunk only by a $1-o(1)$ factor and the error distribution untouched. The reduction works for decision, search, and strong refutation, for any distribution on the support values, and for moduli from $q=2$ (LPN) up to super-polynomial size. Under the standard conjectures that dense LWE takes $2^{\\Omega(\\ell)}$ and dense LPN takes $2^{\\Omega(\\ell/\\log\\ell)}$, the derived sparse lower bounds are within logarithmic factors of the trivial $n^{O(k)}$ algorithms. In the tensor-completion application, composing the reduction with a sparse-LWE-to-tensor map gives a lower bound for order-$k$, rank-$2^{k-1}$ noisy tensor completion from worst-case lattice hardness.","pith_inferences":["Going beyond the paper, the entropy calculation suggests per-equation gadget decoding has a ceiling of $\\ell\\le k\\log n$; reaching a full $n^{\\Omega(k)}$ bound would likely require coordinating the decoding across all samples rather than decoding each equation separately.","In the few-sample regime (below roughly $n^{k/2}$ samples), this reduction still applies, but matching the known refutation algorithms and proof-system lower bounds would need a noise-aware variant that the paper does not construct.","The tensor-completion construction ties the relative noise level to the expected circular distance of the LWE error, so varying the modulus and error distribution should trade tensor rank against tolerable noise—a curve the paper states only implicitly."],"forward_implications":["If dense LWE is exponentially hard, $k$-sparse LWE in dimension $n$ requires $n^{\\Omega(k/(\\log k(\\log k+\\log\\log n)))}$ time for decision, search, and strong refutation; the analogous LPN bound is $n^{\\Omega(k/(\\log k(\\log k+\\log\\log n)^2))}$ under $2^{\\Omega(\\ell/\\log\\ell)}$ dense hardness.","The reduction keeps all but a $1-o(1)$ fraction of samples and leaves the noise distribution unchanged, so the lower bounds hold even when the attacker has arbitrarily many samples, and they extend verbatim to learning with rounding.","Hardness transfers for every support-value distribution and for varying support sizes, so the results cover both standard $k$-LPN and the binary $k$-LWE variant used in the tensor-completion reduction.","Composing with the paper's sparse-LWE-to-tensor map yields a worst-case lattice lower bound for noisy tensor completion: order-$k$, rank-$2^{k-1}$ completion requires $n^{\\Omega(k/(\\log k(\\log k+\\log\\log n)))}$ time under exponential worst-case lattice hardness.","Applications previously based on $k$-sparse LPN, including DNF learning, agnostic halfspace learning, and linear-stretch pseudorandom generators, can be re-derived from standard dense LPN assumptions."],"supporting_citations":[{"why":"The prior gadget-matrix reduction from dense to sparse LWE; its entropy and modulus limitations define the gap this paper closes.","marker":"[JLS24]"},{"why":"Sets the dense-LPN baseline algorithm whose conjectured $2^{\\Omega(\\ell/\\log\\ell)}$ hardness drives the sparse LPN corollary and whose exponent controls the trade-off.","marker":"[BKW03]"},{"why":"Supplies the worst-case lattice-to-LWE reduction that the tensor-completion corollary composes with.","marker":"[Reg09]"},{"why":"Provides the noisy tensor-completion algorithm and the k-XOR-to-tensor perspective that the tensor lower bound targets.","marker":"[BM16]"},{"why":"Gives sub-exponential refutation algorithms for random k-XOR with few samples, used as the comparison for the reduction's claimed tightness.","marker":"[RRS17]"},{"why":"Lower bounds against a natural class of proof systems for refuting sparse LPN, cited as evidence that the low-sample regime may require different techniques.","marker":"[KMO+17]"}],"fun_headline_variants":["Sparse LWE hardness almost free from dense case","Reduction shows sparse LWE matches dense LWE hardness","Near-tight sparse LWE lower bounds from dense conjecture","Sparse LPN and LWE hardness nearly tight via reduction"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The reduction outputs truly uniform random $k$-sparse rows only if every possible word has nearly the same number of $k$-tuples that decode to it, a property the paper proves with a pointwise random-walk bound; if the true pointwise mixing time were $O(h^2)$ rather than $O(h\\log h)$, the achievable dense dimension would shrink and the near-optimal trade-off would collapse.","fun_headline_variants_meta":{"raw":{"variants":["Sparse LWE hardness almost free from dense case","Reduction shows sparse LWE matches dense LWE hardness","Near-tight sparse LWE lower bounds from dense conjecture","Sparse LPN and LWE hardness nearly tight via reduction"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000655,"raw_usage":{"total_tokens":3094,"prompt_tokens":1132,"completion_tokens":1962,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":748,"completion_tokens_details":{"reasoning_tokens":1904}},"tokens_in":748,"tokens_out":1962,"duration_ms":12628,"temperature":1.0,"reasoning_tokens":1904,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T17:27:32.120892+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the paper's dynamic program for the binary word gadget at small parameters, say $h=10$, $q=2$, $k=60$, and compare $|\\mathrm{Preimage}(0)|$ with $|\\mathrm{Preimage}(e_1)|$; if the ratio falls outside the promised $1\\pm\\eta$ interval, the uniformity lemma that carries the reduction is false.","supporting_citations":[],"review_version":1}