# Hamadryad Cryptosystem — Unified SVP Architecture 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: R_q = Z_q[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. ## The SVP Anchor 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 a_i in R_q, find short z such that Σ a_i · z_i = 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 (a_i, b_i = a_i · s + e_i), 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. ## Phase 1: Ring Arithmetic Engine The substrate. No security claim of its own — this is the field in which all claims are planted. All operations in R_q = Z_q[x] / (x^n + 1) where n is a power of 2 (or 3^k for trinary variants) and q is chosen for NTT-friendliness. - Polynomial representation: coefficient arrays in Montgomery form - Number-Theoretic Transform: forward and inverse, O(n log n) polynomial multiplication via butterfly decomposition. Precompute roots of unity. - Barrett/Montgomery reduction for modular arithmetic - Constant-time operations throughout — no branching on secrets 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. ## Phase 2: Hamadryad Hash (Ring-SIS) The collision-resistant hash. The first security claim. - Public matrix A ∈ R_q^{k×l} (ring-SIS instance) - Hash: f(x) = Ax mod q for short input x - Output: k ring elements, serialized to fixed-length bytes For the Hamadryad variant (n=64, q=257): - Input: 1024 bits (128 bytes), interpreted as 16 short polynomials - Output: 7 polynomials × 64 coefficients × 7 bits = 448 bits (56 bytes) - Merkle-Damgård extension for arbitrary-length messages For the Gnarl variant (n=27, q=271): - Input: binary, packed into trinary polynomials - Output tiers: 243-bit canonical, 216-bit packet, 54-bit shard - Precomputed basis tables eliminate forward NTT for binary inputs **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. ## Phase 3: Gaussian Sampler 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: - Floating-point with sufficient precision (53-bit double or 64-bit fixed-point) - Constant-time conditional moves - Statistical distance from true Gaussian ≤ 2^{-128} **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. ## Phase 4: Signatures (GPV Hash-and-Sign) The authentication primitive. Identity asserts itself. - **KeyGen**: Generate NTRU-type key pair. Secret: short basis B = {f, g} of the NTRU lattice. Public: h = g · f^{-1} mod q. The short basis is the trapdoor — knowing short vectors in the lattice. - **Sign**: Hash message m to target t = H(m) in R_q. Use secret short 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. - **Verify**: Check s₁ + h·s₂ = t mod q AND ||(s₁, s₂)|| ≤ β. The 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. ## Phase 5: Key Encapsulation (Ring-LWE + Fujisaki-Okamoto) The encryption primitive. Establishing shared secrets. - **KeyGen**: s ← small, e ← small, public key (a, b = a·s + e) - **Encapsulate**: sample message m, derive coins r = H(m), compute (u, v) = (a·r + e₁, b·r + e₂ + ⌊q/2⌋·m). Output ciphertext (u,v) and shared key K = H(m). - **Decapsulate**: Compute m' = Round(v - s·u). Re-derive r' = 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. ## Phase 6: Homomorphic Evaluation 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 ||e_a|| + ||e_b|| Multiplication requires relinearization (key-switching) and modulus switching to manage noise growth: E(a) × E(b) = E(a · b) with noise ||e_a|| · ||e_b|| · poly(n) Noise budget = log₂(q/noise). Each multiplication roughly doubles the noise bits. When noise exceeds q/2, decryption fails. Levels: 1. **Somewhat Homomorphic (SHE)**: fixed depth before noise overflow. Sufficient for bounded-depth circuits (pattern matching, recognition). 2. **Leveled FHE**: set parameters for known circuit depth. No bootstrapping needed. 3. **Full FHE**: bootstrapping refreshes noise. Unlimited depth. 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. ## Phase 7: Anti-Malleability Architecture The homomorphism is power inside the session and vulnerability outside it. Every defense here inherits its hardness from the phases it composes. ### 7a. Rerandomization 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. ### 7b. Noise Flooding (Circuit Privacy) 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. ### 7c. Session Architecture - **Outer layer**: CCA2-secure KEM (Phase 5) establishes authenticated session. Malleable ciphertexts rejected at this layer by FO consistency. - **Inner layer**: Homomorphic evaluation channel, keyed to session. Malleability is consensual — both parties explicitly enter the homomorphic regime. - **Access control**: Only authenticated session participants see the 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. ### 7d. Verifiable Computation 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. ## Phase 8: Searchable Encryption (The Recognizer) The application layer. Encrypted pattern matching without decryption. - **Index**: Encrypt each token/n-gram homomorphically (Phase 6) - **Query**: Encrypt search pattern, evaluate matching circuit on encrypted data, get encrypted boolean result - **Reveal**: Only the querier (holding session key) decrypts the match 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. ## Phase 9: Identity Accumulation Replaces any non-lattice accumulator. Identity is an iterated SIS hash chain — the hamadryad's growth rings. - **Genesis**: Generate lattice key pair (Phase 4). The public key is the identity root. - **Accumulation**: Each event (signature issued, session established, reputation earned) is hashed into the chain: acc_0 = H_SIS(pubkey) acc_n = H_SIS(acc_{n-1} || event_n) - **Non-transferability**: The accumulator is bound to the key pair. 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. - **Verification**: Given acc_n and a proof (the hash chain), verify each link. Each link is an SIS hash evaluation — O(1) per step. - **Compaction**: Merkle tree over the chain using SIS hash. Prove 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. ## Phase 10: Proof of Work (SVP Mining) 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. - **Challenge**: Derive lattice basis B from block header using SIS hash. B is a public, pseudorandom lattice. - **Solution**: A short vector v in L(B) with ||v|| ≤ β. - **Verification**: Check Bx = v for short x. One matrix-vector multiply. O(n²) — fast. - **Difficulty**: Decrease β to make mining harder. Increase β to make it 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. ## Reduction Diagram 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. ## Parameter Unification 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 Hamadryad Principle 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: - The **private key** is a short basis of the lattice. It is not stored IN the lattice — it IS the lattice's hidden geometric structure. - The **signature** is a short vector found using that basis. It does not encode a message — it IS the message crystallized into the lattice's geometry. - The **accumulator** is an iterated hash chain. It does not record history — it IS the identity's growth rings, inseparable from the key. - The **proof of work** is a short vector in a challenge lattice. It does not prove computation — it IS computation on the hard problem itself. - The **homomorphic ciphertext** is an LWE instance. It does not contain 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.