# Gnarl-Hamadryad Lattice-based cryptographic library in Go. Post-quantum key generation, signatures, verification, key encapsulation, homomorphic encryption, multi-party computation, and searchable encryption - all built on hardness assumptions reducible to SVP/SIS on ideal lattices. ``` go get git.smesh.lol/gnarl-hamadryad ``` ## Post-Quantum Security Claims Hamadryad implements a complete lattice-based cryptographic stack - key generation, public key derivation, signatures, verification, and key encapsulation - built on Bethe lattice geometry with operations reducible to SVP/SIS hardness assumptions. The coordination-bounded tree structure directly models the norm propagation problem central to lattice-based signature aggregation: how to compose local lattice operations into global proofs without unbounded norm growth. The scheme exhibits additive homomorphism over hash outputs (Hamadryad.Sum, GnarlHash.Sum) and both additive and multiplicative homomorphism over ciphertexts (BGV HE with XOR/AND gates), enabling computation on encrypted data. ## Unified SVP Reduction All constructions in this library reduce to the Shortest Vector Problem on ideal lattices: ``` SVP on Ideal Lattices / | \ Ring-SIS Ring-LWE Ring-LWR / \ | \ \ SWIFFT Hash GPV KEM BGV HE Key Derivation / \ Sigs (CCA2) | \ Hamadryad Gnarl HEAdd HEMul Recognizer (Z_257) (Z_271) HEXOR HEAND (Searchable HENot Encryption) | Key Aggregation Distributed Decrypt Multi-Party Computation ``` Ring-SIS provides authentication (collision-resistant hashing, GPV signatures). Ring-LWE provides confidentiality (CCA2 KEM, BGV homomorphic encryption). Both reduce to SVP - breaking either requires finding short vectors in ideal lattices. ## Wire Formats and Binary Encodings All multi-byte integers are big-endian unless stated otherwise. Hash coefficient packing is little-endian bitwise. ### Hash Outputs #### Hamadryad - SWIFFT over Z\_257\[x\]/(x^64+1) | Field | Bits | Bytes | Encoding | |-------|------|-------|----------| | Full hash | 448 | 56 | 64 coefficients x 7 bits, LE bit-packed | | Shard | 48 | 6 | first 6 bytes of full hash | Coefficients are reduced mod 128 (= 2^7) from Z\_257. Packed little-endian bitwise: coefficient 0 occupies bits \[0:6\], coefficient 1 occupies bits \[7:13\], etc. The 448 bits fill 56 bytes exactly. #### Gnarl Hash - Trinary SWIFFT over Z\_271\[x\]/(x^27+1) | Field | Bits | Bytes | Encoding | |-------|------|-------|----------| | GnarlHash | 243 | 31 | 27 coefficients x 9 bits, LE bit-packed | | GnarlMid | 216 | 27 | 27 coefficients x 8 bits, direct byte map | | GnarlShard | 54 | 7 | 27 coefficients x 2 bits, LE bit-packed | **GnarlHash (243-bit):** Coefficients in \[0, 270\] packed 9 bits each, LE bitwise. Byte 30 has 5 spare bits (zeroed). **GnarlMid (216-bit):** Each coefficient reduced mod 243 (= 3^5) and stored as one byte. `out[i] = coeff[i] % 243`. Byte-aligned, no bit-packing. **GnarlShard (54-bit):** Each coefficient reduced mod 3, packed 2 bits each, LE bitwise. Byte 6 has 2 spare bits (zeroed). ### Gnarl Schnorr Signatures (216-bit prime) Scheme: Schnorr on the non-split torus of SL(2, Z\_P), P = 216-bit prime. Q = (P+1)/6, ~213-bit prime subgroup order. Field elements and scalars are serialized as 27 bytes big-endian. Internal representation is 4x uint64 little-endian limbs in Montgomery form (field) or plain form (scalars). The 27-byte encoding maps limbs to bytes as: ``` b[0:3] <- limb[3] low 24 bits (bits 192-215) b[3:11] <- limb[2] (bits 128-191) b[11:19] <- limb[1] (bits 64-127) b[19:27] <- limb[0] (bits 0-63) ``` | Object | Bytes | Layout | |--------|-------|--------| | Private key | 27 | scalar mod Q, BE | | Public key (compressed) | 27 | torus y-coordinate (y < P/3), BE | | Public key (full) | 81 | 3 field elements (a, b, d), each 27 bytes BE | | Signature | 54 | \[0:27\] challenge e (GnarlMid hash), \[27:54\] response z (scalar mod Q, BE) | ### Ring Polynomial Serialization Used by KEM, GPV, HE, and MPC for public keys, ciphertexts, and signatures. Each polynomial of n coefficients mod q is packed at ceil(log2(q)) bits per coefficient, little-endian bitwise: ``` bit position for coeff[i], bit b: bitPos = i * bitsPerCoeff + b byte index: bitPos / 8 bit within byte: bitPos % 8 ``` | Ring | n | q | Bits/coeff | Poly bytes | |------|---|---|------------|------------| | Falcon-512 | 512 | 12289 | 14 | 896 | | NewHope-256 | 256 | 7681 | 13 | 416 | | HE64 | 64 | 10000769 | 24 | 192 | ### KEM (Ring-LWE, CCA2) Default: Falcon-512 ring (n=512, q=12289). | Object | Components | Bytes (Falcon-512) | |--------|------------|-------------------| | Public key | polynomials A, B | 2 x 896 = 1792 | | Secret key | polynomial S + rejection value Z (32 bytes) + embedded PK | 896 + 32 + 1792 | | Ciphertext | polynomials U, V | 2 x 896 = 1792 | | Shared key | - | 32 | Message encoding (32 bytes = 256 bits into polynomial): - Bit 1 -> coefficient = floor(q/2) - Bit 0 -> coefficient = 0 - Decoding threshold: distance to q/2 < q/4 ### GPV Lattice Signatures (Ring-SIS) Default: Falcon-512 ring (n=512, q=12289). Gadget base 2, ceil(log2(q)) = 14 levels. | Object | Components | Bytes (Falcon-512) | |--------|------------|-------------------| | Public key | polynomials A, B | 2 x 896 = 1792 | | Secret key | trapdoor polynomial R + embedded PK | 896 + 1792 | | Signature | polynomials E1, E2 | 2 x 896 = 1792 | Verification: check `A*E1 + B*E2 = H(m) (mod q)` and `||E1||, ||E2||` are small. ### BGV Homomorphic Encryption Default: HE64 ring (n=64, q=10000769). | Object | Components | Bytes (HE64) | |--------|------------|-------------| | Ciphertext | polynomials U, V | 2 x 192 = 384 | | Relinearization key | L pairs of polynomials (A\_i, B\_i) | 2L x 192 | Plaintext space: binary (0 or 1). Depth-1 multiplicative circuits. ### GnarlWire Authenticated Encryption ChaCha20 + GnarlMid MAC. 64-byte header + variable ciphertext. ``` Offset Size Field ------ ---- ----- 0 10 Nonce (80-bit counter, LE) 10 27 Identity (GnarlMid of sender fingerprint) 37 27 Auth tag (GMid(mac_key || nonce || identity || ciphertext_hash)) 64 var Ciphertext (ChaCha20, keystream from block 1) ``` Total overhead: 64 bytes. Key derivation: Hamadryad hash -> 32-byte ChaCha20 key + 12-byte nonce. ### CTR Stream Cipher ChaCha20 in counter mode with random-access block generation. Block size: 64 bytes. | Field | Bytes | Source | |-------|-------|--------| | Key | 32 | derived from Hamadryad hash | | Nonce | 12 | derived from Hamadryad hash | | Block counter | 8 | uint64, increments per 64-byte block | ## Packages ### `crypto/` - Core hashing and wire protocol - **Hamadryad hash**: SWIFFT over Z\_257\[x\]/(x^64+1). 448-bit output (56 bytes). Additive homomorphism via `Sum()` (coefficient-wise mod 128). - **Gnarl hash**: Three-tier trinary SWIFFT over Z\_271\[x\]/(x^27+1). `GHash()` (243-bit/31 bytes), `GMid()` (216-bit/27 bytes), `GShard()` (54-bit/7 bytes). Additive `Sum()` (mod 271). - **GnarlWire**: Packet protocol using ChaCha20 + GnarlMid MAC. 64-byte header. `GnarlSeal()` / `GnarlOpen()`. - **CTR stream cipher**: ChaCha20 CTR mode with random-access block generation. Key derived from Hamadryad hash material. - **NTT**: Number Theoretic Transform for both rings (n=64/p=257 radix-2, n=27/p=271 radix-3). AVX2 acceleration on AMD64. ### `crypto/gnarl/` - Schnorr signatures over SL(2, Z\_P) Schnorr signature scheme on the non-split torus of SL(2, Z\_P) where P is a 216-bit prime. 27-byte keys, 54-byte signatures. Montgomery modular arithmetic with AMD64 assembly for critical-path multiplication. ~107-bit Pollard-rho security. ### `crypto/ring/` - Ring arithmetic, KEM, HE, MPC - **Ring arithmetic**: Polynomial operations over Z\_q\[x\]/(x^n+1) with NTT. Parameter sets: Falcon-512 (n=512, q=12289), NewHope-256 (n=256, q=7681), HE64 (n=64, q=10000769). - **KEM**: CCA2-secure key encapsulation via Fujisaki-Okamoto transform on Ring-LWE. 1792-byte keys and ciphertexts (Falcon-512). 32-byte shared key. - **GPV signatures**: Hash-and-sign with discrete Gaussian sampling. Ring-SIS hardness. 1792-byte signatures (Falcon-512). - **BGV Homomorphic Encryption**: Depth-1 multiplicative circuits over binary plaintext. `HEEncrypt`, `HEDecrypt`, `HEAdd`, `HEMul`, `HEXOR`, `HEAND`, `HENot`. - **Searchable encryption**: Homomorphic pattern matching via `Recognize()`. Evaluates circuits on encrypted data without decrypting. - **Anti-malleability**: 4-layer defense (rerandomize, noise flood, CCA2 session wrap, GPV sign). `WrapResult` / `VerifyResult`. - **Key aggregation**: Ring-LWE multi-party key aggregation. `AggregateHEKeys`, `GenerateSharedA`, `HEKeyGenWithA`, `PartialDecrypt`, `CombinePartialDecryptions`. - **MPC sessions**: Multi-party computation with session-bound anti-malleability. `NewMPCSession`, `Encrypt`, `XOR`, `AND`, `NOT`, `Verify`, `DecryptDistributed`. ### `ratio/` - Exact rational arithmetic GCD-normalized rationals with comparison and formatting. Used by `crypto/params.go` for noise width and smoothing parameters. ### `epoch/` - Crypto scheduling Binary/decimal phase synchronization for nonce rotation and key scheduling. Named epochs align walk lengths to power-of-two boundaries. ## Usage ### Hash ```go import "git.smesh.lol/gnarl-hamadryad/crypto" h := crypto.Hash([]byte("message")) // h is a 448-bit Hamadryad (SWIFFT) hash // Additive homomorphism: h1 := crypto.Hash([]byte("a")) h2 := crypto.Hash([]byte("b")) combined := h1.Sum(h2) // coefficient-wise addition mod 128 ``` ### KEM (CCA2) ```go import "git.smesh.lol/gnarl-hamadryad/crypto/ring" kp := ring.DefaultKEMParams() pk, sk := ring.KEMKeyGen(kp) ct, sharedKey := ring.Encapsulate(pk) recoveredKey := ring.Decapsulate(sk, ct) // sharedKey == recoveredKey ``` ### Homomorphic Encryption ```go kp := ring.DefaultHEParams() pk, sk, rlk := ring.HEKeyGen(kp) ct0 := ring.HEEncrypt(pk, 1) ct1 := ring.HEEncrypt(pk, 0) xored := ring.HEXOR(ct0, ct1) // encrypted 1 XOR 0 = 1 anded := ring.HEAND(ct0, ct1, rlk) // encrypted 1 AND 0 = 0 bit := ring.HEDecrypt(sk, xored) // 1 ``` ### Multi-Party Computation ```go kp := ring.DefaultHEParams() seed := []byte("common-reference-string") // Each party generates keys with shared A. a := ring.GenerateSharedA(kp, seed) pk1, sk1 := ring.HEKeyGenWithA(kp, a) pk2, sk2 := ring.HEKeyGenWithA(kp, a) // Create MPC session with aggregate key. sess, _ := ring.NewMPCSession( []*ring.KEMPublicKey{pk1, pk2}, nil, nil, nil, ) // Encrypt under aggregate key. ct := sess.Encrypt(1) // Homomorphic XOR with anti-malleability. result := sess.XOR(ct, sess.Encrypt(0)) if !sess.Verify(result) { panic("tampered") } // Distributed decryption: each party computes partial. d1 := ring.PartialDecrypt(sk1, result.Ciphertext) d2 := ring.PartialDecrypt(sk2, result.Ciphertext) plaintext := ring.DecryptDistributed(result.Ciphertext, []*ring.Poly{d1, d2}) // plaintext == 1 ``` ### GnarlWire (authenticated encryption) ```go import "git.smesh.lol/gnarl-hamadryad/crypto" key := crypto.Hash([]byte("shared-secret")) sealed := crypto.GnarlSeal(key, []byte("payload"), 0x01) payload, msgType, err := crypto.GnarlOpen(key, sealed) ``` ## Test ``` go test ./... go test -race ./... go test -bench=. ./crypto/ ./crypto/ring/ ``` ## License MIT