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
           /      \    /   \   (CCA2)  |   \
     Hamadryad  Gnarl Lyub  MP12  HEAdd  HEMul  Recognizer
     (Z_257)    (Z_271) Sigs  Gadget HEXOR  HEAND  (Searchable
                         |     Sigs  HENot        Encryption)
                         |      |                    |
                   Sigma Proof  |            Key Aggregation
                   (ZK Layer)   |            Distributed Decrypt
                         |      |            Multi-Party Computation
                    Randomized  |
                    Sig Proof   |
                         \      /
                   ZK Credential Layer

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)

Variable-Width Ring Polynomial Serialization

Polynomials with bounded coefficients can be packed at reduced width to save space.

Encoder	Width	Signed	Use
`Serialize` (default)	`ceil(log2(Q))`	no	KEM, HE, GPV keys and sigs
`SerializeBounded` (variable)	caller-specified	yes	sigma protocol responses, compressed proofs

SerializeBounded uses the same LE bitwise order as Serialize but truncates to bitsPerCoeff bits. Signed coefficients are stored in two's complement at the given width. For a Gaussian response with bound B, use bitsPerCoeff = ceil(log2(B)) + 1 to cover the signed range.

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.

Two signing paradigms available:

Lyubashevsky Fiat-Shamir with Aborts (gpv.go): sigma-protocol-derived signature. Rejection-sampled response: z = y + r·c, verify A·z + B·c = w and c = H(w, m).

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.

MP12 Gadget-Trapdoor GPV (gpv_gadget.go): proper hash-then-sign trapdoor preimage. Uses ℓ-component gadget vector B[i] = -A·R[i] + base^i with Gaussian perturbation. Signing: E2 = GadgetDecompose(t - A·p, base), E1 = p + Σ R[i]·E2[i].

Object	Components	Bytes (Falcon-512, base=2)
Public key	polynomial A + ℓ polys B[i]	(1+ℓ) x 896
Secret key	ℓ short trapdoor polys R[i]	ℓ x 896
Signature	polynomial E1 + ℓ digit polys E2[i]	(1+ℓ) x 896

ℓ = ceil(log_base(q)). For Falcon-512 with base=2, ℓ=14 → ~13 KB public key, ~1700 B compressed signature. Acceptable for enterprise/government deployments with 10-100 counterparties. Switching to base-4 gives ℓ=7 (~7 KB PK). The Falcon NTRU path (~700 B PK, ~700 B sig) is tracked as follow-up work. The gadget decomposition is unsigned: each E2[i] coefficient is in [0, base). Verification: A·E1 + Σ B[i]·E2[i] = H(m) and digit norm bounds.

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, signatures, ZKP

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 (Lyubashevsky): Fiat-Shamir with Aborts. Rejection-sampled sigma protocol turned into a signature. GPVKeyGen, GPVSign, GPVVerify. ~1600 B compressed.
MP12 gadget GPV signatures (gpv_gadget.go): Proper hash-then-sign trapdoor preimage GPV. Uses ℓ-component gadget vector B[i] = -A·R[i] + base^i. GPVGadgetKeyGen, GPVGadgetSign, GPVGadgetVerify. GadgetDecompose splits a polynomial into base-b digit polynomials.
Variable-width serializer (vwidth.go): SerializeBounded / DeserializeBounded pack polynomial coefficients at caller-specified bit width. Signed two's complement or unsigned. Same LE bitwise order as Serialize.
Interactive sigma protocol (sigma.go): Commit generates w = A·y for Gaussian y. Challenge generates random short (±1) challenge. Respond computes z = y + r·c with rejection sampling. VerifyInteractive checks A·z + B·c = w and norm bound.
Non-interactive (Fiat-Shamir) proof (sigma.go): Prove/VerifySigma generate and verify a proof of GPV secret key knowledge. MarshalSigmaProof/UnmarshalSigmaProof serialize with compressed challenge (position-sign pairs) and bounded response. ~800 B proof size.
Randomized GPV signature proof (sigma.go): RandomizeGPVSignature hides the signature response z by additive Gaussian randomization z' = z + r_m, producing C = A·r_m as commitment. VerifyRandomizedGPVSignature recovers the original commitment and checks the Fiat-Shamir challenge. Works with any ring size. ~900 B proof size.
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)

MP12 Gadget GPV Signature (hash-then-sign trapdoor)

import "git.smesh.lol/gnarl-hamadryad/crypto/ring"

gp := ring.DefaultGPVParams()          // Falcon-512, ℓ=14
pk, sk := ring.GPVGadgetKeyGen(gp)

msg := []byte("post-quantum message")
sig := ring.GPVGadgetSign(sk, msg)

if !ring.GPVGadgetVerify(pk, msg, sig) {
    panic("signature rejected")
}

// Gadget decomposition (standalone utility):
digits := ring.GadgetDecompose(poly, 2)
for _, d := range digits {
    // d has coefficients in {0, 1} for base=2
}

Sigma Protocol (interactive proof of key knowledge)

gp := ring.SmallGPVParams()
pk, sk := ring.GPVKeyGen(gp)

rng := rand.Reader

// Prover commits.
w, y := ring.Commit(pk, rng)

// Verifier challenges.
c := ring.Challenge(gp.Ring, rng)

// Prover responds (retry if rejection sampling fails).
z, ok := ring.Respond(sk, y, c)
if !ok {
    // w and y must be discarded — start a fresh commitment
}

// Verifier checks.
if !ring.VerifyInteractive(pk, w, c, z) {
    panic("proof rejected")
}

Non-Interactive Proof (Fiat-Shamir)

gp := ring.SmallGPVParams()
pk, sk := ring.GPVKeyGen(gp)

// Prover generates proof (no verifier interaction needed).
proof := ring.Prove(sk, nil)

// Verifier checks.
if !ring.VerifySigma(pk, nil, proof) {
    panic("proof rejected")
}

// Serialize for transport.
data := ring.MarshalSigmaProof(proof)

// Deserialize on the receiving end.
restored := ring.UnmarshalSigmaProof(gp.Ring, data)

Randomized GPV Signature (signature-hiding proof)

gp := ring.DefaultGPVParams()           // Falcon-512
pk, sk := ring.GPVKeyGen(gp)

msg := []byte("age>=18")
sig := ring.GPVSign(sk, msg)

rng := rand.Reader

// Prover randomizes the signature — hides z from verifier.
proof := ring.RandomizeGPVSignature(pk, sig, msg, rng)

// Verifier checks without learning the original signature.
if !ring.VerifyRandomizedGPVSignature(pk, msg, proof) {
    panic("randomized signature rejected")
}

// Each randomization produces a different z' — unlinkable.
proof2 := ring.RandomizeGPVSignature(pk, sig, msg, rng)
// proof.ZPrime != proof2.ZPrime

Test

go test ./...
go test -race ./...
go test -bench=. ./crypto/ ./crypto/ring/

License

MIT

gnarl-hamadryad