Provable Subexponential Algorithms for NIST Third-Round Lattice Families

1 Introduction

• Small secrets and errors motivate asking whether narrow coefficient distributions permit provable subexponential recovery, beyond the heuristic security estimates used for lattice reduction, sieving, and hybrid attacks.Earlier work includes a Wagner-style Gaussian sampler [DEL25] and a decision-LWE algorithm [HGH26], but the latter still needs more than n samples and does not cover structured LWE.Source: §1 · p. 4

1.1 Contributions

• A coordinate guess changes the error vector’s squared norm by an exact integer gap, allowing one Gaussian list to identify each secret coordinate without enumerating the others.The recovery procedure separates coordinate tests and list construction from the public operator’s algebraic structure.Source: §1 · p. 4, §1.1 · p. 5
• Prefix smoothing estimates for prime fields, cyclotomic modules, finite-field multipliers, and power-of-two moduli connect the generic recovery theorem to the five linear families.Uniform images, ideal decompositions, and additive order layers establish mass bounds, including for coefficient prefixes ending within a polynomial block.Source: §1.1 · p. 5
• For public NTRU-type quotients, Gaussian averages estimate successive affine-slice masses and guide coordinate choices toward a short pair passing public algebraic checks.The valid-pair path probability is controlled by total Gaussian mass; Falcon and cyclic NTRU geometry comes from key quality or spectral and saturation estimates.Source: §1.1 · p. 5

1.2 The NIST Third-Round Lattice Families

• The two frameworks are instantiated for seven growing families associated with NIST third-round candidates, including five linear families and the Falcon and cyclic NTRU quotient families.Kyber and Dilithium were subsequently standardized as ML-KEM and ML-DSA, respectively.Source: §1 · p. 4, §1.1 · p. 5

1.3 Low Energy Linear Recovery

• When D → ∞ and ln q is polylogarithmic, low-energy linear recovery takes expected time and space 2^((1/2+o(1))n/D); for polynomial q and polylogarithmic U, D ∼ ln ln n.A single Gaussian list serves all coordinate tests and admissible labels; recovery holds for inputs within the energy bound when the prescribed geometric event holds.Source: §1.3 · p. 9
• With probability 1−o(1), the linear-recovery corollaries recover the original secrets for FrodoKEM, Kyber/ML-KEM, SABER, NTRU LPRime, and Dilithium/ML-DSA in expected time and space Tlin(n).For NTRU LPRime, n = p; for Dilithium/ML-DSA, n = ℓm.Source: §1.3 · pp. 9–10
• The linear applications rely on family-specific geometric estimates for additive orders, ideals and prefixes, coefficient prefixes, random field multipliers, and restricted ML-DSA blocks.These estimates support FrodoKEM, Kyber/ML-KEM, SABER, NTRU LPRime, and ML-DSA recovery statements.Source: §1.3 · p. 10
• For square ternary LWE over a prime modulus, coordinate recovery takes 2^o(n), versus May’s exponential heuristic estimates for fixed-positive-entropy ternary secrets.Both comparison methods use the original n equations in the common square model.Source: §1.3 · p. 10

1.4 Short Pair Search from Public Quotients

• 2^O(m/ln ln m) time and space suffice to find a verified nonzero short vector with probability at least 1 − m^-K under a public Gaussian-mass bound.The search fixes coordinates through affine lattice slices, samples each next coordinate proportional to the slice’s Gaussian mass, and estimates masses using reusable dual Gaussian lists.Source: §1.4 · pp. 10–11
• For Falcon, quality-qualified keys yield an equivalent NTRU basis in 2^O(n/ln ln n) time and space; NTRU-HPS/HRSS short key cores are recovered in 2^O(N/ln ln N).Falcon’s key-generation quality condition supplies the mass bound; HPS/HRSS bounds hold with probability 1 − o(1) over accepted inputs and algorithmic randomness.Source: §1.4 · p. 11

1.5 Consequences and Organization

• Under randomized ETH, reductions to matching low-energy recovery laws cannot have n(N)/D_n(N) = o(N), where this ratio measures the composed recovery scale.The paper also states that constant or polylogarithmic coefficient scales with polynomial moduli give D ∼ ln ln n in the discussed linear families.Source: §1.5 · p. 11

2.1 A coordinate guess reveals an energy gap

• A correct coordinate guess uniquely minimizes the comparison energy, while every incorrect integer guess raises it by at least one.The other secret coordinates contribute a common offset, so they need not be enumerated.Source: §2.1 · p. 12

2.2 From a Gaussian score to a shared list

• One Gaussian list estimates scores simultaneously for all admissible coordinate tests, and adjacent-score comparisons enable binary search in O(log(2B + 1)) tests per coordinate.A single simultaneous event also covers operator-determined rounding errors and permits reuse across FrodoKEM secret columns.Source: §2.2 · p. 13

2.3 Building the list via Wagner-Style Gaussian Sampling

• The Wagner-style construction adds secret-coordinate constraints in blocks through Gaussian lifting and quotient-label pairing, with resulting time and space 2^((1/2+o(1))n/ln ln n).The allocation schedule uses list depth to accumulate capacity for all coordinates while keeping public observations fixed.Source: §2.3 · p. 14

2.4 The geometry of the public operator

• Structured-operator smoothing bounds come from uniform images over fields and ideal or additive-order decompositions in structured rings, including partial coefficient prefixes.The geometric argument covers Kyber/ML-KEM and the selected square row block of ML-DSA, as well as power-of-two settings for FrodoKEM and SABER.Source: §2.4 · pp. 14–15

2.5 From Gaussian mass to a short pair search

• Because quotient lattices contain zero, negatives, and potentially other short pairs, Gaussian mass guides a search through affine slices rather than a norm-ball uniqueness test.At each stage, estimated slice weights choose the next coordinate; a positive coordinate anchor excludes zero and retaining both signs covers either sign of a valid pair.Source: §2.5 · pp. 15–16
• For Falcon, the quality-qualified key yields a uniform public Gaussian-mass budget of 2; cyclic NTRU HPS/HRSS uses spectral and saturation estimates to obtain its recovery guarantee.For cyclic NTRU, the saturation estimate gives ln ∆sat ≤ N/D_N with probability 1−o(1), where D_N ∼ ln ln N.Source: §2.5 · p. 16

3.1 Notation and coefficient embeddings

• Coefficient embeddings concatenate ring-vector coefficients; integer lifts must be specified before norms or integer observations, which use the Euclidean coefficient embedding.The section distinguishes coordinatewise and centered lifts and sets conventions for coefficient and abstract vector indices.Source: §3.1 · p. 16

3.2 Lattices and discrete Gaussians

• Lattice preliminaries define duals, determinants, and primitive sublattices; projection onto the orthogonal complement yields a lattice whose fibers are translates used in Gaussian lifting.Discrete Gaussians are defined on lattices and their cosets, with width t corresponding to continuous standard deviation t/√(2π).Source: §3.2 · p. 17

3.3 Smoothing and Poisson summation

• Poisson summation bounds shifted Gaussian mass uniformly over centers at smoothing widths and yields the Fourier identity underlying the periodic Gaussian score used in Section 4.The theta-function relation follows by taking the lattice Z and center zero.Source: §3.3 · p. 17

3.4 Modular kernels and the LWE relation

• Modular kernel lattices have rank equal to the number of input coordinates; systematic matrices are surjective even for composite q, and their dual structure supports the stated LWE relations.Search-LWE seeks the secret in b = A^T s + e mod q, while decision-LWE distinguishes this input from uniform b; the recovery formulation uses y = Ms + e with h ≤ n.Source: §3.4 · p. 18

3.5 Conditional similarity and concentration

• Strong conditional γ-similarity controls dependent Gaussian lists by conditioning on all other entries, enabling concentration of bounded scores; implementation error adds only one total-variation penalty.For 0 ≤ γ ≤ 1, Lemma 3.1 bounds score deviations using a Hoeffding tail and the conditional-mean discrepancy.Source: §3.5 · pp. 18–19

3.6 Gaussian lifting and pairing

• Gaussian lifting and cyclic quotient pairing produce vectors in the target lattice without reusing inputs, while preserving strong conditional similarity within a smoothing-width condition.For M0 ≥ 3P, pairing returns exactly floor(M0/3) vectors; if the input similarity is γ and t ≥ 2ηε(L), the output similarity is 4γ + 3ε.Source: §3.6 · pp. 19–20

3.7 Auxiliary lattices and shifted sampling

• Random auxiliary lattices have a cyclic quotient of size P, while shifted Gaussian sampling achieves statistical error 2^-cDGSb^2 in time and space 2^(b+o(b)); adaptive-call errors compose additively.The auxiliary-lattice smoothing guarantee holds with probability at least 1 − 2^(1−b) under the stated conditions; the sampling bound is up to polynomial input-bit factors.Source: §3.7 · pp. 20–21

3.8 Gaussian mass from uniform images

• For uniform-image public operators, expected nonzero dual mass can be bounded even without joint independence across labels, with an additional bound when Im(T) < ε.The method uses uniform images of each fixed nonzero label to calculate the mass relevant to prefix smoothing.Source: §3.8 · pp. 21–22
• Under the stated width and growth conditions, Lemma 3.6 and Corollary 3.7 bound Gaussian mass for prescribed lattices whose public maps have the uniform-image property.The result covers lattices that may depend on the same public draw.Source: §3.8 · pp. 22–23
• The bounds apply to independent prime-modulus matrices and to multiplication by a random field element.Source: §3.8 · p. 23

4 Secret Recovery by Coordinate Scoring

• The model uses y = Ms + e (mod q), and appending guessed secret coordinates leaves the observation count unchanged.Rounded observations enter through an integer lift; the secret and error may depend on M.Source: §4 · p. 23, §4.1 · p. 23

4.1 Systematic coordinates and the joint energy bound

• A coordinate’s correct candidate has an exact squared-norm gap over incorrect candidates, even when the other secret coordinates are not enumerated.The coordinate energy-gap lemma applies simultaneously to all candidates within the stated coordinate bound.Source: §4.1 · p. 24

4.2 A score estimate on the entire energy ball

• Under the stated operator condition, periodic Gaussian scores approximate the leading Gaussian terms uniformly over the full energy ball, preserving a gap of at least 31g/32.The score bounds apply simultaneously to integer labels and error vectors of norm at most R.Source: §4.2 · pp. 24–25

4.3 One list for all public labels

• One shared list recovers every bounded-energy input with probability at least 1 − δ − ν, and adjacent-score binary search locates each coordinate’s maximizing candidate.The recovery event is uniform over admissible pairs; a union bound also covers public labels and inputs chosen as functions of M.Source: §4.3 · pp. 25–26

4.4 Energy bounds for the secret and error

• Concentration or deterministic coefficient bounds can supply the joint secret-and-error energy threshold required by the recovery theorem.The threshold must be fixed before sampling the public matrix and lie within the theorem’s parameter window.Source: §4.4 · pp. 27–28

5 Constructing the Gaussian List

• The construction begins with easy Gaussian sampling on the integer lattice and grows the list width so later stages can impose larger coordinate blocks.The section attributes the lifting-and-pairing method to DEL and its quantitative LWE construction to HGH [DEL25].Source: §5 · p. 29

5.2 Widths and block sizes

• A geometric width schedule allocates coordinate blocks whose combined capacity reaches n while keeping the list length 2^(1/2+o(1))n/D.The required public-distribution condition is smoothing at the selected coordinate prefixes.Source: §5 · p. 29, §5.2 · pp. 30–31

5.1 The unified recovery statement

• Under the energy and candidate bounds and the scheduled-prefix condition, the randomized algorithm recovers the integer secret from h labels with failure probability at most pE + ωn + o(1).It constructs one Gaussian list and applies LinearScoreRecover to all coordinates.Source: §5.1 · p. 29

5.3 Lifting and pairing

• Lifting adds coordinate constraints and pairing returns vectors to the desired prefix lattice, producing a list of N vectors with strong conditional similarity to the target discrete Gaussian.The construction succeeds with probability at least 1 − 2r2^−bmin over its independent uniform choices.Source: §5.3 · pp. 32–33

5.4 From the list to recovery

• The list’s scores can be estimated accurately enough for the recovery theorems to identify every coordinate on the energy event.The cited proof concludes that every coordinate is identified, then recovers the original integer representative.Source: §5.4 · pp. 34–35

• The paper demonstrates its linear recovery framework on unstructured LWE, where the public matrix has independent uniform entries.The comparison with May’s attacks assumes (s, e) is independent of M, although the recovery result also allows dependence on M.Source: §6 · pp. 35–36
• The original secret is recovered from the given n equations with probability 1 − o(1).The square ternary model has a deterministic joint secret-and-error energy bound of 2n.Source: §6 · p. 36
• In the common square ternary model, the paper gives a proved subexponential upper bound, while May’s representation-based attacks have heuristic exponential estimates.Both attacks use the original n equations [May21, Sections 2.1–2.3].Source: §6 · pp. 35–36

7.1 An exact additive order identity

• Grouping nonzero dual labels by additive order yields an exact theta-series identity for the nonzero dual mass over power-of-two moduli.Unlike the field case, a nonzero label can have an image confined to a proper subgroup.Source: §7.1 · p. 37

7.2 Recovery from a square or nearly square system

• The dyadic recovery theorem applies to square or nearly square systems and recovers the integer secret from h labels under its energy and geometric conditions.The proof bounds the geometric-condition failure probability by 8re^−h/4 = o(1).Source: §7.2 · p. 38

7.3 Several columns with the same public matrix

• The multi-column result reuses one list for every column, allowing dependence among columns and between the columns and A.For polynomially many columns, the leading exponent and reusable list space remain unchanged.Source: §7.3 · pp. 39–40
• For q = 2^⌈κ log2 n⌉ with κ > 1/2, one Gaussian list recovers all columns of S with probability 1 − o(1) in expected time and space 2^(1/2+o(1))n/ln ln n.The result assumes a polynomial number of columns and a public polylogarithmic simultaneous joint energy bound.Source: §7.3 · p. 40

8.1 The public operator and the modulus restriction

• The public relation is y=Ms+e (mod q), with M the coefficient matrix of multiplication by a uniform module matrix; fixed splitting degree forces q=Ω(n).For k=1, the relation is the algebraic form of ring-LWE; the same public relation underlies Kyber/ML-KEM [FIPS203, Section 5.1, Algorithm 13].Source: §8.1 · p. 41

8.2 Ideal images in the coefficient basis

• For coefficient prefixes, larger image ideals provide averaging, while small ideals force long nonzero integer representatives; both estimates bound their Gaussian mass.The analysis tracks ideal images and partial polynomial blocks in the original coefficient basis.Source: §8.2 · pp. 41–42

8.3 Smoothing every prescribed prefix

• The ideal-image and representative-length estimates establish the prefix-smoothing condition needed by the recovery schedule.The section’s smoothing proposition provides the combined bound for prescribed prefix and scale pairs.Source: §8.3 · pp. 43–44

8.4 Recovery and the Kyber/ML-KEM relation

• The fixed splitting degree also requires ln(q/√n) to grow at least as ln n, constraining the modulus regime for the stated recovery rate.The section derives β≥1 when ln(q/√n)=(ln n)^β+o(1).Source: §8.4 · pp. 44–45
• With fixed k, q=n^κ+o(1), fixed splitting degree, and polylogarithmic energy bound, Kyber/ML-KEM secrets are recovered with probability 1-o(1) in time and space 2^((1/2+o(1))n/ln ln n).The bound applies to the original coefficient secret from k ring equations.Source: §8.4 · p. 45

9 SABER: Recovery from Rounded Module Products

• Modulo two, X^d+1=(X+1)^d, so the ideals form a nested chain whose prefix counts enable Gaussian-mass bounds in coefficient coordinates.The counting handles prefixes ending inside a polynomial block.Source: §9 · p. 46, §9.2 · p. 48

9.1 The rounded relation and its energy

• The rounded relation has a bounded integer rounding error, and polylogarithmic secret and rounding scales yield the target recovery exponent.The residue bound holds for every matrix and secret.Source: §9.1 · pp. 46–47

9.2 Ideals and coefficient prefixes

• The ideal chain is described by powers of 1−x, with prefix dimensions accounting for constraints and free coefficient bits.These counts include partial polynomial blocks.Source: §9.2 · pp. 47–48

9.3 Gaussian mass of the prescribed prefixes

• For order-two labels, a nonzero prefix lies at least 1/2 from the integer lattice, giving Gaussian decay; summing the order ranges establishes the smoothing bound.The order-two contribution is at most (1+o(1))e^(-8πL0).Source: §9.3 · pp. 49–50

9.4 Recovery and the effect of rounding

• When ln ∆=(ln n)^a+o(1) for fixed 0<a<1, the recovery depth is D=(1−a+o(1))ln ln n.This quantifies how coarser rounding affects the depth.Source: §9.4 · p. 51
• For fixed module rank, q=n^κ+o(1) with κ>1/2, and polylogarithmic secret and rounding bounds, SABER secrets are recovered with probability 1-o(1) in time and space 2^((1/2+o(1))n/ln ln n).This is the specialization for k rounded ring equations.Source: §9.4 · p. 51

10.1 The public multiplier and its Gaussian mass

• Multiplication of any fixed nonzero field element by a uniform public multiplier gives a uniform image, supplying the prefix randomness required for smoothing.The argument applies to any irreducible defining polynomial.Source: §10.1 · p. 52

10.2 Rounding gives a small error

• Rounding to a multiple of three yields the lifted relation y=MGa+e (mod q), with each error coefficient in {−1,0,1}.The rounded integer output is retained when forming the error.Source: §10.2 · p. 53

10.3 Recovery from the given product

• For prime p and q=Θ(p), the original ternary NTRU LPRime secret is recovered with probability 1-o(1) in time and space 2^((1/2+o(1))n/ln ln n), where n=p.The family assumes the specified arithmetic requirements and irreducibility of X^p−X−1 modulo q.Source: §10.3 · p. 53
• For q=Θ(n), the recovery depth satisfies D∼ln ln n, and the recovered integer coefficient vector determines the ring element a.The result applies to the n coefficient observations in the single rounded product.Source: §10.3 · p. 54

11 Dilithium/ML-DSA: Recovery from Compressed Public Keys

• The public key stores high bits of a noisy module product; discarded low bits enter the lifted error, allowing the prime-module recovery geometry to apply.The remaining short algebraic components can then be completed coefficientwise.Source: §11 · p. 54

11.1 The public relation and its integer lift

• Power2Round gives a lifted relation with an energy certificate, and the selected rows provide a uniform square module operator for recovery.The certificate bounds the combined secret and error energy by nV.Source: §11.1 · pp. 54–55

11.2 Recovery of the original secret component

• The recovery theorem returns the original integer coefficient vector s1 with probability 1-o(1) over the public matrix and algorithmic randomness.The construction uses a predetermined square block of ℓ public equations.Source: §11.2 · p. 55

11.3 Completion of the short algebraic components

• The recovered s1 enables deterministic polynomial-time completion of compatible short algebraic components that reproduce the same compressed public key.The completion finds bounded s′2 and a corresponding rounding remainder.Source: §11.3 · p. 55

12 Recovering Short Pairs from Public Quotients

• The search fills u one coordinate at a time, estimates affine-slice completion masses with dual Gaussian lists, and verifies resulting short pairs against public checks.Fixing a positive coordinate anchors the search; estimates for candidate next values reuse a list with different shifts.Source: §12 · p. 56

12.1 From Gaussian mass to verifiable search

• A public bound on total Gaussian mass supports a verifier-checked output with probability at least 1−m^-K and time and space 2^O(m/ln ln m).For a fixed short witness, transition-probability bounds telescope across slices, and repetition raises the success probability.Source: §12 · p. 56, §12.1 · p. 57

12.2 Falcon: recovery from the key generation quality bound

• For Falcon, recovery succeeds with probability at least 1−n^-K in time and space 2^O(n/ln ln n) for public keys satisfying the stated quality-witness conditions.The output also meets the theorem's algebraic and quality guarantees; the result applies to distributions supported on quality-qualified keys, including qualifying KeyGen outputs.Source: §12.2 · pp. 58–59

12.3 Cyclic NTRU: distributional short key recovery

• For cyclic NTRU, spectral and saturation estimates supply a public mass budget that makes the affine-slice search applicable.The stated sufficient conditions include bounds on spectral extrema and the logarithm of the saturation index.Source: §12.3 · p. 59
• The cyclic NTRU results recover a valid short key core in time and space 2^O(N/ln ln N) under the stated accepted-law conditions.The results cover HPS and HRSS, including the HPS sorting-label variant; the combined conclusion states that the accepted laws have vanishing spectral and saturation failure terms.Source: §12.3 · pp. 60–61

13 Conclusion and Further Discussion

• Gaussian estimates expose coordinate-guess energy gaps in linear relations and guide affine-slice searches for short quotient pairs; operator geometry supplies the needed bounds.Separating recovery procedures from public-operator geometry suggests studying further relations through the energy and mass bounds they require.Source: §13 · p. 61

13.1 Further Applications to Homomorphic Encryption

• For homomorphic-encryption public keys, reduction to a selected prime yields a relation to which the linear recovery theorem applies, with one ring equation supplying N coefficient observations.For qi=N^κ+o(1), fixed κ≥1, and polylogarithmic V, the stated expected time and space is 2^((1/2+o(1))N/ln ln N).Source: §13.1 · pp. 61–62

13.2 Further Directions

• The proposed implementation work measures linear score gaps and quotient slice-mass estimates, while suggested extensions include new public distributions and rings.The discussion also proposes Gaussian peak estimation for linear recovery and pruning strategies for quotient search.Source: §13.2 · pp. 62–63
• For HAWK, the quadratic Gram-matrix public key fits neither framework as presented; applying them would require a suitable linear relation or short-pair lattice formulation with a mass bound.The discussion describes this as a scope boundary of the two frameworks, not of lattice cryptanalysis generally.Source: §13.2 · p. 63

A Finite Implementation

• The finite-sampling appendix gives rational-mass approximation and sampling procedures with bounded error, including for adaptive calls with fresh randomness.The stated adaptive-call error is bounded by the sum of the assigned accuracies.Source: §A.1 · pp. 68–69

A.2 Finite implementation for linear recovery

• Finite linear-recovery sampling uses rational coordinate representations and cutoffs whose combined cost is at most e^-n2, while score errors remain below the adjacent gap g.Cosine evaluation uses precision O(n/D) bits, and retained coordinates have polynomial bit length through r = O(ln q) levels.Source: §A.2 · p. 70

B Proofs for Quotient Recovery

• The quotient-recovery proof proceeds through dual Gaussian-list construction, affine-slice search, and Gaussian-mass bounds verified for Falcon and cyclic NTRU.In the family applications, the public matrix is coefficient multiplication by h for Falcon or by bh for cyclic NTRU.Source: B Proofs for Quotient Recovery · pp. 70–71

B.1 Persistent Gaussian lists

• One random rank-one extension serves every coordinate prefix under a single smoothing event, and fixed-pair differences remove the extension.The construction applies to both multiplication matrices used later.Source: §B.1 · p. 71

Then the completed reference list is strongly conditionally

• The finite quotient-removal procedure disagrees with its completed reference with probability at most ζ and preserves similarity after conditioning on positive-probability events determined by pair-success indicators.The reference list is formed by completing a deficient output with independent samples from the conditional difference law.Source: Then the completed reference list is… · p. 71, §B.1 · p. 71
• The persistent-list procedure has preprocessing failure and total-variation error each at most n^-K, with total time and space exp(O(n/D)).For at most n^AS prescribed coordinate sets, it produces Nout-entry lists whose reference laws are strongly conditionally similar at parameter 1/ssearch, subject to the theorem’s stated parameter conditions.Source: Then the completed reference list is… · p. 72
• Finite-precision sampling uses dyadic error budgets, while rational widths and lattice denominators keep the arithmetic at polynomial bit length through O(ln n) levels.The stated error budget bounds implementation error by ν and reference failure probability by 3n^-K-10.Source: Then the completed reference list is… · p. 76

B.2 Affine slice search and witness containment

• Affine-slice search reuses one dual Gaussian list per free-coordinate set, estimates child weights with a shared denominator that cancels, and samples only values consistent with the partial energy bound.The search bounds the relevant cosine phases across lists and evaluates the queries encountered on sampled paths.Source: §B.2 · pp. 76–77

3. Run every anchored branch independently

• A fixed witness is missed with probability at most εpre + ν + εqry + εhit; repeated anchored branches recover it with constant-times-pB probability per correct run.The search retains each verified pair and its negative; the guarantee also holds after averaging over any distribution of witness pairs.Source: §3 · pp. 77–78

B.3 Falcon: quality, Gaussian mass, and basis completion

• The Falcon analysis presents two routes to the required negacyclic Gaussian-mass bound: key-generation quality and spectral bounds on a short pair.The available passages establish the quality-condition route and introduce the separate spectral route without detailing its guarantee.Source: §B.3 · pp. 78–79

B.3.1 Basis completion

• For the conventional NTRU row basis, the constructed rows lie in the public lattice and their determinant matches its index, so they form a basis.A polynomial-time completion procedure solves the required integer system and checks accepted candidates using exact arithmetic.Source: §B.3.1 · pp. 79–80

B.3.2 Recovery from the key quality condition

• For every quality-qualified Falcon public key, the public mass budget is Amass = 2 uniformly, enabling the stated recovery schedule in the modulus window.The quality predicate uses C = 117/100 for Falcon and is decidable exactly in polynomial bit complexity.Source: §B.3.2 · pp. 80–81
• Qualified public keys yield an accepted candidate with probability at least 1 − n^-K in time and space 2^O(n/ln ln n), uniformly over keys.The verifier uses polynomial-time completion and quality checks; the accepted candidate has a quality basis that supplies the mass bound.Source: §B.3.2 · p. 82

B.3.3 Recovery from spectral bounds

• Under the stated modulus window and spectral bounds, an admissible witness enables negacyclic recovery with probability 1 − o(1) in time and space exp(O(n/ln ln n)).The guarantee is uniform over instances admitting such a witness; the distributional corollary allows the spectral condition to fail with probability ω_n, yielding success at least 1 − ω_n − o(1).Source: §B.3.3 · pp. 83–84

B.4 Cyclic NTRU: saturation and recovery

• For cyclic HPS and HRSS, accepted pairs yield a short key core, and when q = Θ(N), a constant C_len gives a pair norm at most C_len√q, below q/2 eventually.The core comprises the secret polynomial and inverses used for decryption and decapsulation on valid inputs.Source: §B.4 · p. 85

B.4.1 Saturation and Gaussian mass

• When G_min > 0, the short-pair sublattice has finite-index saturation, with Δ_sat = [T : R_N] = [R_N : fR_N + gR_N + kR_N], and its Gaussian mass is bounded using Δ_sat and spectral theta factors.The saturation index is computable from the rectangular Smith form of the stacked multiplication matrices; the mass estimate yields recovery conditions.Source: §B.4.1 · pp. 86–87
• A public total-mass bound yields a recovery budget A_mass = 4⌈(C_mass+1)N/D_N⌉ and success probability 1 − N^-K in time and space 2^O(N/ln ln N).The stated modulus, witness, and radius conditions are also required for the recovery theorem to apply.Source: §B.4.1 · p. 87
• Spectral and saturation bounds suffice for recovery when G_min ≥ q/N^α, G_max ≤ C_sp q ln N, and ln Δ_sat ≤ C_sat N/D.Under the Corollary B.17 schedule, the result uses C_mass = C_sat + 1.Source: §B.4.1 · p. 87

Put s2

• Sampling estimates give an explicit integer A_N with ln A_N = O(N/D) as a public mass bound.The estimate assumes the stated spectral and saturation bounds, including G_min ≥ q/N^α, G_max ≤ C_sp q ln N, and ln Δ_sat ≤ C_sat N/D.Source: §B.4.1 · p. 87, Put s2 · p. 88
• At s = sref, both theta-factor contributions are 1 + N^-ω(1), with the stated conclusions following from monotonicity and dyadic lower approximation.The proof evaluates the upper bound in (B.47) at sref.Source: Put s2 · p. 88

B.4.2 Recovery from geometric bounds

• The recovery theorem returns a valid short pair and associated decryption tuple with high probability, using time and space bounded by the stated subexponential cost.It applies when the generator satisfies the joint geometric event and other recovery conditions; conditional success is at least 1 − N^-K for every fixed K > 0.Source: §B.4.2 · p. 88

B.4.3 Arithmetic parameters and accepted sampling laws

• HPS and HRSS use common arithmetic constraints and accepted key laws, while growing sorting-label lengths yield an asymptotically accurate HPS sampling law.For bN ≥ (2 + δ) log2 N, the fixed-type sorting error is o(1); bN = ⌈(Ktag + 3) log2 N⌉ gives error O(N^-Ktag−1).Source: §B.4.3 · pp. 89–90

B.4.4 Logarithmic saturation from common cyclotomic ideals

• For the raw HPS and HRSS laws, the saturation bound holds with fixed constant Csat = 1 when the public dyadic schedule satisfies DN ∼ ln ln N.The bound uses a proxy based on common cyclotomic ideals; for g with cyclic coefficients bounded by two, the expected log-norm contribution is at most ϵN N ln(3N).Source: §B.4.4 · p. 92

B.4.5 Spectra of the raw samplers

• Balanced polynomials with m coefficients of each sign have uniform small-ball and upper-tail estimates at nontrivial frequencies, with Q(1) = 0.The estimates hold for odd prime N and ηN ≤ m ≤ (N−1)/2.Source: §B.4.5 · p. 93
• TernaryPlus preserves the input small-ball estimates up to twice the constant, and outputs from independent input blocks remain independent.These bounds support the HRSS spectral estimate alongside the bounds for the raw HPS laws.Source: §B.4.5 · p. 94
• For q = Θ(N), q ≥ 2N + 1, and 2/3 < α < 1, raw HRSS and ideal HPS laws obey the stated spectral bound with Csp = 32(Ksp + 3).The bound controls the probability that Gmin < q/N^α or Gmax > Csp q ln N.Source: §B.4.5 · p. 95

B.4.6 Geometry of accepted keys

• The accepted-key geometry event inherits the raw failure bound rsp + rsat, with an additional εFT term for the HPS sorting law.Conditioning on key-generation acceptance accounts for the denominator in the recovery guarantee.Source: §B.4.6 · pp. 95–96

C Changing the Public Distribution

• A changed public law adds its energy failure, geometric-event failure, and internal algorithm failure to the total recovery failure bound.The geometric-event term can be controlled through total variation distance or a density bound relative to the reference law.Source: C Changing the Public Distribution · p. 96
• A short seed alone provides neither transfer bound; geometry must instead be proved for the induced law or covered by suitable pseudorandomness.The pseudorandomness must cover the recovery algorithm’s running time and success experiment.Source: C Changing the Public Distribution · p. 96

D.1 Recovery Cost and the Reduction Model

• The recovery cost in the stated window is 2^O(n/Dn), with a computable worst-case timeout and constant success probability on each good instance.The reduction model requires a specified target law, recovery output, and good-instance set.Source: §D.1 · p. 97

4. The accumulated exceptional probability satisfies

• Each query’s bad-instance probability is bounded by δn(N) + ζN when its law is within ζN of the specified target law.The reduction discussion requires matching the full recovery task, including secret distribution, observation count, and geometric guarantee.Source: §4 · p. 97, §D.1 · p. 97

D.2 Composition and Randomized ETH

• Under the stated reduction conditions, 3-SAT has a bounded-error randomized algorithm running in time 2^O(n(N)/Dn(N)) poly(N).The composition budgets errors from bad queries and from recovery on good instances separately.Source: §D.2 · pp. 97–98
• Repeating recovery reduces its internal error on good instances but does not reduce the chance that a query violates energy or geometry assumptions.The exceptional-query budget is separate from amplification.Source: §D.2 · p. 98

D.3 Dimension and Hidden Energy

• Under rETH, the stated matching linear-dimension reduction is excluded when Dn(N) → ∞.For polynomial modulus and polylogarithmic Un, Dn ∼ ln ln n, and the paper also excludes the corresponding stated growth windows.Source: §D.3 · p. 98, §D.2 · p. 98
• At fixed target dimension and modulus, increasing Un decreases Dn and raises recovery cost, so dimension and energy must be compared together.The composed exponent is O(n/ln Ln) for Un = exp(ln n/Ln), where 1 ≪ Ln ≤ ln n.Source: §D.3 · p. 99

E Finite-Parameter Substitutions

• Table 3 presents parameter values, joint energy bounds, and formal leading-term values for five linear public families.The finite formal substitution uses n/(2D), while the asymptotic comparison replaces D with ln ln n.Source: E Finite-Parameter Substitutions · p. 99, Table 3 · p. 100
• For ML-DSA-44, U ≈ 4098 gives D ≈ 0.292 versus ln ln n ≈ 1.936, so bD/b∞ ≈ 6.63.The rounding contribution 2d−1 = 4096 dominates the deterministic energy bound at the listed ML-DSA dimensions.Source: E Finite-Parameter Substitutions · p. 100
• For the listed linear-family parameter ranges, polynomial modulus and polylogarithmic U give D ∼ ln ln n.The modulus bounds yield ln(q/√n) = Θ(ln n); the finite correction accounts for the separation between formal exponents in the ML-DSA rows.Source: E Finite-Parameter Substitutions · p. 100