The nymph is the tree. The identity is the lattice. One hardness assumption binds every construction: the Shortest Vector Problem on ideal lattices. No component appeals to a different hard problem. No escape hatch into discrete logarithms, factoring, or graph-theoretic balance problems. SVP is the root system, and everything that grows from it inherits its hardness — including against quantum adversaries, where no subexponential algorithm is known.
Three capabilities emerge from this single root: hash, authenticate, encrypt. A fourth — homomorphic evaluation — is a controlled feature gated by session architecture. A fifth — proof of work — is SVP itself, performed literally.
Algebraic substrate: Rq = Zq[x] / (x^n + 1), the cyclotomic polynomial quotient ring. Every operation in the system is polynomial arithmetic in this ring. The NTT (finite-field Walsh-Hadamard transform) converts multiplication to pointwise Hadamard products. The butterfly decomposition is the recursive orthogonal splitting that the entire system breathes through.
All security claims in this system terminate at:
Given a lattice L ⊂ Z^n, find the shortest nonzero vector in L.
For ideal lattices (lattices corresponding to ideals in R_q), the best known algorithms are BKZ-family with cost 2^{Θ(n)} — exponential in the ring dimension. No quantum algorithm improves this beyond a polynomial factor (Grover speedup on the classical enumeration, at best). This is unlike RSA, DH, and ECDSA, which fall to Shor's algorithm in polynomial time.
The reduction chain for every phase:
Construction → Ring-SIS or Ring-LWE → worst-case SVP_γ on ideal lattices
Ring-SIS (Short Integer Solution): given random ai in Rq, find short z such that Σ ai · zi = 0 mod q. Hardness: if you can solve Ring-SIS with advantage ε, you can solve SVP_γ on any ideal lattice in R with comparable effort.
Ring-LWE (Learning With Errors): given (ai, bi = ai · s + ei), distinguish from uniform. Hardness: if you can solve Ring-LWE decision with advantage ε, you can solve SVP_γ on any ideal lattice in R with comparable effort.
These are the ONLY two intermediate problems. Everything else is a construction on top of one of them.
The substrate. No security claim of its own — this is the field in which all claims are planted.
All operations in Rq = Zq[x] / (x^n + 1) where n is a power of 2 (or 3^k for trinary variants) and q is chosen for NTT-friendliness.
multiplication via butterfly decomposition. Precompute roots of unity.
Parameter sets (each a different facet of the same ring family):
| Name | n | q | Use | Security |
|---|---|---|---|---|
| Falcon-512 | 512 | 12289 | Signatures | 128-bit |
| Falcon-1K | 1024 | 12289 | Signatures | 256-bit |
| NewHope | 256 | 7681 | KEM | 128-bit |
| Hamadryad | 64 | 257 | Hash (SWIFFT) | 128-bit |
| Gnarl | 27 | 271 | Hash (trinary) | 128-bit |
| HE-64 | 64 | 10000769 | Homomorphic evaluation | 128-bit |
The NTT IS the Hadamard structure: recursive sign-pattern decomposition converting convolution to pointwise product. For trinary rings (n=27), the radix-3 NTT uses cube roots of unity instead of square roots, but the butterfly principle is identical.
SVP binding: None directly. This is the algebraic ground.
Deliverable: ring/ package — polynomial type, NTT, pointwise multiply,
add, subtract, scalar multiply, serialize/deserialize.
The collision-resistant hash. The first security claim.
For the Hamadryad variant (n=64, q=257):
For the Gnarl variant (n=27, q=271):
SVP binding: Collision ↔ finding short z such that Az = 0 mod q. This IS Ring-SIS. Ring-SIS reduces to worst-case SVP_γ on ideal lattices in R. Finding a collision = solving SVP. The reduction is tight for γ = O(√(n log q)).
Deliverable: hamadryad/hash/ — SIS hash, streaming interface, domain
separation, shard extraction.
The precision instrument. Required for signatures (Phase 4) to achieve zero-knowledge — the sampler ensures signatures don't leak the secret basis.
Produces lattice vectors from a discrete Gaussian distribution D_{L,σ,c}: probability of sampling x proportional to exp(-π||x - c||² / σ²).
Implementation: FALCON's Fast Fourier sampler — O(n log n) via FFT over the reals, matching the NTT infrastructure.
Requirements:
fixed-point)
SVP binding: The sampler's statistical quality determines the tightness of the signature security reduction. If the sampler leaks information about the secret basis, the signature scheme's SVP reduction loosens. The smoothing parameter η_ε(L) — the Gaussian width above which the discrete Gaussian looks uniform modulo L — is directly computed from the lattice's shortest vectors.
Deliverable: hamadryad/sampler/ — discrete Gaussian over lattice cosets,
proven statistical distance bounds.
The authentication primitive. Identity asserts itself.
of the NTRU lattice. Public: h = g · f^{-1} mod q. The short basis is the trapdoor — knowing short vectors in the lattice.
basis + Gaussian sampler to find short (s₁, s₂) where s₁ + h·s₂ = t. The Gaussian sampling ensures (s₁, s₂) reveals nothing about B beyond the fact that a short basis exists.
norm bound β is public. Anyone can verify; only the basis holder can sign.
Alternative: Fiat-Shamir with Aborts (Lyubashevsky). Commit y ← Gaussian, challenge c = H(a·y, m) with sparse ternary coefficients, response z = y + s·c with rejection sampling. Slightly larger signatures, no need for trapdoor sampling.
SVP binding: Forging a signature = finding short (s₁, s₂) satisfying the linear relation WITHOUT the short basis. This IS Ring-SIS: finding a short preimage of t under the linear map [I | H]. Ring-SIS reduces to worst-case SVP_γ. Forgery = SVP.
Key recovery = finding the short basis of the NTRU lattice = approximate SVP on the NTRU lattice. Also SVP.
Both attack paths terminate at SVP.
Benchmark target: >1000 sign/sec, >5000 verify/sec on commodity hardware. Signature size: ~666 bytes (FALCON-512 equivalent).
Deliverable: hamadryad/sign/ — keygen, sign, verify. Constant-time.
The encryption primitive. Establishing shared secrets.
(u, v) = (a·r + e₁, b·r + e₂ + ⌊q/2⌋·m). Output ciphertext (u,v) and shared key K = H(m).
Re-encrypt (u', v'). If (u', v') = (u, v): return K = H(m'). Otherwise: return K = H(z || (u,v)) for random z in secret key. (Implicit rejection — no distinguishable failure.)
The re-encryption check is the Fujisaki-Okamoto transform. It converts IND-CPA (malleable) to IND-CCA2 (non-malleable) in the quantum random oracle model (QROM).
SVP binding: IND-CPA security ← Ring-LWE decision problem (distinguishing (a, a·s + e) from (a, u)). Ring-LWE decision reduces to worst-case SVP_γ. IND-CCA2 follows from IND-CPA + FO transform in QROM. The entire chain:
CCA2 ← FO(CPA) ← Ring-LWE ← SVP
Breaking the KEM = solving SVP.
Deliverable: hamadryad/kem/ — CPA core + FO-wrapped CCA2 KEM.
The controlled power. Computation on ciphertexts.
LWE ciphertexts are natively additive-homomorphic because the error terms add:
E(a) + E(b) = E(a + b) with noise ||ea|| + ||eb||
Multiplication requires relinearization (key-switching) and modulus switching to manage noise growth:
E(a) × E(b) = E(a · b) with noise ||ea|| · ||eb|| · poly(n)
Noise budget = log₂(q/noise). Each multiplication roughly doubles the noise bits. When noise exceeds q/2, decryption fails.
Levels:
Sufficient for bounded-depth circuits (pattern matching, recognition).
bootstrapping needed.
Expensive. Only when circuit depth is unknown at setup.
For the recognizer (Phase 8), SHE suffices — the matching circuit has bounded depth determined by pattern length × log(DFA states).
SVP binding: Semantic security of HE ciphertexts ← Ring-LWE ← SVP. The homomorphic operations preserve the LWE structure — each evaluated ciphertext is still an LWE instance with larger error. Security degrades gracefully with noise growth but never exits the LWE family. Breaking HE at any level = distinguishing LWE = solving SVP.
Deliverable: hamadryad/he/ — homomorphic add, multiply, relinearize,
modulus switch, circuit evaluator.
The homomorphism is power inside the session and vulnerability outside it. Every defense here inherits its hardness from the phases it composes.
Given ciphertext c encrypting m, produce c' = c + E(0) — add a fresh encryption of zero. Same plaintext, unlinkable ciphertext. Requires a public rerandomization key (encryption of zero under public key).
SVP binding: Unlinkability ← Ring-LWE (c' is fresh LWE instance) ← SVP.
After homomorphic evaluation, add noise exceeding the circuit noise by superpolynomial factor 2^{λ} (smudging lemma). The evaluator's choice of operations is statistically drowned.
SVP binding: Circuit privacy is information-theoretic given sufficient flooding. The underlying ciphertexts remain LWE instances ← SVP.
session. Malleable ciphertexts rejected at this layer by FO consistency.
Malleability is consensual — both parties explicitly enter the homomorphic regime.
homomorphic inner layer. Passive observers see CCA2 blobs.
SVP binding: Outer CCA2 ← FO + Ring-LWE ← SVP. Inner HE ← Ring-LWE ← SVP. Both layers, same anchor.
The evaluator proves they executed the agreed circuit. Lattice-based commitment scheme: commit to circuit description using Ring-SIS hash, reveal intermediate wire values with short openings.
SVP binding: Commitment binding ← Ring-SIS collision resistance ← SVP. Soundness of the proof ← same.
Deliverable: hamadryad/shield/ — rerandomization, noise flooding,
session wrapper, evaluation proofs.
The application layer. Encrypted pattern matching without decryption.
encrypted data, get encrypted boolean result
For regular expression matching: convert regex to DFA, encode DFA transition function as homomorphic lookup table. Circuit depth = input_length × log₂(states). Set SHE parameters to support this depth.
SVP binding: Inherits entirely from Phase 6 (HE security ← LWE ← SVP) and Phase 7c (session authentication ← KEM ← LWE ← SVP). The recognizer adds no new hardness assumption — it is a circuit evaluated on LWE ciphertexts.
Deliverable: hamadryad/search/ — encrypted index, homomorphic pattern
evaluator, PIR protocol.
Replaces any non-lattice accumulator. Identity is an iterated SIS hash chain — the hamadryad's growth rings.
the identity root.
reputation earned) is hashed into the chain:
acc0 = HSIS(pubkey) accn = HSIS(acc{n-1} || eventn)
Presenting acc_n requires proving knowledge of a signature chain back to acc_0, which requires the private key at genesis. You cannot transfer your history without transferring your secret basis.
each link. Each link is an SIS hash evaluation — O(1) per step.
membership of any event in O(log n) without revealing the full chain.
SVP binding: Chain integrity ← SIS collision resistance ← SVP. Finding a second preimage (forging history) = finding SIS collisions = solving SVP. Non-transferability ← signature unforgeability ← SIS ← SVP.
This is the hamadryad principle made explicit: the identity grows with the tree. The accumulator IS the tree's ring structure. Cutting the tree (extracting the secret basis) kills the nymph (invalidates all accumulated history bound to that key).
Deliverable: hamadryad/identity/ — accumulator chain, Merkle compaction,
membership proofs.
The consensus mechanism. The hard problem IS the work.
Traditional PoW: find x such that H(x) < target. The hardness is adjustable but the work is wasted — the hash preimage proves nothing about lattice structure.
SVP mining: find a short vector v in a challenge lattice L such that ||v|| ≤ β, where β is the difficulty target.
B is a public, pseudorandom lattice.
O(n²) — fast.
easier. The smoothing parameter of the lattice gives a natural lower bound.
The miner is literally solving SVP instances. The work is not wasted — it contributes to the empirical understanding of SVP hardness at the operational parameters. Every block mined is a data point about lattice security.
Sybil resistance: producing short vectors is expensive (BKZ enumeration / sieving). Verifying them is cheap (one multiply). Asymmetry ratio ≈ 2^n — better than hash-based PoW.
SVP binding: The proof of work IS SVP. Not reduces to. IS.
Deliverable: hamadryad/pow/ — challenge derivation, solver interface,
verification, difficulty adjustment.
Every component, one anchor:
SVP_γ (ideal lattices)
│
┌─────────────┴─────────────┐
│ │
Ring-SIS Ring-LWE
│ │
┌────────┼────────┐ ┌────────┼────────┐
│ │ │ │ │ │
Hash Sigs Accum KEM HE Session
(Ph.2) (Ph.4) (Ph.9) (Ph.5) (Ph.6) (Ph.7c)
│ │ │ │ │ │
│ │ │ │ ┌──┴──┐ │
│ │ │ │ Rerand Recog │
│ │ │ │ (7a) (Ph.8) │
│ │ │ │ │
└────────┴────────┴─────────┴────────┬────────┘
│
Verifiable Computation
(Ph.7d)
│
Commit ← SIS
│
SVP
Proof of Work (Ph.10) ═══ SVP directly
No node in this graph exits the SVP family. Every leaf, every branch, every internal node terminates at the same root.
All parameter choices flow from a single security target λ (e.g., 128-bit):
| Parameter | Meaning | Constraint |
|---|---|---|
| n | Ring dimension | 2^{⌈log₂(λ/δ)⌉} |
| q | Modulus | q ≡ 1 mod 2n, NTT-OK |
| σ | Gaussian width | σ ≥ η_ε(L) · √(ln(2n/ε)/π) |
| β_SIS | SIS norm bound | β < q / poly(n) |
| β_LWE | LWE error bound | β · √n < q/4 |
| β_PoW | Mining difficulty | β ∈ [λ_1(L), √n · q] |
| depth | HE circuit depth | log₂(q/β_LWE) / log₂(n) |
| γ | SVP approximation factor | γ = O(√(n · log q)) |
The lattice estimator (https://github.com/malb/lattice-estimator) validates concrete choices against BKZ, primal, dual, and hybrid attacks. Run it for every parameter set. No exceptions.
The nymph does not inhabit the tree. The nymph IS the tree. If you uproot the tree, the nymph dies — not because the nymph was hiding inside, but because they were the same entity viewed from different angles.
In this cryptosystem:
IN the lattice — it IS the lattice's hidden geometric structure.
encode a message — it IS the message crystallized into the lattice's geometry.
history — it IS the identity's growth rings, inseparable from the key.
not prove computation — it IS computation on the hard problem itself.
data — it IS data embedded in the lattice's error distribution.
Every component is a different projection of the same mathematical object. The Hadamard structure (NTT butterfly decomposition) is the lens that transforms between these projections — the same way the Hadamard gate creates superposition between |0⟩ and |1⟩, the NTT creates correspondence between coefficient space (where secrets live) and evaluation space (where multiplication is cheap).
The security of the entire system is the security of SVP. If SVP falls, everything falls simultaneously — but SVP falling would require a breakthrough in the geometry of numbers that has resisted three centuries of effort (Minkowski 1896 → Ajtai 1996 → present). The lattice does not have a weak point because it has no joints. It is one piece.
The megalith does not need mortar. The arrangement is the structure.