One ring, one tree, two primitives. The gnarl ring (n=27, q=271) delivers both a compact lattice signature and a group messaging protocol from the same algebraic substrate. No separate KEM, no separate signature scheme, no separate tree protocol. SIS short vectors for signing. The same ring structure for group coordination. One serialization format, one verification equation, one trust model.
SVP on Ideal Lattices
|
Ring-SIS / Ring-LWE
/ \
NTRU Signature Group Protocol
(43 bytes) (27-ary tree)
/ \ / | \
Compact PQ Single PQ PCS Consensus
individual verifier MLS +FS by norm
Ring: R = Z_271[x]/(x^27+1), n=27=3^3, q=271 prime.
NTT: radix-3 negacyclic. Primitive 54th root psi=188. Primitive 27th root
omega=114. Primitive cube root w3=242. Three fully-unrolled stages, Barrett
reduction. Module: crypto/ntt27.go.
Ring splits completely: 271 is prime, psi^54≡1, psi^27≡-1 mod 271. The 27 evaluation points -psi^(2j+1) are distinct. The ring is isomorphic to a direct product of 27 copies of Z_271. Inversion is pointwise in the NTT domain via Fermat's little theorem. This is the same structure as the power-of-2 case — NTRU keygen ports directly.
Security: single n=27 SIS instance has ~25-bit hardness. BKZ-27 solves SVP exactly on dimension 27 — no reduction factor. A single 27-dimensional SIS instance is solvable on a laptop in hours. The ring is a building block, not a final security parameter. Production PQ security requires composite rings at n≥400.
Existing primitives:
crypto/ntt27.go): done, tested (round-trip, convolution, linearity, negacyclic)crypto/gnarl_hash.go): SWIFFT over gnarl ring, three output tiers (GMid 216-bit/27B, GHash 243-bit/31B, GShard 54-bit/7B)[27]uint16 in NTT codecrypto/gnarl/): separate algebraic object — 216-bit SL(2) torus, NOT the gnarl ring. Disjoint from the tree protocol.The atomic primitive. NTRU signature on the gnarl ring producing a 43-byte lattice proof. Security: 25-bit SIS per leaf. Accept this as the coordination primitive — the tree coordinates many leaves, it does not amplify per-leaf security.
1. Sample f, g from discrete Gaussian D(Z^27, sigma=10.4).
Reject if f not invertible (any NTT slot == 0).
These ARE the f,g stored in the secret key.
2. Compute public key: h = g * f^{-1} mod (x^27+1, 271).
Serialized: 31 bytes (27 coeffs × 9 bits unsigned, LE bitwise).
3. Build NTRU lattice from h to find the complete short basis:
H = 27×27 multiplication-by-h matrix (circulant with x^27+1 twist).
B = [I | 0; H | 271*I] — 54×54 integer matrix.
4. LLL-reduce B (δ=0.99, exact integer arithmetic).
Dimension 54, O(54^3 × iterations) ≈ sub-ms, one-time at keygen.
The reduced basis contains short lattice vectors. The signer uses
LLL to find the complete secret basis — this is correct NTRUSign
keygen, not an attack on the signer's own key.
Extract (F,G) from the reduced basis: the first two reduced vectors
have the form (a,b) and (c,d) where a,b,c,d are 27-coefficient
integer vectors. Set F = d, G = b (or the appropriate sign-corrected
linear combination). The reduced vectors satisfy:
a*G - b*F = 271^n = 271^27 (as integer polynomials)
The extracted (F,G) alongside the original (f,g) form a complete
short basis suitable for ffSampling.
5. Verify the basis is correct:
- det of the 54×54 basis matrix = 271^27
- f*G - g*F = 271 (NTRU equation, verified coefficient-wise over Z)
- ||F||, ||G|| ≤ bound (basis is short)
6. Secret key: (f, g, F, G), each a Poly27. Serialized: 4 × 31 = 124 bytes.
Public key: h (31 bytes).
Alternative approach (extended GCD per NTT slot): for each of the 27 NTT slots, solve the 2D extended GCD fi * Gi - gi * Fi = 271 over integers, then INTT to recover (F,G) in coefficient form. Simpler than LLL but requires handling the case where gcd(fi, gi) ≠ 1. The LLL approach handles this generically. Either works for n=27.
Adapted from crypto/ring/falcon.go:233 for 27-element polynomials:
ffSampling(f, g, F, G, target):
b1 = (g, -f), b2 = (-G, F) -- NTRU basis (2-vectors of Poly27)
Current = (0, target) -- non-short preimage
// Process b2: Gram-Schmidt orthogonalize
mu2 = dot(Current, b2*) / dot(b2*, b2*)
z2 = sampleZ(sigma/||b2*||, mu2)
Current = Current - z2·b2
// Process b1
mu1 = dot(Current, b1) / dot(b1, b1)
z1 = sampleZ(sigma/||b1||, mu1)
Current = Current - z1·b1
return Current.s2 -- short polynomial
Gram-Schmidt operates on 2-vectors of 27-element polynomials (54 coefficients total). Dot products use centered (signed) coefficient values modulo 271.
Sigma scaling: the base sigma=10.4 is the Gaussian width for the polynomial sampler (producing f, g, etc). During ffSampling, the effective sigma per basis vector is scaled down by the Gram-Schmidt norm:
||b1|| = ||(g,-f)|| ≈ sqrt(2×27)×10.4 ≈ 76 ||b2*|| = Gram-Schmidt norm of orthogonalized second vector ≈ 76 (similar)
sigma_eff for z2: sigma / ||b2*|| ≈ 10.4 / 76 ≈ 0.137 sigma_eff for z1: sigma / ||b1|| ≈ 10.4 / 76 ≈ 0.137
Each z_i is a small integer (typically 0 or ±1) — the scaled-down sigma keeps the adjustments fine-grained. The final preimage (s1,s2) after subtracting z1·b1 + z2·b2 from the target inherits the base sigma's bound:
bound = sigma × (1.5 + tail) = 10.4 × (1.5 + 9) = 10.4 × 10.5 ≈ 109
This is consistent: the base sigma determines the final signature norm, while the per-basis-vector effective sigma determines the integer step sizes during the ffSampling walk.
1. salt = random 16 bytes
2. c = sparsePoly(GMid(salt || pk.h || msg), tau=13)
Sparse polynomial: exactly τ=13 non-zero positions, each ±1.
3. s2 = ffSampling(f, g, F, G, c, sigma)
4. sig = salt || Serialize(s2, bits=8, signed=true)
= 16 + 27 = 43 bytes
Tail factor = 9 (2^{-64} statistical distance). Bound = sigma × 10.5 ≈ 109. 8-bit signed covers [-128, 127] with room for 109. Maximum observed norm < 109 by rejection sampling — overflows are rejected at signing time.
1. salt, s2 = parse sig
2. c = sparsePoly(GMid(salt || pk.h || msg), tau=13)
3. s1 = c - h·s2 (mod 271, centered)
4. Norm(s1) ≤ bound AND Norm(s2) ≤ bound → accept
One ring equation check. O(n log n) = fast.
NTRUPublicKey { H *Poly27 } 31 bytes serialized
NTRUPrivateKey { F, G, f, g *Poly27; PK *NTRUPublicKey } 124 + 31 bytes
NTRUSignature { Salt [16]byte; S2 *Poly27 } 43 bytes serialized
The tree geometry: z = n+1 = 28. Each node has exactly 27 children, dimension-matched to the ring. The tree IS a credential coordination graph — children hold independent trapdoors, the coordinator aggregates their commitments. The tree does NOT amplify per-leaf SIS security. It distributes trust and coordinates participation.
Coordinator public key: A_parent (NTRU h polynomial)
Child i projection: A_i = A_parent · ω^i for i = 0..26
where ω = 114 (primitive 27th root in Z_271)
Child i has NTRU keypair: (A_i, R_i)
R_i = (f_i, g_i, F_i, G_i) — NTRU trapdoor for A_i
The projection differentiates children while using the coordinator's A as the shared base. Each child generates its own NTRU key with its own trapdoor. The coordinator needs only A_parent — it does not know children's trapdoors.
Child i produces: z_i = ffSampling(f_i, g_i, F_i, G_i, c_i)
w_i = A_i · z_i (commitment, 31 bytes)
Coordinator receives: w_0..w_26
target = sparsePoly(GMid("gnarl-pure-agg-v1" || epoch || w_0 || ... || w_26 || msg))
z_total = Σ ω^{-i} · z_i (weighted sum cancelling projection twiddles)
Signature: z_total (8-bit signed × 27 = 27 bytes)
No salt needed in pure aggregation: the verifier recomputes target from the w_i list (which the coordinator publishes as part of the epoch frame). The target hash contains epoch and all w_i — it is already nonce-bound. The coordinator does not sign; it merely sums. The verifier checks: Aparent · ztotal == target. One ring equation. 25-bit SIS.
Coordinator has: R_parent (trapdoor for A_parent).
After pure aggregation: z_partial = Σ ω^{-i} · z_i
Coordinator signs the aggregate with its own NTRU key:
salt = random 16 bytes
target = sparsePoly(GMid("gnarl-coord-sign-v1" || salt || epoch || w_0 || ... || w_26 || msg))
z_correction = ffSampling(f_parent, g_parent, F_parent, G_parent,
target - A_parent · z_partial)
z_sig = z_partial + z_correction
Signature: salt || Serialize(z_sig, bits=8, signed=true)
= 16 + 27 = 43 bytes.
Security: 25 (children) + 25 (coordinator) = 50-bit SIS.
Attack cost: forge all 27 child contributions (27 × 25-bit) OR forge coordinator trapdoor (25-bit) AND one child set. The coordinator trapdoor adds one more SIS dimension the attacker must break.
Height h | Members (27^h) | Sequential depth | Coordinator model
1 | 27 | 1 level | pure or with trapdoor
2 | 729 | 2 levels | recursive coordinator
3 | ~19,683 | 3 levels | recursive
At each level, the coordinator aggregates 27 child commitments into 1 parent commitment, then the parent coordinator signs the root. Depth-2: 27 level-1 coordinators, 1 root coordinator. Depth-h: h sequential aggregation passes, each level fully parallel (all 27^{h-1} coordinators at level h work independently).
The tree signature structure IS the group protocol. The commitment list IS the membership roster. The epoch binding IS the Fiat-Shamir domain separation. No separate protocol needed — the signature provides group authentication as a side effect.
Adapt the KEM encrypt/decrypt from crypto/ring/kem.go for Poly27:
Encrypt(pk, m):
r = sampleShortPoly() // ternary or CBD noise
e1, e2 = sampleShortPoly() // noise
u = A_parent · r + e1 // (mod 271, centered)
v = h_parent · r + e2 + encode(m) // h_parent is coordinator public key
ciphertext = (u, v)
Decrypt(sk, ct):
m' = decode(v - f_parent · u)
Noise term: e2 + r·e - f·e1. Small enough for threshold decoding.
Coordinator generates short secret s ∈ Poly27.
Splits: s = Σ s_i (additive shares, each child_i holds s_i)
Ciphertext: (u, v) where v = h_parent · r + e2 + encode(m)
Child i computes partial: d_i = s_i · u
Coordinator combines: d_total = Σ d_i = s · u
Decode: m' = decode(v - d_total) = decode(encode(m) + noise)
Distributed decryption requires k-of-n children to submit partials. The coordinator waits for k responses, sums them, decodes. No single child leaks the full secret. No single point of compromise for decryption.
Epoch 0: child_i holds static key pair (A_i_0, R_i_0)
coordinator generates s_0, splits into s_i_0 shares
encrypts each share to A_i_0, child decrypts with R_i_0
Epoch 1: derive A_i_1 = A_parent · ω^i · Hash(1 || i)
child generates new R_i_1 from KEM output
coordinator encrypts new s_i_1 to A_i_1
(OR: child publishes new A_i_1, coordinator encrypts to it)
Property: compromising child_i at epoch e reveals R_i_e and s_i_e.
These are useless for epoch e-1 (different A_parent_epoch, different s).
Attacker must break SIS for each compromised child per epoch.
Static key weakness: if child_i's base key A_i is fixed, compromise reveals
all future KEM traffic encrypted to that key. Fix: derive per-epoch A_i =
A_parent · ω^i · Hash(epoch || i). Child generates new per-epoch trapdoor
from the KEM output. Adds one round trip (child must publish A_i_epoch before
parent encrypts). Acceptable for squad-scale.
EpochState {
Counter uint64 // epoch number
Coordinator *NTRUPublicKey // root public key (31B)
Children [27]*ChildCommitment // member commitments
RootSig *NTRUSignature // coordinator signature
finalized bool
}
func StartEpoch(counter, coordinatorPK) *EpochState
func (es *EpochState) AddCommitment(cc) error // per child, O(1)
func (es *EpochState) Finalize(coordinatorSK, msg) error // produce RootSig
func (es *EpochState) Verify(coordinatorPK, msg) bool // one ring equation
func (es *EpochState) RotateMember(index, newChild) // O(1)
Short-vector voting: each child's z_i carries a ±1 vote as a norm-bounded coefficient. The coordinator sums all zi. The norm of ztotal reveals the vote count. Individual votes are hidden in the aggregate.
Vote protocol:
Vote YES: child produces z_i where first coefficient is +1 (norm-bounded)
Vote NO: child produces z_i where first coefficient is -1
Abstain: child produces z_i = 0
Coordinator: z_total = Σ ω^{-i} · z_i
Norm(z_total) ≈ k × 54 (each vote contributes sqrt(n) × sigma ≈ 54)
For 27 children all YES: norm ≈ 1458.
For 14 YES, 13 NO: norm ≈ 54 (the +1 and -1 cancel, residual from noise).
Threshold: if norm ≥ k_threshold × 54 → k_threshold honest votes.
k-of-n threshold enforced by the norm bound.
Privacy model: two variants.
Pure aggregation (no privacy): children send z_i in the clear to the coordinator. The coordinator sees individual votes. Privacy comes from transport-layer encryption (GnarlWire), not from the protocol. Suitable for transparent group decision-making.
Coordinator-with-trapdoor (private broadcast): children encrypt z_i to A_parent using Ring-LWE. Ciphertexts are published to the tree — all members see them. Only the coordinator (holding Rparent) decrypts the individual zi, sums them, publishes ztotal. The verifier checks Aparent · z_total == target and the norm threshold for vote count. Individual z_i remain hidden from non-coordinator members. The coordinator is trusted with vote privacy.
Byzantine tolerance: coordinator sums k honest responses, ignores Byzantine ones. The verifier checks the norm bound on z_total — if the norm matches k honest votes, accept.
Three frame types for the three communication patterns.
Offset Size Field
0 1 Index (uint8, 0–26)
1 31 PubKey (Poly27, 9-bit unsigned)
32 31 W (commitment, Poly27, 9-bit unsigned)
Offset Size Field
0 8 Counter (uint64 LE)
8 31 RootPK (coordinator's H, 9-bit unsigned)
39 63×27 Commitments [27]CommitmentFrame
1740 43 RootSig (16B salt + 27B s2 at 8-bit signed)
Sent once at epoch start. Verifier caches the commitment list and root PK.
Offset Size Field
0 8 Counter (uint64 LE)
8 31 RootPK
39 31 WCompressed = GMid(w_0 || ... || w_26 || epoch)
70 43 RootSig
A relay receiving a message verifies the checkpoint against its cached epoch state: confirm WCompressed matches the cached commitment list, then verify root sig covers the reconstructed target (salt from sig + cached w_i + msg). O(1) per message. A new relay joining mid-epoch must fetch the full EpochFrame first — the EpochCheckFrame is a proof of cached state, not a self-verifying proof.
Pure aggregation compact frame (39 bytes): the coordinator broadcasts counter (8B) + WCompressed (31B) = (GMid of all w_i + epoch).
No root sig needed. The verifier checks: target = sparsePoly(GMid("gnarl-pure-agg-v1" || WCompressed || msg)) Aparent · ztotal == target
One ring equation, O(1). 25-bit SIS, zero coordinator trust, 39-byte per-message proof. The compact frame carries the commitment hash — no raw w_i list, no coordinator signature. The verifier confirms the hash chain without caching.
GnarlWire (crypto/gnarl_wire.go) provides ChaCha20 + GMid MAC authenticated
encryption with a 64-byte header. Epoch frames are payload data with a new
message type byte assigned to GnarlSeal(msgType, data). The coordinator's
broadcast is a GnarlPacket, not a new wire format. The GnarlWire identity
field identifies the sender (coordinator or child).
crypto/gnarlring/The gnarl-ring polynomial arithmetic (uint16 mod 271) is disjoint from
crypto/gnarl/ (4-limb 216-bit Montgomery field elements for the torus
Schnorr scheme). Separate package avoids coupling the tree protocol to the
torus group operations.
crypto/gnarlring/
poly.go (~200 LOC) Poly27 type, ring arithmetic, NTT, serialization
gaussian.go (~80 LOC) CDT Gaussian sampler for sigma≈10.4
ntru.go (~450 LOC) NTRU keygen (LLL), ffSampling, sign, verify
commitment.go (~150 LOC) ChildCommitment, AggregatedCommitment, target
epoch.go (~150 LOC) EpochState, coordinator ops, verification
wire.go (~120 LOC) Frame serialization for all three frame types
poly_test.go (~100 LOC)
gaussian_test.go (~60 LOC)
ntru_test.go (~150 LOC)
commitment_test.go (~80 LOC)
epoch_test.go (~100 LOC)
wire_test.go (~60 LOC)
Total: ~1700 LOC
Dependencies: crypto (ntt27, invMod271, mod271, GMid). No dependency on
crypto/gnarl/ or crypto/ring/.
| Step | Module | Deliverable | Depends On |
|---|---|---|---|
| 0 | poly.go | Poly27 arithmetic, NTT wrapping, inversion, serialization | crypto/ntt27 |
| 1 | gaussian.go | CDT sampler, sigma≈10.4 | (stdlib) |
| 2 | ntru.go | 43-byte NTRU signature, LLL keygen, ffSampling | steps 0, 1 |
| 3 | commitment.go | Child commitment + aggregation + target hash | steps 0, 2 |
| 4 | epoch.go | Epoch state machine, coordinator signing, verification | steps 2, 3 |
| 5 | wire.go | CommitmentFrame, EpochFrame, EpochCheckFrame | steps 0, 2, 3, 4 |
After step 2: compact PQ signature (43 bytes, 25-bit SIS) works standalone. After step 4: group messaging protocol works (up to 27 members, epoch management). The compound deliverable — signature IS group proof — is validated.
| Step | Module | Deliverable | Notes |
|---|---|---|---|
| 6 | lwe.go | Ring-LWE encryption on gnarl ring | ~200 LOC, adapt from crypto/ring/kem.go for Poly27 |
| 7 | shard.go | Additive secret sharing + distributed decryption | ~100 LOC |
| 8 | consensus.go | Short-vector voting + norm threshold | ~150 LOC |
| 9 | insurge_wire.go | GnarlWire msgType for epoch frames | ~50 LOC |
| 10 | composite.go | Composite ring at n≥400 for 128-bit SIS | ~500-1000 LOC, major engineering |
| 11 | recursive.go | Recursive tree at depth > 1 | ~100 LOC on top of flat model |
No known function compresses n SIS instances into 1 at the same ring dimension without a kernel. The tree coordinates participation — it does not amplify per-leaf security. A 27-leaf tree at 25-bit SIS per leaf still requires 25-bit total from the verifier's perspective (the attacker forges one leaf and the coordinator sums it in). The coordinator's trapdoor adds 25 more bits (50 total), not multiplicative.
Accepted: the tree is for credential coordination and parallel computation, not security amplification. The security of the group equals the security of one NTRU instance plus, optionally, the coordinator's own NTRU instance.
Requires ring dimension n ≥ 400 with aggressive encoding (ternary secrets, arithmetic coding). Falcon-512 at 690 bytes is the practical baseline. The gnarl ring (n=27) and hamadryad ring (n=64) are building blocks for composite rings — they validate the algorithmic machinery (LLL, ffSampling, NTRU encoding) at small scale. The machinery ports to larger rings once the ring arithmetic is provided.
Getting below Falcon's 690 bytes: the same NTRU structure on a composite ring produces two short polynomials (s1, s2). Falcon sends only s2 (~690 bytes compressed). Can we compress s2 further using the gnarl-ring encoding techniques (variable-width bit packing, leaner norm bounds from the ffSampling output)? The gap from 690 to sub-128 requires either a relaxed security margin or a novel encoding. The tree does not close this gap.
Childi's base public key Ai is fixed across epochs unless a per-epoch derivation is used. If the child is compromised at epoch e, and the base Ai is static, all future KEM traffic encrypted to Ai is decryptable. Fix: derive Aiepoch = A_parent · ω^i · Hash(epoch || i). Child generates new per-epoch trapdoor. This requires the child to publish Aiepoch before the coordinator can encrypt to it — a round trip per epoch. Acceptable at squad-scale, needs refinement for larger groups.
The insurge protocol's content-routing layer maps relays to tree nodes:
Depth-1: 27 leaf relays + 1 coordinator relay → local cluster (28 relays)
Depth-2: 729 leaf relays + 27 level-1 coordinators + 1 root → regional (757 relays)
Depth-3: ~19,683 leaf relays → global scale
Each relay is a tree node holding either a leaf keypair (children) or a coordinator keypair (internal nodes). Message routing: content hash → tree path — which child subtree handles the content. The relay path is the tree path from leaf to root.
Per-Message Verification: a relay receiving an insurge message verifies the sender's epoch membership via the EpochCheckFrame (113 bytes). The relay checks the root signature against WCompressed. O(1) per message. No need to receive all 27 child commitments. The full epoch frame (1783 bytes) is sent only at epoch transitions.
The Compound Deliverable: mainline DHT made torrent metadata discovery decentralized. This stack makes group messaging fully PQ with private broadcast, post-compromise security, forward secrecy, and distributed decryption — all from one ring assumption and one tree structure. The tree's concurrent-parallel construction scales throughput linearly with members. The wire format is sentinel-delimited epoch batches of short vectors. Nostr is a decentralized tweet database. Insurge is a relay network that does what MLS promises but with lattice primitives, running in parallel, and post-quantum.
MIT — same as the gnarl-hamadryad repository.