Cayley Tree Cryptography — Research Summary

tl;dr

Tree-SIS on random-generator Cayley graphs of SL(2, Z_P) is a hard problem with no known polynomial-time attack. The Euclidean algorithm breaks tree-SIS on STANDARD generators but does NOT transfer to random/obfuscated generators. A working (but slow) signature exists via BFS keygen + lookup table. The trapdoor — giving the signer a polynomial advantage over the attacker — is the open problem.

1. The Euclidean Attack Does Not Transfer

Standard generators: SL(2) with g0=[[1,1],[0,1]], g1=[[1,0],[1,1]]. The Euclidean algorithm on matrix entries decomposes any SL(2,Z_P) element into O(log P) generator steps. Tree-SIS on this graph is trivial.

Obfuscated generators: random SL(2) elements. BFS measurements at P=101 show the standard generators sit at TYPICAL distances in the obfuscated Cayley graph (ratio = 1.0 — exactly the graph mean). The Euclidean algorithm works in the standard basis; converting to the obfuscated basis requires solving tree-SIS for 4 anchor vertices (the standard generators). Tree-SIS reduces to tree-SIS.

The conjugate obfuscation gi = Q·si·Q^{-1} is broken by trace invariance: trace(gi) = trace(si) = 2, exposing Q via linear solve. Random generators do not have this property.

2. BFS Ground Truth

BFS enumeration over SL(2, Z_P) for small primes:

P		SL(2,Z_P)		diam	mean	reachable
11	1,320	10	6.6	100%
31	29,760	15	11.2	100%
101	1,030,200	23	16.6	100%

Key findings:

• All vertices reachable with b=4 random generators (proves they generate the group).
• Diameter scales as O(log_b(|G|)) — consistent with expander graph property.
• Random walk at depth 40 covers 85% of |G| at P=31.
• Path length distribution is symmetric unimodal, concentrated near the mean.

3. Obfuscated Generators Have Smaller Diameter

P	Standard gens diam	Random gens (b=4) diam	Random (b=8)	Random (b=16)
31	15	10	7	5
101	23	12	—	—

Random generators produce MORE COMPACT Cayley graphs than standard generators — the expander property is stronger with random choices.

4. Working Signatures via BFS Table (Non-Competitive)

Keygen: Run BFS from root over Cay(G,G) — O(|G|) = O(P^3). Store optimal paths to all vertices. For P=101: 1M vertices, ~4 seconds. For P~2^216: ~2^648 work — infeasible at production scale.

Sign: Look up target in the precomputed table. Path IS the BFS optimal. Verify: Walk the path, check endpoint matches hash target.

Hit rate = table coverage = M/|G|. M entries, |G| vertices, linear.

This is a WORKING signature scheme but keygen is exponentially expensive. The Euclidean algorithm (standard generators) does O(log P) keygen — the Cayley tree equivalent at O(P^3) is the missing algorithmic shortcut.

5. Trapdoor Constructions (All Non-Viable or Inconclusive)

5.1 Conjugate Obfuscation

gi = Q·si·Q^{-1}. Broken: trace(g_i)=2 → linear solve for Q.

5.2 Path Table

Coverage = M/|G|. At production |G|≈2^648: asymptotically zero.

5.3 Generative Basis

Signer decomposes target via Euclidean→G-word conversion. Blowup = (Euclidean len) × (BFS distance to standard gens) / (BFS optimal). At P=31: 10.8×. At production: ~34×. Signature grows quadratically. Non-competitive.

5.4 Multi-Path (k paths, lock analogy)

k=1: sig=76 steps. k=2: sig=87 steps. k=10: sig=125 steps. Adding paths INCREASES signature size with this trapdoor. MIM security unchanged (kD=constant). Lock analogy benefit: eliminates local-search attacks (k>1 → 1 bit feedback per trial).

5.5 Voronoi Tiling

Coverage = k × b^R / |G|. For production |G|≈2^648: R must be diam-sized (~281), making b^R ≈ |G| → k must be O(1), trivially covered. Doesn't scale.

6. What IS Proven

1. Tree-SIS hardness: no known polynomial attack on random-generator Cayley graphs

of SL(2,Z_P). The Euclidean algorithm is a standard-basis attack that does not transfer. The security reduces to expander graph path-finding.

1. Generator obfuscation works (random generators are expanders, fully generating

the group, with no Euclidean-level algebraic shortcut).

1. Conjugate obfuscation does NOT work (trace invariant = 2, trivial distinguish).

1. Multi-path eliminates local search attacks (lock analogy) without changing

MIM bounds.

1. A BFS-table signature EXISTS and works correctly at small scale. The gap

from O(P^3) to O(log P) is the algorithmic challenge.

7. Open Problem

Find a trapdoor giving the signer polynomial advantage in tree-SIS on random-generator Cayley graphs. The signer must find short paths efficiently while the attacker faces MIM (b^{kD/2} bound) or equivalent hardness. Candidate directions:

• Generative basis with sub-diameter decomposition
• Subset-product over designed basis with hidden structure
• Lattice-based trapdoor (GPV analog on Cayley graphs)

8. Relationship to Existing Code

Package	Substrate	Security	Status	Role
crypto/gnarlring/	Z_271[x]/(x^27+1) (circulant)	~25-bit SIS	working	Coordination protocol, epoch tree, wire format
crypto/ring/	Z_q[x]/(x^n+1) (cyclotomic)	~128-bit (n=512)	working	Production PQ: GPV, KEM, HE, MPC
crypto/composite/	Z_q[x]/(x^n+1), n=16	~20-bit	inversion OK, (F,G) blocked	Scaling validation
crypto/cayley/	SL(2,Z_P) Cayley graph	~128-bit (P~2^216)	security proven, trapdoor open	Research: tree-SIS

The ring-based path delivers production PQ signatures today. The Cayley tree path delivers the long-term vision (76-byte PQ signatures). The bridge is an efficient trapdoor construction.