These are the foundations. Everything reduces to one of these being hard to solve.
Finding the shortest non-zero vector in a lattice. Given a basis, find the vector with minimum Euclidean norm. This is the bedrock. No known polynomial-time quantum algorithm solves it — unlike factoring (RSA) or discrete log (ECDSA), which Shor's algorithm breaks.
Say: "The security of this construction reduces to SVP hardness."
Given a lattice and a target point NOT on the lattice, find the nearest lattice point. Decryption in many schemes is "noisy CVP" — encryption adds noise, the secret key lets you round back to the correct point.
Say: "Decryption reduces to solving CVP with the secret basis."
Given noisy linear equations over a finite field, recover the secret. Formally: given (aᵢ, bᵢ) where bᵢ = ⟨aᵢ, s⟩ + eᵢ (mod q), find s. The noise eᵢ is what makes it hard. Without noise, it's linear algebra.
LWE reduces to worst-case SVP — breaking LWE means breaking SVP on ANY lattice.
Parameters:
Say: "LWE gives us a worst-case to average-case reduction, which is why lattice crypto has the strongest theoretical foundations of any PQ family."
LWE in a polynomial ring Rq = Zq[x]/(x^n + 1) where n is a power of 2. Polynomial multiplication replaces matrix multiplication. Keys and ciphertexts get much smaller.
Trade-off: Ring structure might enable algebraic attacks that don't apply to plain LWE. No known practical exploit, but it's an active research area.
Say: "RLWE gives us practical efficiency while the best known attacks still reduce to SVP."
Small matrices of ring elements. Hybrid between unstructured LWE/SIS and fully structured RLWE. This is what the NIST standards actually use. Tunable security/efficiency trade-off.
Say: "Module-LWE is the sweet spot — more structure than plain LWE for performance, less than Ring-LWE for conservative security margins."
Given random matrix A, find short non-zero x such that Ax = 0 (mod q). Basis for hash functions and signature schemes. The "short" constraint is what makes it hard.
CRITICAL PROPERTY FOR YOUR PROPOSAL: SIS is linear. If Ax₁ = 0 and Ax₂ = 0, then A(x₁ + x₂) = 0. But x₁ + x₂ may no longer be "short." This norm growth under addition is THE central problem in signature aggregation.
Say: "SIS linearity gives us a natural aggregation path, but bounding norm growth through the aggregation tree is the core unsolved challenge."
Know these cold. Name, purpose, underlying problem, and status.
Say: "FALCON gives us the best verification efficiency and smallest bandwidth, which is why it's the leading candidate for on-chain PQ signatures. But the signing complexity and NTRU-specific structure create challenges for aggregation that Module-SIS schemes might handle more naturally."
The finite-field analogue of the Fast Fourier Transform. Converts polynomial multiplication from O(n²) to O(n log n). This is THE performance bottleneck for all lattice schemes on EVM.
How it works: Transform polynomials into "evaluation form" (NTT domain), multiply pointwise, transform back (inverse NTT). Requires the modulus q to support n-th roots of unity (q ≡ 1 mod 2n).
EVM context: ZKnox's entire optimisation story is NTT in Yul. EIP-7885 proposes NTT as a native precompile.
Say: "NTT is the critical path for on-chain lattice verification. The question is whether to optimise it in the EVM, add it as a precompile, or move verification into a ZK circuit where the cost profile inverts."
Many lattice operations require sampling vectors from a Gaussian distribution over a lattice. FALCON signing requires this (GPV framework). It's computationally expensive and tricky to implement securely (timing side-channels).
Say: "Gaussian sampling is what makes FALCON signing hard to implement in constrained environments, but verification doesn't require it — which is why the on-chain story focuses on verification."
RLWE and FALCON operate in Z_q[x]/(x^n + 1). The polynomial x^n + 1 (where n is power of 2) is the 2n-th cyclotomic polynomial. It's irreducible over the integers, which gives the ring nice algebraic properties.
Say: "The cyclotomic structure is what enables NTT — we need roots of unity in Z_q for the transform to work efficiently."
A lattice is a discrete subgroup of R^n. A basis is a set of vectors that generates the lattice via integer linear combinations. Different bases generate the same lattice but have different "quality" — short, nearly orthogonal bases are "good" (and secret), long, skewed bases are "bad" (and public).
Basis reduction algorithms: LLL (polynomial time, finds somewhat short vectors), BKZ (better quality, exponential in block size). These are the attacker's tools. Security parameters are chosen so that BKZ can't find short enough vectors in feasible time.
Say: "Security parameter selection comes down to the BKZ block size required to break the scheme — we target at least 128 bits of security, meaning BKZ with block size ~400+ is needed."
FALCON uses a specific lattice family different from Module-LWE. In NTRU, the public key h = g/f (mod q) in the polynomial ring, where f and g are short polynomials. The secret key is the short basis of the NTRU lattice generated by (f, g).
Key difference from LWE: NTRU is older (1996), well-studied, but the algebraic structure is different from Module-LWE. This matters for aggregation because the aggregation properties of NTRU-based signatures differ from SIS-based ones.
The theoretical framework for "hash-then-sign" lattice signatures. FALCON is a concrete instantiation. You hash the message to a point, then use the secret short basis to find a nearby lattice point (solving CVP). The signature IS the short vector.
Say: "FALCON instantiates the GPV framework over NTRU lattices, which gives compact signatures but ties us to NTRU-specific algebraic structure."
Ethereum consensus requires ~30,000 validator signatures per slot (12 seconds). Today: BLS signatures with bilinear pairings — aggregate all signatures into one, verify once. Post-quantum: no PQ scheme has this property natively.
Naive batching in ZK: Prove "I verified N signatures" inside a ZK circuit (leanVM), post one proof on-chain. Works but the circuit size scales linearly with N. Expensive proving time.
SIS-based linear aggregation: If signatures are SIS solutions (short vectors x where Ax = 0), you can add them: xagg = x₁ + x₂ + ... + xN. The problem: ‖xagg‖ grows as √N (if independent) or linearly (worst case). After enough additions, xagg is no longer "short" — the verification bound is exceeded.
Tree-structured aggregation: Instead of summing all N signatures at once, aggregate pairwise in a tree. At each level, aggregate two signatures and "re-sign" or compress to control norm growth. This is where Bethe lattice structure becomes relevant — the tree has fixed coordination number, and you need bounded propagation at each level.
Rogue key attacks: When aggregating, an adversary who sees others' public keys can choose their own key to cancel others out. Mitigations: proof of possession, key aggregation protocols. This is a known issue from BLS aggregation that carries over.
The question is whether SIS-based signatures can be designed so that tree-structured aggregation keeps the norm below the verification bound at every level of the tree, without requiring a full ZK proof at each node. If yes, you get "native" aggregation cheaper than naive ZK batching. If the norm bound is tight enough, the aggregation tree depth gives you a parameter: deeper tree = more signatures aggregated, but each level costs norm budget.
Say: "I'm investigating whether Bethe-lattice-structured aggregation over SIS-based signatures can bound norm growth tightly enough to avoid the linear proving cost of naive batched ZK verification."
Minimalist ZK virtual machine optimised for hash-based (and lattice-based) PQ signature verification. Not the EVM. A separate proving environment where you execute the verification off-chain and produce a succinct proof that the EVM can cheaply verify.
Why it exists: PQ signature verification is too expensive for the EVM even with precompiles. Move the heavy computation off-chain, verify a proof on-chain.
Say: "leanVM changes the cost model — operations that are expensive in the EVM (polynomial arithmetic) can be cheap in a ZK circuit, while operations cheap in the EVM (hashing) become expensive in ZK. The optimal PQ scheme for leanVM may differ from the optimal scheme for raw EVM execution."
Proposed by ZKnox. Add the Number Theoretic Transform as a native EVM operation. Would drop FALCON verification costs from ~2M gas to an estimated ~500K. Also benefits Dilithium and any future lattice scheme.
Status: Proposed, not scheduled for any fork yet. The strawmap doesn't mention it explicitly but EVM cryptographic precompiles are on the Glamsterdam/Hegotá track.
ZKnox's EVM-optimised variants. Key modifications from NIST standards:
Say: "ETHFALCON demonstrates that the standard needs adaptation for on-chain contexts. The question is whether leanVM changes those trade-offs again."
Smart contract wallets that can use any signature scheme, not just ECDSA. This is the migration path for PQ: users upgrade their wallet contract to verify PQ signatures instead of ECDSA, without changing their address.
Say: "Account abstraction is what makes the PQ migration non-breaking — users switch signature schemes without changing addresses."
Current Ethereum consensus uses BLS12-381 curve for validator signatures. Key property: bilinear pairing enables aggregation. Given signatures σ₁...σₙ on messages m₁...mₙ, the aggregate σ_agg = σ₁ + ... + σₙ can be verified with n pairings (or 1 if same message). This is what we lose going post-quantum.
Say: "BLS aggregation is essentially free because of the bilinear map. No PQ construction has an equivalent. That's the fundamental gap."
Ethereum needs to replace SNARK-based components with STARK-based ones. This is parallel to replacing ECDSA with PQ signatures. leanVM is designed for STARK-friendly computation.
Say: "The proof system transition from SNARKs to STARKs is the ZK side of the same PQ migration. leanVM targets STARK-friendly verification."
When discussing specific parameter sets, these are the standard names:
| Scheme | Security Level | NIST Level | Name |
|---|---|---|---|
| ML-KEM | 128-bit | 1 | ML-KEM-512 |
| ML-KEM | 192-bit | 3 | ML-KEM-768 |
| ML-KEM | 256-bit | 5 | ML-KEM-1024 |
| ML-DSA | 128-bit | 2 | ML-DSA-44 |
| ML-DSA | 192-bit | 3 | ML-DSA-65 |
| ML-DSA | 256-bit | 5 | ML-DSA-87 |
| FALCON | 128-bit | 1 | FALCON-512 |
| FALCON | 256-bit | 5 | FALCON-1024 |
NIST Security Levels:
Say: "For Ethereum consensus, Level 1 (128-bit) is the target — matching current BLS12-381 security."
Critical for the EVM/gas cost argument:
| Scheme | Public Key | Signature | Verify Speed |
|---|---|---|---|
| ECDSA (current) | 33 bytes | 64 bytes | ~3,000 gas |
| BLS12-381 (consensus) | 48 bytes | 96 bytes | ~180,000 gas |
| FALCON-512 | 897 bytes | 666 bytes | ~2M gas (ZKnox) |
| ML-DSA-44 | 1,312 bytes | 2,420 bytes | ~6M gas (est.) |
| SLH-DSA-128s | 32 bytes | 7,856 bytes | very expensive |
The bandwidth problem: PQ signatures are 10-40x larger than ECDSA. For 30,000 validators per slot, this is ~20MB of signatures alone (FALCON) vs ~2MB (BLS). Aggregation doesn't just save gas — it saves network bandwidth.
Say: "The bandwidth multiplier from PQ signatures makes aggregation not optional but existential for Ethereum consensus."
Use these terms precisely.
The length of a vector. Usually Euclidean (L2) norm: ‖x‖ = √(Σxᵢ²). Sometimes infinity norm: ‖x‖∞ = max|xᵢ|. Security bounds are stated in terms of norms.
A signature is valid if the vector is shorter than a threshold β. During aggregation, the combined vector's norm must stay below β. This is why aggregation is hard.
The standard deviation of the discrete Gaussian distribution used in sampling. Larger = easier to sample, weaker security. Smaller = harder to sample, stronger security.
For lattice Λ, the dual Λ* contains all vectors whose inner product with any lattice vector is an integer. Dual lattices appear in LWE security proofs and some constructions.
A lattice defined modulo q. Most cryptographic lattices are q-ary: Λ_q(A) = {x : Ax = 0 mod q}. SIS solutions live in this lattice.
Dimension = the ambient space R^n. Rank = number of basis vectors. A full-rank lattice has rank = dimension. Cryptographic lattices are usually full-rank.
Quantum algorithm that breaks factoring and discrete log in polynomial time. This is WHY we need PQ crypto. Does NOT break lattice problems.
Say: "Shor breaks RSA, ECDSA, and BLS. Lattice problems survive because there's no known quantum speedup beyond the classical-to-quantum polynomial overhead."
Quantum algorithm that searches unsorted databases in √N time. Halves the security of symmetric ciphers (AES-128 → 64-bit quantum security). For lattice schemes, the impact is minor — mostly just motivates slightly larger parameters.
Polynomial-time lattice basis reduction. Finds "somewhat short" vectors. The starting point for lattice attacks but doesn't break modern parameters.
Better lattice reduction. Parameterised by block size β. Larger β = shorter vectors found, but exponential cost. Security parameters are chosen so that the required β is infeasible.
Say: "We set parameters so the required BKZ block size for an attack exceeds 400, which corresponds to roughly 2^128 operations."
Two main attack strategies against LWE:
The better of these two determines the concrete security level.
| Wrong | Right |
|---|---|
| "Post-quantum Diffie-Hellman" | "Key Encapsulation Mechanism" (KEM) |
| "Kyber" | "ML-KEM" (Kyber was the competition name) |
| "Dilithium" | "ML-DSA" (same reason) |
| "SPHINCS+" | "SLH-DSA" (same reason) |
| "FALCON" | Still "FALCON" until FIPS 206 publishes, then "FN-DSA" |
| "Lattice-based encryption" | "Lattice-based KEM" (for key exchange) |
| "Zero-knowledge proof" (generic) | Specify: "SNARK" or "STARK" or "ZK circuit" |
| "Hash" (vague) | Specify: "Keccak", "Poseidon", "SHAKE", "SHA-3" |
| "Private key" | Fine, but "secret key" is more standard in PQ literature |
| "Homomorphic" | Specify: "additively homomorphic" or "fully homomorphic (FHE)" |
| "Aggregation" | Specify: "signature aggregation" vs "key aggregation" |
| "Torus" | In crypto context: T = R/Z (reals mod 1). Used in TFHE. Not the geometric donut. |
The real numbers modulo 1. Elements are in [0, 1) with wraparound arithmetic. TFHE (Fully Homomorphic Encryption) represents ciphertexts as elements of the torus, which gives natural modular arithmetic properties.
LWE but with the secret and noise on the torus. Used in TFHE. If someone asks about your FHE knowledge, this is the connection point to lattice crypto.
Different applications of lattice hardness. TFHE uses lattice problems for computation on encrypted data. PQ signatures use lattice problems for authentication. Same mathematical foundation, different constructions.
Say: "Both TFHE and PQ signatures reduce to lattice hardness, but the construction goals differ — TFHE optimises for homomorphic operations, signatures optimise for compact verification."
FALCON compresses signatures by encoding polynomial coefficients more compactly. Standard FALCON saves ~30% but uses bitwise operations expensive on EVM. ETHFALCON skips compression, accepts larger signatures for lower gas.
ZKnox packs 16 coefficients of 16 bits into a single EVM word (uint256). This minimises storage operations. The packing/unpacking between compact and expanded representation is handled by NTT helper functions.
Dilithium includes "hints" in signatures — information that lets the verifier reconstruct values without recomputing them. This is the "h" vector in ML-DSA. It's essentially a compression technique for the verification equation.
Say: "There's a tension between NIST standard encoding and EVM-optimal encoding. For consensus, we need a canonical format that all clients agree on."
Use these naturally. Don't recite — absorb.
On security: "The reduction from Module-LWE to worst-case lattice problems is what gives us confidence that no quantum algorithm will break this — unlike the structured number theory problems that Shor exploits."
On FALCON vs Dilithium: "FALCON wins on bandwidth and verification cost, which matters most for on-chain. Dilithium wins on implementation simplicity and hardware support. The consensus layer probably wants FALCON for efficiency; the wallet layer might prefer Dilithium for ecosystem compatibility."
On aggregation: "BLS gives us aggregation for free via the bilinear map. In the lattice world, SIS linearity gives us a starting point, but norm growth under addition is the fundamental constraint. Tree-structured aggregation with bounded depth is the most promising approach to keep norms within the verification bound."
On leanVM: "The cost model inverts between EVM and ZK. Polynomial arithmetic is expensive on EVM but native in ZK circuits. Hashing is cheap on EVM but expensive in ZK. This means the optimal PQ scheme for leanVM verification may differ from the optimal scheme for raw EVM execution."
On your proposal: "I'm investigating whether Bethe-lattice-structured aggregation over SIS-based signatures can achieve sub-linear proving cost compared to naive batched verification in leanVM, by exploiting the linearity of SIS and controlling norm propagation through bounded-degree tree composition."
On the urgency: "Vitalik puts 20% probability on Q-day before 2030. The migration timeline for a network with millions of wallets is measured in years, not months. The time to build is now."