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

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)

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

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

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)

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

README.md raw