param-estimation

Lattice (LWE / RLWE / MLWE / NTRU)

Tooling

• lattice-estimator (public, a Sage library) is the default. Pin its commit in the project MANIFEST. Invocation:

  # sage -python est.py
  import sys; sys.path.insert(0, "/path/to/lattice-estimator")
  from estimator import LWE, ND, RC
  params = LWE.Parameters(n=1024, q=2**27, Xs=ND.UniformMod(3), Xe=ND.DiscreteGaussian(3.2), m=1024)
  r = LWE.estimate(params, red_cost_model=RC.MATZOV)       # full run
  r = LWE.estimate.rough(params)                            # fast core-SVP-style screen

  Sparse or ternary secrets use ND.SparseTernary(n_plus, n_minus, n). NTRU uses NTRU.Parameters / NTRU.estimate. Parse the output with crbench parse --parser lattice-estimator.

• Built-in core-SVP model (for quick screens and sanity): cost ≈ 0.292·β (classical sieve) or 0.265·β (quantum). β is the smallest block size meeting the GSA/uSVP success condition, with δ(β) = ((πβ)^{1/β} β / (2πe))^{1/(2(β−1))}. The lib/cryptomath lattice module provides this. Use it to screen; use the estimator for final numbers.

Protocol

1. Record the convention: estimator commit; cost model (RC.MATZOV, RC.BDGL16, RC.ADPS16...); secret distribution (dense ternary, sparse with weight h, uniform, Gaussian); error σ; number of samples m; how q is rounded. Round q up, which is the attacker-favourable and therefore conservative choice.
2. Model the real distribution. Check the library's actual secret sampler. For example, a library may default to a dense ternary secret with weight about n/2, or to a sparse one. The estimate must match what the code samples, not what the paper says.
3. Run all attacks (usvp, bdd, bdd_hybrid, bdd_mitm_hybrid, dual, dual_hybrid). Report the minimum, and name the attack that achieves it.
4. Non-power-of-two cyclotomics and structured rings. The estimator treats the instance as plain LWE. State that algebraic attacks (subfield attacks, overstretched NTRU, small-Galois-orbit structure) were considered separately, or were not.
5. Put one table per parameter set in EVIDENCE: n, log q, secret, σ, attack → log2(rop), β. Keep the raw JSON or log.

Pitfalls

• An NTRU "fatigue point" is not a modulus ceiling. The fatigue point is where the dense-sublattice attack becomes cheaper than key recovery. It is not where security collapses. The largest modulus still meeting a target security level can be much larger. Treating one as the other can underestimate usable parameters by many bits and can wrongly rule out whole designs. Always find the ceiling by running the estimator over a q-grid, and leave margin near any cliff where a new attack becomes applicable.
• Check the function shape, not just constants. When you claim a scaling law ("secure log q grows like f(N)"), fit it on at least four points. A wrong shape (logarithmic vs linear) is a bigger error than a wrong constant.
• Estimator performance patches. Some scripts need cache-size or laziness patches to handle very large n. Record each patch, and confirm the results on small n match the unpatched commit bit for bit.
• Module or matrix variants can be weaker than the circulant or ring version with the same dimension. Estimate them separately.
• Keys generated for the benchmark may use weaker parameters than the paper's headline. Compute the security of key-switching and bootstrapping keys too, since they sometimes use a smaller dimension or a larger modulus.
• Compare baselines at equal security. If your parameters give 118 bits and the baseline's give 128, the speed-up is not comparable. Re-parameterise one side.

Symmetric primitives

• Report the security margin as (rounds attacked by the best known distinguisher or key recovery) versus (full rounds). State the attack type (differential, linear, integral, algebraic, cube, MitM) and whether it is a distinguisher or key recovery.
• For FHE- or MPC-friendly ciphers, algebraic attacks (Gröbner, linearisation, interpolation, higher-order differentials) often dominate. Estimate the degree growth and the number of monomials, and use a published complexity formula with its citation.
• A "keystream looks random" test is not a security argument. Run vectorised distinguishers and algebraic-degree checks on the actual component (for example a whole-table S-box analysis) before claiming anything.
• Trail search: use SAT/MILP models (CryptoSMT, CaDiCaL, HiGHS). Report solver, version, time limit and whether the bound is proven optimal or only the best found.

MPC / PSI cost

• Report communication (bytes), rounds, and computation separately, for each party and for each phase (offline or pre-processing vs online).
• Simulate the network explicitly, for example LAN at 10 Gbit/s with 0.1 ms delay and WAN at 100 Mbit/s with 40 ms delay, using tc netem. State the settings.
• Match the security model (semi-honest or malicious; honest or dishonest majority), the statistical security parameter (for example 40) and the computational one (128).
• Check asymptotic cost formulas against measured traffic on at least two set sizes.

Output

A section in THEORY.md ("Parameters and security") plus EVIDENCE rows for each printed security level. Use scripts/core_svp_screen.py for a quick, dependency-free screen.