{"id":"d5e3dbd7-221d-480d-86b5-b92d2bc16d5d","arxiv_id":"1908.03724","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"A generalized slide reduction that handles every block size now gives the fastest provable algorithms for δ-approximate SVP in the cryptographic range n^{1/2+ε} ≤ δ ≤ n^{O(1)}.","lead":"This paper removes a divisibility barrier in slide reduction for lattice shortest-vector problems, giving the fastest proven algorithms for the approximation factors used in cryptography. For approximation factors between n^{1/2+ε} and n^{O(1)}, it improves the running-time exponent by a constant factor.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Invalid step in Appendix A proof leaves SVP bound for n≥2k unproven","rationale":"The reader's weakest-assumption is the outsourced DBKZ bound, which is indeed a dependency. However, the most load-bearing concern in the submitted manuscript is internal: the appendix proof of Theorem A.1, used directly in Theorem 4.2 for the n≥2k SVP factor, contains a step that is not justified by the definition of slide reduction. The block B[d+1,d+k+1] is not among the blocks that Definition 4.1 requires to be δ-SVP-reduced, so the sentence 'B[d+1,d+k+1] is δ-SVP reduced' is false as written. This is more than a typographical slip: it is the key step in proving Eq. (9), and Eq. (9) underpins Theorem 1.1's SVP approximation factor in the n≥2k regime. I verified that the surrounding HSVP bound (Eq. (5)) goes through via Lemma 2.2 and Eq. (8), so the issue is specific to the SVP claim. The concern is fixable—a correct case analysis exists—so it does not overturn the reader's CONDITIONAL verdict, but it should be corrected before publication. I therefore keep the verdict unchanged and note partial disagreement with the reader's choice of weakest assumption.","tokens_in":16939,"tokens_out":36824,"duration_ms":315550,"concrete_test":"Re-derive Eq. (9) of Theorem A.1 from Definition 4.1 without the disputed sentence. In the induction step where λ_1(L(B[d+1,n])) = λ_1(L(B[d+1,d+k+1])), split on whether the shortest vector has a nonzero coefficient on b_{d+k+1}: if zero, use δ-SVP-reducedness of B[d+1,d+k]; if nonzero, use Fact 2.1 on the twin block B[d+1,d+k+1] to bound ‖b^*_{d+1}‖ by (δ²γ_k)^{k/(k-1)}λ_1, and check this matches the required exponent k(p-1)/(k-1) for p≥2. If either case fails, Theorem 4.2 Eq. (6) is unproven.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In Theorem 4.2, the SVP bound (Eq. (6)) relies on Theorem A.1's Eq. (9), which states that B[d+1,n] is δ(δ²γ_k)^{(n-d-k)/(k-1)}-SVP-reduced. The proof of Eq. (9) in the appendix contains a false assertion in the induction step's second case: when λ_1(L(B[d+1,n])) = λ_1(L(B[d+1,d+k+1])), it says 'B[d+1,d+k+1] is δ-SVP reduced.' Definition 4.1 guarantees only (i) B[d+1,d+k] is δ-SVP-reduced and (ii) B[d+2,d+k+1] is δ-DSVP-reduced; the size-(k+1) block B[d+1,d+k+1] is not a reduced block in the definition. The variable '‖b_1‖' in the same sentence should read '‖b^*_{d+1}‖', but even with that correction the implication does not follow. A correct case analysis is possible (split on whether the shortest vector's coordinate along b^*_{d+k+1} is nonzero), but the manuscript does not supply it. Without Eq. (9), the n≥2k SVP approximation factor in Theorem 1.1 is unsupported.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper generalizes Gama and Nguyen's slide reduction to all ranks n >= k, removing the requirement that the block size divide the rank. For n >= 2k it claims a reduction from δH-HSVP and δS-SVP on rank n to δ-SVP on rank k with δH = (δ²γ_k)^((n-1)/(2(k-1))) and δS = δ(δ²γ_k)^((n-k)/(k-1)); for k <= n <= 2k it claims δS approximately δ(δ²γ_k)^(n/(2k)). The algorithms use a δ-SVP oracle, and the n >= 2k case invokes the Micciancio-Walter DBKZ algorithm to treat the first block with HSVP reduction. The paper argues that these bounds give the fastest provable running times for δ-approximate SVP in the range n^{1/2+ε} <= δ <= n^{O(1)}, with explicit dependence on the oracle approximation factor δ.","tokens_in":17142,"tokens_out":24712,"duration_ms":205489,"significance":"If the proof gap identified below is repaired, this is a strong contribution. The paper fills a real gap in slide reduction, shows that the DBKZ HSVP bound can be matched by a single algorithm for both HSVP and SVP, and gives concrete improvements to the provable approximation factor for SVP in the polynomial approximation regime. The gluing lemma (Lemma 2.2) and the twin-reduction bound (Fact 2.1) are clean and reusable, and the paper is transparent about its reliance on the DBKZ analysis of Micciancio and Walter and Neumaier. The oracle-accounting in the algorithms is careful, and the claimed running-time improvements are stated with explicit constants. However, the central SVP approximation theorem for n >= 2k is currently not proven as written because of a gap in Appendix A.","major_comments":[{"comment":"The induction step is not justified. The text says that 'B satisfies the requirements of the theorem with d′ := d+k and p′ := p−1,' but Definition 4.1's Mordell condition applies only to the prefix B[1,k+q], not to the larger prefix B[1,d+k]. Neither the whole matrix nor the suffix B[d+k+1,n] satisfies the hypotheses of Theorem A.1 with that parameter shift, so the displayed bounds on ‖b*_{d+k+1}‖ and ‖b_{d+k+1}‖ do not follow from the stated induction. Since these bounds are used in Lemma 2.2 and then in Theorem 4.2, this leaves Eq. (9) and therefore the n >= 2k SVP approximation factor unsupported.","section":"Appendix A, proof of Theorem A.1"},{"comment":"The text asserts that B[d+1,d+k+1] is δ-SVP-reduced when λ1(L(B[d+1,n])) = λ1(L(B[d+1,d+k+1])). This block is not one of the reduced blocks in Definition 4.1; only B[d+1,d+k] is δ-SVP-reduced and B[d+2,d+k+1] is δ-DSVP-reduced. The displayed '‖b1‖' in that sentence should also be '‖b_{d+1}‖' when working inside the suffix. The case therefore requires an actual argument, for example splitting on whether a shortest vector has a nonzero component along b*_{d+k+1}, but the manuscript does not supply one. This is load-bearing because Eq. (9) is used in Theorem 4.2 Eq. (6) and in Corollary 4.4.","section":"Appendix A, proof of Eq. (9), second case"}],"minor_comments":[{"comment":"In the chain bounding vol(B[1,k]), the factor ‖b*_q‖^q should be ‖b*_{q+1}‖^q when applying Eq. (4) of Fact 2.1 to the twin-reduced block B[1,q+1]; with that correction the displayed inequality and the final bound are consistent.","section":"Theorem 3.2, proof"},{"comment":"The notation in the exponent (n−k)/2 is correct but would be clearer as q/2, since n−k=q in this section; as written the reader must perform that substitution to verify the final exponent.","section":"Theorem 3.2, proof"},{"comment":"The second induction bound for ‖b_{d+k+1}‖ contains the expression n−3k−ℓ, where ℓ is not defined and the exponent appears to be a typo for the correct n−d−2k (equivalently, the corresponding expression in p).","section":"Appendix A, proof of Theorem A.1"},{"comment":"The variable p is overloaded: Definition 4.1 writes n = pk+q, while Theorem A.1 writes n = pk+d with d = k+q, so the suffix rank is (p−1)k in one notation and pk in the other. The relation between the two notations should be stated explicitly to avoid confusion.","section":"Theorem A.1 / Definition 4.1"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is a strong candidate for publication if the authors can repair the proof of Theorem A.1; the gap appears local and fillable rather than fatal. I would ask the authors to provide the missing case analysis for Eq. (9) and to clarify the induction step. The paper also depends heavily on the DBKZ analysis in [MW16, Neu17]; the authors are transparent about this, but the final constants are inherited from that external proof."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Read this one. It gives the best proven running times for δ-SVP across the cryptographic range, and the n≤2k algorithm is a genuinely new idea. But before you trust Theorem 1.1, know that Appendix A has a localized bug in the proof of the tail SVP bound (Eq. 9). It's fixable, but it needs to be fixed.\n\nWhat's new: previous slide reduction required k | n, and the padding cost changed the exponent of the approximation factor. The n≥2k generalization removes that by HSVP-reducing a larger first block, matching DBKZ's HSVP factor. The n≤2k case is the more interesting part: slide reduction with unequal blocks, then a volume argument shows a rank-k prefix has small determinant, and one more oracle call finds a short vector. That is a real contribution, and the proof structure around Fact 2.1 and Lemma 2.2 is clean. The explicit dependence on δ for the SVP oracle is useful, and the paper is honest about relying on the DBKZ/Neumaier result as a dependency.\n\nWhere I'd push back: the stress-test is right. In Theorem A.1's induction, the second case says B[d+1,d+k+1] is δ-SVP-reduced when Definition 4.1 only guarantees B[d+1,d+k] SVP-reduced and B[d+2,d+k+1] DSVP-reduced. The size-(k+1) block is not a reduced block, and the sentence's \"b1\" should be \"b*_{d+1}\". The fix is simple: split on whether the shortest vector of the tail lies in B[d+1,d+k]. If it does, that block's SVP-reduction gives the bound directly; if not, Lemma 2.2 with tail B[d+k+1,n] applies. So Eq. (9) is unproven as written, but the gap is local and the main theorem can survive it.\n\nOther soft spots are minor. Theorem 3.2 has a couple of typos in the proof (wrong Gram-Schmidt index, a missing factor), and \"fastest\" should be \"best known\" absent a lower bound. The outsourced DBKZ proof is acceptable, but should be flagged explicitly as an external dependency. The citation pattern is appropriate; the self-citations to GN08 and MW16 are standard and not a problem.\n\nBottom line: this is a serious paper with real results for lattice cryptography and algorithms. If I were the editor, I'd send it out. The referee should ask for the appendix fix and the typo cleanup; I'd expect the corrected version to be correct. Worth bringing to reading group.","headline":"Real results with a localized, fixable gap in Appendix A; worth refereeing and likely correct after correction.","tokens_in":17807,"tokens_out":12479,"would_cite":true,"duration_ms":111764,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q17","68W25","11H06","94A60"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper removes the divisibility barrier in slide reduction and proves the fastest provable algorithms for approximate SVP across the cryptography-relevant range $\\delta \\in [n^{1/2+\\varepsilon}, n^{O(1)}]$.","keywords":["lattice basis reduction","shortest vector problem","slide reduction","Hermite SVP","DBKZ algorithm","approximation algorithms","post-quantum cryptography"],"falsifier":"Run the DBKZ algorithm on a rank $2k$ lattice for a representative $k$ (for example, random $q$-ary lattices at cryptographic dimensions) with a $\\delta$-SVP oracle and measure the ratio $\\|b_1\\|/\\mathrm{vol}(L)^{1/n}$. If any input family makes this ratio exceed $(1+\\varepsilon)(\\delta^2\\gamma_k)^{(2k-1)/(2(k-1))}$ by a constant factor, the convergence claim behind Theorem 2.3 is false and the central reduction's approximation factors collapse.","tokens_in":16686,"feed_emoji":"🧮","tokens_out":11038,"duration_ms":94131,"temperature":0.7,"pith_summary":"This paper shows that Gama and Nguyen's slide reduction can be extended to every block size $k \\ge 2$, removing the old requirement that $k$ divide the lattice rank $n$. The authors prove efficient reductions from approximate Shortest Vector Problem (SVP) on rank-$n$ lattices to $\\delta$-SVP on rank-$k$ lattices, for every $n \\ge 2k$ and for $k \\le n \\le 2k$, with the target approximation factors given in Theorems 1.1 and 1.2. These factors match the best known Hermite-SVP bound and, combined with known subexponential SVP solvers, yield the fastest provable running times for $\\delta$-SVP for every approximation factor $n^{1/2+\\varepsilon} \\le \\delta \\le n^{O(1)}$. This matters because this is the approximation range on which lattice-based cryptography's security estimates rest.","feed_headline":"Divisibility barrier falls for slide reduction, speeding up SVP","feed_subtitle":"Generalized slide reduction gives the fastest provable SVP algorithms in the range used by lattice cryptography.","key_machinery":"The central object is the slide-reduced basis: a size-reduced basis whose primal blocks $B[ik+q+1,(i+1)k+q]$ are $\\delta$-SVP-reduced and whose shifted dual blocks are $\\delta$-DSVP-reduced (dual reduction means the reversed dual basis is SVP-reduced after LLL), with the first block replaced by an $\\eta$-HSVP-reduced block of size $k+q$ for $\\eta = (\\delta^2\\gamma_k)^{\\frac{k+q-1}{2(k-1)}}$. The proof is carried by the gluing lemma, which shows how two reduced blocks with controlled decay of Gram-Schmidt vectors combine into a larger reduced block; together with the twin-reduction inequality $\\|b_1\\| \\le \\delta^{2d/(d-1)}\\|b^*_{d+1}\\|$, it turns the local reduction conditions into the global approximation factor. The big first block is Hermite-SVP-reduced by the DBKZ algorithm, which supplies exactly the needed bound, and the potential $\\mathrm{vol}(B[1,ik+q])^2$ bounds the number of iterations polynomially.","core_discovery":"The central discovery is that a slide-reduced basis does not require every primal block to be SVP-reduced; the first block can be replaced by a Hermite-SVP-reduced block of size $k+q$, and the gluing analysis still delivers the full approximation factor $\\delta(\\delta^2\\gamma_k)^{(n-k)/(k-1)}$ for SVP when $n \\ge 2k$, and $\\delta\\sqrt{\\gamma_k}(\\delta^2\\gamma_q)^{\\frac{q+1}{q-1}\\cdot\\frac{n-k}{2k}}$ for $n = k+q \\le 2k$. This removes the rounding penalty $\\lceil n \\rceil_k/k$ that forced earlier slide reduction to lose a constant in the exponent whenever $k$ did not divide $n$. For $n \\le 2k$, the extra oracle call on the extended block $B[1,k]$, whose volume is bounded through the slide-reduced structure, yields sublinear approximation factors in a regime where no provable sublinear algorithm was previously known. The result matches the DBKZ approximation factor for Hermite-SVP, so one algorithm now attains the best proven bound for both problems.","pith_inferences":["Because the SVP approximation factor for $n \\ge 2k$ is governed by $(\\delta^2\\gamma_k)^{(n-k)/(k-1)}$, further progress on Hermite-SVP algorithms such as DBKZ would translate directly into faster SVP reductions; this paper effectively identifies Hermite-SVP, not SVP, as the bottleneck for this regime.","The $n \\le 2k$ construction's extra oracle call on $B[1,k]$ suggests that other volume information inside a slide-reduced basis, not just the first vector, could be exploited to find still shorter vectors within the same oracle model.","Removing the divisibility barrier implies that lattice-cryptography parameter sets no longer need to pad the rank to a multiple of $k$; concrete security evaluations for schemes such as LWE and NTRU could shift if these reductions are instantiated with practical heuristic block reduction."],"forward_implications":["For every $n \\ge 2k$, there is an efficient reduction from $\\delta(\\delta^2\\gamma_k)^{(n-k)/(k-1)}$-SVP on rank-$n$ lattices to $\\delta$-SVP on rank-$k$ lattices, matching the best known Hermite-SVP factor and removing the rounding loss that Gama-Nguyen slide reduction incurred when $k$ does not divide $n$.","For $k \\le n \\le 2k$, the reduction achieves a factor of about $\\delta(\\delta^2\\gamma_k)^{n/(2k)}$, giving provable sublinear approximation factors in a range where no provable sublinear SVP algorithm was previously known.","Combined with the $2^{0.802k}$-time approximate SVP oracle of Wei, Liu, and Wang, the reductions give running time $2^{0.802n/(c+1)}$ for $\\delta = n^c$ with $c \\ge 1$, and $2^{0.802n/(2c)}$ for $1/2 < c < 1$; the paper states these are the fastest provable running times for $\\delta \\in [n^{1/2+\\varepsilon}, n^{O(1)}]$.","For approximation factors $n^c$ with $c$ slightly smaller than an integer, the exponent improves from $\\lceil c+1 \\rceil$ to $c+1$, removing a constant-factor gap that directly affected cryptographic security estimates."],"supporting_citations":[{"why":"Original slide reduction framework whose primal/dual block conditions, twin-reduction inequality, and potential argument are generalized here.","marker":"[GN08]"},{"why":"DBKZ algorithm used as the Hermite-SVP oracle for the big first block; supplies the approximation factor and convergence analysis the reductions rely on.","marker":"[MW16]"},{"why":"Original proof of the convergence claim inside the DBKZ analysis, which the paper outsources as the key technical step.","marker":"[Neu17]"},{"why":"LLL reduction underlies size-reduction, DSVP reduction existence, and the polynomial bounds on intermediate basis vectors.","marker":"[LLL82]"},{"why":"Subexponential-time $\\delta$-SVP algorithm used to instantiate the oracle and to obtain the running-time improvements in Table 1.","marker":"[WLW15]"},{"why":"Fastest exact SVP algorithm, serving as the baseline that the new reductions improve upon for near-exact approximation factors.","marker":"[ADRS15]"},{"why":"Justifies that repeated block reductions keep intermediate matrix entries polynomially bounded, supporting the efficiency claims.","marker":"[LN14]"}],"fun_headline_variants":["Slide reduction reworked: fastest provable SVP for all crypto ranges","Gap-free slide reduction: new fastest SVP algorithm","Slide reduction generalized: no more rounding penalty","SVP speedup: slide reduction without the divisibility barrier","Provably faster SVP: slide reduction's missing pieces found"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the DBKZ algorithm provably achieves the Hermite-SVP bound $\\|b_1\\| \\le (1+\\varepsilon)(\\delta^2\\gamma_k)^{(n-1)/(2(k-1))}\\mathrm{vol}(L)^{1/n}$ on blocks of rank $k+q$ when given only a $\\delta$-SVP oracle for rank $k$; the paper's advertised SVP approximation factors are directly proportional to this bound.","fun_headline_variants_meta":{"raw":{"variants":["Slide reduction reworked: fastest provable SVP for all crypto ranges","Gap-free slide reduction: new fastest SVP algorithm","Slide reduction generalized: no more rounding penalty","SVP speedup: slide reduction without the divisibility barrier","Provably faster SVP: slide reduction's missing pieces found"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00053,"raw_usage":{"total_tokens":2506,"prompt_tokens":852,"completion_tokens":1654,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":468,"completion_tokens_details":{"reasoning_tokens":1571}},"tokens_in":468,"tokens_out":1654,"duration_ms":13499,"temperature":1.0,"reasoning_tokens":1571,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T14:05:17.783944+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the DBKZ algorithm on a rank $2k$ lattice for a representative $k$ (for example, random $q$-ary lattices at cryptographic dimensions) with a $\\delta$-SVP oracle and measure the ratio $\\|b_1\\|/\\mathrm{vol}(L)^{1/n}$. If any input family makes this ratio exceed $(1+\\varepsilon)(\\delta^2\\gamma_k)^{(2k-1)/(2(k-1))}$ by a constant factor, the convergence claim behind Theorem 2.3 is false and the central reduction's approximation factors collapse.","supporting_citations":[],"review_version":1}