{"id":"ec49d6b8-a7ba-41ef-8452-de97bd2c68db","arxiv_id":"2506.23438","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":1.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"A survey that frames the security of lattice-based post-quantum cryptography as classical geometry-of-numbers problems: SVP/CVP, ball packing and covering, and quadratic forms.","lead":"This paper surveys the mathematical problems behind lattice-based post-quantum cryptography, linking shortest and closest vector problems to ball packing, ball covering, and quadratic forms. It is a map for mathematicians who want to enter a field where NIST is standardizing cryptography that must resist quantum computers.","discovery_kind":"review","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The cryptographic hook depends on an unstated transfer from worst-case general SVP/CVP to structured average-case instances; the packing and quadratic-form problems are never actually connected to any deployed scheme.","rationale":"The reader's weakest assumption and my identified concern align: the paper moves from general worst-case SVP/CVP to structured average-case instances without justification. I agree with the reader's conditional verdict. The paper is useful as a survey of classical lattice geometry, and its mathematical equivalences are largely correct, so a rejection would be too harsh. However, the abstract and introduction make a strong claim about post-quantum cryptography that the body does not substantiate. The concrete test I propose would force the paper's authors or a reader to make the reduction explicit; if it cannot be made explicit, the paper's stated purpose—showing mathematicians that they are 'in the game'—needs to be reframed as contributing to the classical theory of lattices rather than to the security of the standardized cryptographic schemes. The historical error about the date of Ajtai's SIS is a secondary factual issue and should be corrected, but it is not the load-bearing problem.","tokens_in":11352,"tokens_out":4058,"duration_ms":46243,"concrete_test":"Write down the explicit chain: Module-LWE (or NTRU) → average-case SVP/CVP → worst-case SVP/CVP → the packing or covering problem for the same parameters. Attempt to instantiate Regev's or Ajtai's reduction with the dimensions and moduli used in FIPS 203, and determine whether the approximation factor needed in the worst-case SVP step is a small absolute constant or a polynomial in the security parameter. If it is polynomial, then compute what change in δ*(B_n) or γ_n (say, a 1% improvement) would lower the approximation factor below the threshold; if no feasible change suffices, the paper's central claim is not cryptographically meaningful.","verdict_should_be":"UNCHANGED","load_bearing_attack":"This attack targets the abstract's strongest claim: \"the security of the lattice-based cryptosystems relies on the computational complexity of the shortest vector problem (SVP), the closest vector problem (CVP) and their generalizations\" and the subsequent framing of SVP as ball packing and CVP as ball covering. The paper's internal connections are mathematically correct for arbitrary lattices: SVP is equivalent to finding the largest radius of a ball packing, CVP to finding the smallest radius of a ball covering, and both to quadratic-form problems. But the standardized schemes Kyber, Dilithium, and Falcon rely on structured lattices (module lattices and ideal lattices), and their security proofs do not reduce to solving SVP in a worst-case lattice of moderate dimension; they rely on reductions with polynomial approximation factors where the precise constant-factor optimization problems (δ*(B_n), θ*(B_n), γ_n, ω_n) do not appear. No step in the paper connects an exact value of γ_n or a better upper bound on δ*(B_n) to an attack on Module-LWE or NTRU. Thus the paper's motivational bridge is unsupported: a mathematician solving Problem 3.1 or 4.1 would not, by the argument given, affect the security of any NIST scheme.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper is an expository survey of classical mathematical problems that, the author argues, are the foundations of lattice-based post-quantum cryptography. It reviews the shortest and closest vector problems (SVP, CVP), their approximation and decision versions, seven related basis and sublattice problems, and the connections of SVP and CVP to ball packing, ball covering, and positive definite quadratic forms. The survey collects theorems and tables of exact constants (δ*(B_n), θ*(B_n), γ_n, φ*(B_n), ω_n), lists several open problems, and discusses reduction theory. The stated equivalences—SVP with the densest lattice ball packing problem, CVP with lattice ball covering, and both with arithmetic problems for positive definite quadratic forms—are classical and are presented in a way that is mostly faithful to the literature.","tokens_in":11549,"tokens_out":16138,"duration_ms":172567,"significance":"Taken on its own terms as a survey for mathematicians, the paper is useful: the tables of exact constants are correct and well documented, the open problems are stated concretely, and the bibliography gives a good entry point to the geometry-of-numbers literature. The explicit identification of packing and covering densities, Hermite constants, and reduction theory as objects behind SVP/CVP is a service to readers outside cryptography. However, the paper's cryptographic hook is currently overstated: the passage from the security of lattice-based cryptosystems to the listed general worst-case lattice problems is not made precise, and the structured lattices actually used in NIST standards are never discussed. Since the stated motivation of the manuscript is to convince mathematicians that progress on these classical problems matters for post-quantum security, this gap is consequential. The mathematical content itself does not depend on the cryptographic hook, and the survey can be fixed by a clarifying discussion of worst-case-to-average-case reductions and structured lattices.","major_comments":[{"comment":"The central motivating claim that the security of lattice-based cryptosystems relies on SVP and CVP and their generalizations is not supported as stated. The NIST-selected schemes Kyber, Dilithium, and Falcon are based on Module-LWE and NTRU, which involve structured module and ideal lattices; the classical worst-case hardness of SVP/CVP in arbitrary lattices does not by itself transfer to these average-case structured problems. LWE has a worst-case-to-average-case reduction from GapSVP/SIVP with polynomial approximation factors, but that reduction does not make the exact constants δ*(B_n), γ_n, or ω_n the operative hardness parameter, and NTRU has no analogous reduction. Consequently, Conjectures 2.2 and 2.3, which concern worst-case SVP and CVP, do not directly guarantee the security of the deployed schemes. The paper should either spell out the actual reduction chain, including approximation factors and the structured-vs-unstructured gap, or explicitly narrow its motivational claim to the classical lattice problems that historically underpin the area.","section":"Abstract and Section 2 (pp. 2–3)"},{"comment":"The paragraph beginning 'In 2004, Ajtai introduced a new problem, called the short integer solution (SIS) problem' contains a historical error and an imprecise reduction statement. Ajtai's SIS problem and the worst-case-to-average-case reduction appeared in his 1996 STOC paper 'Generating hard instances of lattice problems,' not in 2004; the cited item [3] is a later republication. The following sentence, stating that SIS is 'at least as hard as approximating the shortest vector problem for any lattice,' is also imprecise: the reduction is from worst-case approximate SVP (or SIVP) to average-case SIS for specified approximation factors. The same paragraph's claim that 'the security of both NTRU and LWE does rely on the complexity of approximating versions of the SVP' overstates the situation for NTRU, which lacks such a worst-case reduction, and for LWE, whose reduction is to GapSVP/SIVP rather than to SVP itself. These details matter because they are part of the paper's bridge to cryptography.","section":"Section 2, p. 3"}],"minor_comments":[{"comment":"The statement that 'In 2007, D-Wave demonstrated the first quantum computer' is contested; the D-Wave device is a quantum annealer and is not universally regarded as a quantum computer in the sense underlying Shor's algorithm. The wording should be qualified.","section":"Abstract and Section 1"},{"comment":"The text contains the typo 'the L WE' in the sentence introducing LWE; it should read 'the LWE by O. Regev'.","section":"Section 1, p. 1"},{"comment":"The word 'spaned' in the definition of the b_i projections should be 'spanned'.","section":"Section 3, p. 4"},{"comment":"In the table of θ*(B_n), 'Kersshner' should be 'Kershner'.","section":"Section 3, p. 5"},{"comment":"In the passage defining CVP in quadratic form, the lattice is written as Λ = {zA : z ∈ E^n}; this should be z ∈ Z^n, since with z ranging over E^n the set is all of E^n rather than a lattice.","section":"Section 4, p. 8"},{"comment":"The text 'Lestra-Lenstra-Lovazs reduction' should be 'Lenstra–Lenstra–Lovász reduction'; likewise 'leaded' should be 'led'.","section":"Section 4, p. 9"},{"comment":"The root notation in the table of Hermite constants is garbled: for example, n = 3 should read ∛2, n = 5 should read the fifth root of 8, n = 6 should read the sixth root of 64/3, and n = 7 should read the seventh root of 64. The current typography is likely to confuse readers.","section":"Section 4, table of γ_n"},{"comment":"The sentence 'Clearly, to determine the values of ω(Q) or ϖ(B) are equivalent to the quasi orthogonal basis problem' is imprecise: the quasi orthogonal basis problem is an algorithmic problem for a given lattice, whereas ω_n and ϖ_n are dimension-dependent constants. It would be clearer to say that computing ω(Q) or ϖ(B) for a fixed lattice is what the quasi orthogonal basis problem asks for.","section":"Section 4, discussion of ω_n"}],"recommendation":"major_revision","confidential_remarks":"The manuscript overlaps substantially with the author's own arXiv:2404.19186 [49], which the author discloses in the concluding remarks. The overlap is acknowledged and the present paper's added value is mainly the explicit problem list and constant tables; the editor may wish to assess whether this satisfies the journal's policy on self-overlap. The main technical content appears sound, but the cryptographic framing needs revision before the paper can serve its stated purpose."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is a well-organized survey, not a research contribution. The packing/covering and quadratic-form reformulations of SVP/CVP are standard and mostly stated correctly, and the tables of known constants are genuinely useful. But the cryptographic framing is looser than it should be. The paper moves from \"security of NTRU/LWE relies on SVP\" to the exact constants γ_n, δ*(B_n), θ*(B_n), etc., without ever acknowledging that the NIST-standardized schemes are built on structured lattices (module and ideal lattices) and that the worst-case to average-case reductions carry approximation-factor losses. A mathematician who determines δ*(B_8) or improves the bound on γ_n would not, by anything in this paper, threaten Kyber or Falcon. That is a real gap in the motivational bridge, not a manufactured complaint.\n\nThere is also a factual error: the paper says Ajtai introduced SIS in 2004. That is wrong. SIS appeared in his 1996 \"Generating hard instances of lattice problems\" (STOC); the 2004 date is the Quaderni reprint. A minor but embarrassing slip for a survey.\n\nCredit where due: the author is transparent that the background and references overlap with his companion survey [49], the classical theorems (van Emde Boas, Ajtai, Khot, Dinur et al.) are correctly attributed and stated, and the geometric content is computed correctly. The writing is clear and the collection of open problems (3.6, 3.7, 4.2) is a nice service.\n\nIf this lands in a math journal as an expository piece, it deserves a serious referee; it is not desk-reject material. But I would not accept it as is. The abstract's \"security relies on SVP/CVP\" needs qualification, the module-lattice gap needs at least a paragraph, and the Ajtai date needs correction. For my own work, I would not cite it; the original sources are better. But I would send a student to it for orientation. Send it to review with a request for revision.","headline":"Competent expository survey of lattice geometry problems behind PQC, but the cryptographic motivation overstates the link to deployed structured-lattice schemes and there is a factual error on Ajtai's SIS; worth reviewing as an expository piece, needs revision.","tokens_in":12085,"tokens_out":3011,"would_cite":false,"duration_ms":33005,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["11H31","11H55","52C17","94A60"],"pacs":[],"model":"deepseek-v4-flash","headline":"This review argues that the security of the standardized lattice-based post-quantum cryptosystems rests on three classical mathematical lenses—ball packing, ball covering, and positive definite quadratic forms—so progress on their open…","keywords":["lattice-based cryptography","shortest vector problem","closest vector problem","sphere packing","sphere covering","positive definite quadratic forms","geometry of numbers","post-quantum cryptography"],"falsifier":"A polynomial-time quantum algorithm that approximates SVP or CVP within a polynomial factor would refute the conjectures the paper identifies as guaranteeing security; so would a successful classical or quantum attack on the standardized parameter sets that obtains secret keys without solving a shortest-vector or closest-vector instance.","tokens_in":11121,"feed_emoji":"🔐","tokens_out":11469,"duration_ms":119769,"temperature":0.7,"pith_summary":"Lattice-based cryptography was selected as the backbone of post-quantum encryption, and this review argues that its security is not a new phenomenon but a restatement of classical geometry of numbers. The shortest vector problem (SVP) is a ball packing problem; the closest vector problem (CVP) is a ball covering problem; and both are equivalent to arithmetic questions about positive definite quadratic forms. The paper's purpose is to tell mathematicians that these problems—packing and covering densities, reduction theory, and the constants attached to quadratic forms—are the real bottlenecks, so contributions to them are contributions to cryptography. A sympathetic reader cares because this turns an urgent practical question into open problems with centuries of mathematical tools already aimed at them.","feed_headline":"Packing, covering, quadratic forms: the math behind lattice crypto","feed_subtitle":"Kyber, Dilithium, and Falcon rest on ball packing, ball covering, and quadratic forms—here is how.","key_machinery":"The machinery that carries the argument is the correspondence between lattices, ball packings and coverings, and positive definite quadratic forms. The form $Q(z)=zAA'z'$ encodes every squared lattice length, so the geometry of the lattice is fully captured by an arithmetic minimization problem; the packing lens identifies the shortest vector with the maximal radius for disjoint unit balls, and the covering lens identifies the covering radius $\\rho(\\Lambda)$ with the minimal radius for covering space by translates of the ball $B^n$. The bridge constants are the Hermite constant $\\gamma_n$, the lattice packing density $\\delta^*(B^n)=\\omega_n\\gamma_n/2^{2n}$, the lattice covering density $\\theta^*(B^n)$, and the ratio $\\phi^*(B^n)=2\\rho(\\Lambda)/\\ell(\\Lambda)$, while reduction theory supplies the algorithms and obstructions that turn these constants into practical hardness statements.","core_discovery":"On its own terms, the paper's central claim is a dictionary. A lattice $\\Lambda=\\{zA:z\\in\\mathbb Z^n\\}$ can be read geometrically as a discrete set of points, as an arrangement of equal balls around those points, and arithmetically through the positive definite quadratic form $Q(z)=zAA'z'$. SVP asks for the largest radius $r$ such that $rB^n+\\Lambda$ is a ball packing, equivalently for the minimum of $Q(z)$ over nonzero integer vectors; CVP asks for the smallest radius $\\rho$ such that $\\rho B^n+\\Lambda$ covers all of $\\mathbb E^n$, equivalently for the minimum of $Q(y-z)$ over $z\\in\\mathbb Z^n$. The paper then assembles the known complexity theorems, exact small-dimensional constants, asymptotic bounds for $\\delta^*(B^n)$ and $\\theta^*(B^n)$, the universal bound on the ratio $\\phi^*(B^n)=2\\rho(\\Lambda)/\\ell(\\Lambda)$, and the reduction-theoretic quantities known to matter for lattice algorithms, presenting them as the mathematical core on which the security of the lattice-based post-quantum schemes rests.","pith_inferences":["Editorial: the paper stops short of numerical translation; if the asymptotic constants in the packing and covering bounds were determined, they could be converted into concrete estimates of the gap between shortest-vector and covering-radius hardness in realistic dimensions.","Editorial: the same dictionary suggests a concrete benchmark—generate lattices from exact optimal packings and coverings in dimensions 8 and 24 and test whether standard basis-reduction algorithms recover the predicted shortest vectors, giving a laboratory check of how the pure constants govern attack behavior.","Editorial: the universal bound on $\\phi^*(B^n)$ implies the covering radius and packing radius of every lattice are within a constant factor; a cryptographic reading the paper leaves implicit is that worst-case CVP-style attacks gain only bounded advantage over SVP-style attacks, so parameter choices should reflect that ratio.","Editorial: one can test the paper's framing directly by taking a fixed lattice family and comparing solver performance on SVP against solver performance on CVP as dimension grows; if one problem scales systematically differently, the assumed equivalence of their cryptographic roles would need refinement."],"forward_implications":["Tight estimates of the densest lattice packing density $\\delta^*(B^n)$ would translate directly into bounds on the shortest vector length, and hence on the concrete hardness of SVP-based schemes.","New values or bounds for the thinnest lattice covering density $\\theta^*(B^n)$ would feed the covering radius problem, the densest sublattice problem, and the shortest diagonal problem, all listed as security-relevant.","If no polynomial-time quantum algorithm approximates SVP or CVP within a polynomial factor, the related lattice-based cryptosystems remain secure in the quantum era; the paper records this as the operative pair of conjectures.","Improving the universal bound $\\phi^*(B^n)\\le 2+o(1)$ to $\\phi^*(B^n)\\le 2-c$ would improve the known lower bound on the packing density, and finding a dimension with $\\phi^*(B^n)\\ge 2$ would separate the densest lattice packing from the densest unrestricted packing.","Reduction theory is presented as the key tool for security analysis, so efficient reductions for quantum computation, or proofs that none exist, are posed as the central open algorithmic problem."],"supporting_citations":[{"why":"Proves the closest vector problem is NP-hard, the first complexity anchor for the CVP side.","marker":"[42]"},{"why":"Proves the shortest vector problem is NP-hard under randomized reductions, anchoring worst-case SVP hardness.","marker":"[2]"},{"why":"Introduces the short integer solution problem and the hardness connection to approximating SVP that underlies NTRU and LWE.","marker":"[3]"},{"why":"Introduces the NTRU cryptosystem, the basis for the Falcon standard.","marker":"[17]"},{"why":"Introduces the learning with errors problem, the basis for the Kyber and Dilithium standards.","marker":"[35]"},{"why":"Shows approximating SVP within any constant factor is NP-hard under randomized reductions.","marker":"[20]"},{"why":"Shows approximating CVP within an almost-polynomial factor is NP-hard.","marker":"[11]"},{"why":"Proves the exact sphere packing density in dimension 24, one of the two high-dimensional exact results used to tabulate packing constants.","marker":"[8]"},{"why":"Proves the exact sphere packing density in dimension 8, the other high-dimensional exact result in the table.","marker":"[43]"},{"why":"Supplies the classical packing and covering bounds, including the universal bound on the covering-to-packing radius ratio.","marker":"[38]"}],"fun_headline_variants":["Lattice crypto rests on ball packing and quadratic forms","The geometry behind post-quantum lattice security","From ball packing to Kyber: the math of lattice crypto","SVP as ball packing: the math powering lattice crypto","Why lattice security is really a ball-packing problem"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the structured, average-case lattices used in the standardized schemes inherit the hardness of general worst-case shortest-vector and closest-vector problems.","fun_headline_variants_meta":{"raw":{"variants":["Lattice crypto rests on ball packing and quadratic forms","The geometry behind post-quantum lattice security","From ball packing to Kyber: the math of lattice crypto","SVP as ball packing: the math powering lattice crypto","Why lattice security is really a ball-packing problem"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00022,"raw_usage":{"total_tokens":1496,"prompt_tokens":1042,"completion_tokens":454,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":658,"completion_tokens_details":{"reasoning_tokens":375}},"tokens_in":658,"tokens_out":454,"duration_ms":5107,"temperature":1.0,"reasoning_tokens":375,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T21:43:37.952985+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A polynomial-time quantum algorithm that approximates SVP or CVP within a polynomial factor would refute the conjectures the paper identifies as guaranteeing security; so would a successful classical or quantum attack on the standardized parameter sets that obtains secret keys without solving a shortest-vector or closest-vector instance.","supporting_citations":[{"cited_title":"S¨ odergren, On the distribution of angles between the N shortest vectors in a random lattice,J","cited_arxiv_id":null,"evidence_quote":"Proves the closest vector problem is NP-hard, the first complexity anchor for the CVP side."},{"cited_title":"Ajtai, The shortest vector problem in L2 is NP-hard for randomized reductions","cited_arxiv_id":null,"evidence_quote":"Proves the shortest vector problem is NP-hard under randomized reductions, anchoring worst-case SVP hardness."},{"cited_title":"Ajtai, Generating hard instances of lattice problems","cited_arxiv_id":null,"evidence_quote":"Introduces the short integer solution problem and the hardness connection to approximating SVP that underlies NTRU and LWE."},{"cited_title":"Hoffstein, J","cited_arxiv_id":null,"evidence_quote":"Introduces the NTRU cryptosystem, the basis for the Falcon standard."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces the learning with errors problem, the basis for the Kyber and Dilithium standards."},{"cited_title":"Khot, Hardness of approximating the shortest vector problem in lattices","cited_arxiv_id":null,"evidence_quote":"Shows approximating SVP within any constant factor is NP-hard under randomized reductions."},{"cited_title":"Dinur, G","cited_arxiv_id":null,"evidence_quote":"Shows approximating CVP within an almost-polynomial factor is NP-hard."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Proves the exact sphere packing density in dimension 24, one of the two high-dimensional exact results used to tabulate packing constants."},{"cited_title":"van Emde Boas, Another NP-complete problem and the complexity of computing short vectors in a lattice","cited_arxiv_id":null,"evidence_quote":"Proves the exact sphere packing density in dimension 8, the other high-dimensional exact result in the table."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the classical packing and covering bounds, including the universal bound on the covering-to-packing radius ratio."}],"review_version":1}