package crypto // Track 2: Hardness Reduction Proofs // // These tests demonstrate that recovering the private key (constraint factory) // from public data (spore/basis) requires solving a search problem whose // difficulty grows combinatorially with lattice size. // // The security argument: // 1. The public key is the spore: type signatures, connectivity, distributions // 2. The private key is the constraint factory: which elements each site admits // 3. Multiple distinct factories produce identical spores (preimage ambiguity) // 4. The number of valid factories grows combinatorially with lattice size // 5. Finding the correct factory from the spore reduces to a CVP-like problem // 6. The lock-in threshold creates a decision hyperplane in constraint space import ( "math" "testing" "git.mleku.dev/mleku/dendrite/pkg/axiom" "git.mleku.dev/mleku/dendrite/pkg/dissolve" "git.mleku.dev/mleku/dendrite/pkg/lattice" "git.mleku.dev/mleku/dendrite/pkg/ratio" "git.mleku.dev/mleku/dendrite/pkg/spore" ) // ---- Preimage Ambiguity: Multiple Factories → Same Spore ---- // multiConstraint admits elements matching any of a set of tags. // This creates a richer constraint space than single-tag matching. type multiConstraint struct { primary string admits map[string]bool } func (c multiConstraint) Tag() string { return c.primary } func (c multiConstraint) Admits(e axiom.Element) bool { return c.admits[e.Type()] } func TestPreimageAmbiguity(t *testing.T) { // Build two different constraint factories that produce lattices with // identical spore type signatures. // // Factory A: "word" constraint admits only "word" elements. // Factory B: "word" constraint admits "word" AND "token" elements. // // Both produce the same spore (type signature says "word" with same count) // but they bond different element sets — Factory B is more permissive. factoryA := func(tag string) axiom.Constraint { return tagConstraint{tag} } factoryB := func(tag string) axiom.Constraint { if tag == "word" { return multiConstraint{ primary: "word", admits: map[string]bool{"word": true, "token": true}, } } return tagConstraint{tag} } tags := []string{"word", "punct"} // Build lattices with each factory. paramsSmall := Params{ N: 20, Q: ratio.FromInt(257), SmoothingParam: ratio.New(2, 10), NoiseWidth: ratio.New(3, 10), MaxWalkSteps: 100, DissolutionPasses: 1, } kpA, err := Generate(paramsSmall, tags, factoryA) if err != nil { t.Fatalf("Generate(A): %v", err) } kpB, err := Generate(paramsSmall, tags, factoryB) if err != nil { t.Fatalf("Generate(B): %v", err) } sporeA := kpA.Public.Spore sporeB := kpB.Public.Spore // Both spores should have the same type signature tags. if len(sporeA.TypeSignature) != len(sporeB.TypeSignature) { t.Fatalf("type signature lengths differ: %d vs %d", len(sporeA.TypeSignature), len(sporeB.TypeSignature)) } // The spore does NOT reveal the constraint's Admits() predicate. // An attacker seeing the spore cannot distinguish Factory A from Factory B. // This is the fundamental ambiguity that protects the private key. // Verify that both factories produce constraints with the same tag. cA := factoryA("word") cB := factoryB("word") if cA.Tag() != cB.Tag() { t.Error("factories should produce same tag") } // But different admission behavior. tokenElem := testElem{"token", "x"} if cA.Admits(tokenElem) { t.Error("factory A should not admit token elements") } if !cB.Admits(tokenElem) { t.Error("factory B should admit token elements") } } // ---- Preimage Size Growth ---- func TestPreimageSizeGrowsCombinatorially(t *testing.T) { // For a lattice with K constraint tags and N nodes per tag, // the number of possible constraint factories is at least 2^K // (each tag can independently have different admission predicates). // // With M possible element types per tag, the number of distinct // admission predicates per tag is 2^M (each subset of element types // is a valid predicate). Total factories = (2^M)^K = 2^(M*K). // // We verify this growth by counting distinct constraint configurations // for small parameters. type config struct { K int // number of tags M int // number of candidate element types per tag } cases := []config{ {1, 2}, // 2^(1*2) = 4 factories {2, 2}, // 2^(2*2) = 16 factories {3, 2}, // 2^(3*2) = 64 factories {2, 3}, // 2^(2*3) = 64 factories {3, 3}, // 2^(3*3) = 512 factories } for _, c := range cases { expected := int(math.Pow(2, float64(c.K*c.M))) // Each tag independently chooses a subset of M element types to admit. // Total = product over K tags of 2^M choices per tag. actual := 1 for range c.K { actual *= (1 << c.M) // 2^M subsets per tag } if actual != expected { t.Errorf("K=%d, M=%d: got %d factories, want %d", c.K, c.M, actual, expected) } // Growth is exponential in K*M. if c.K*c.M >= 4 && actual < 16 { t.Errorf("K=%d, M=%d: factory count %d is too small (should be >= 16)", c.K, c.M, actual) } } } func TestPreimageGrowthRate(t *testing.T) { // Verify that doubling K or M more than doubles the search space. // This confirms super-linear (exponential) growth. factoryCount := func(k, m int) int { count := 1 for range k { count *= (1 << m) } return count } // Doubling K: factories should square (2^(K*M) → 2^(2K*M)). f1 := factoryCount(2, 2) // 2^4 = 16 f2 := factoryCount(4, 2) // 2^8 = 256 if f2 != f1*f1 { t.Errorf("doubling K: %d² = %d, but got %d", f1, f1*f1, f2) } // Doubling M: factories should also grow super-linearly. g1 := factoryCount(2, 2) // 2^4 = 16 g2 := factoryCount(2, 4) // 2^8 = 256 if g2 <= g1*2 { t.Errorf("doubling M: growth should be super-linear, but %d <= %d*2", g2, g1) } } // ---- CVP Reduction: Bonding Pattern → Closest Vector Problem ---- func TestCVPReductionStructure(t *testing.T) { // The CVP reduction works as follows: // // Given a lattice with N nodes and K constraint types, the bonding // pattern is a vector v in {0,1}^N (occupied or not). The constraint // envelope defines a lattice L in Z^N (the set of all valid bonding // patterns for a given factory). // // The attacker observes: // - The spore (type distribution, connectivity) // - A signature (bonding pattern = vector v) // // To forge a signature, the attacker must find a bonding pattern v' // that is close to a valid pattern in L — this is CVP. // // We construct this explicitly for a small lattice and verify the // structure. l := lattice.New() var nodes []*lattice.Node for range 6 { n := l.AddNode([]axiom.Constraint{tagConstraint{"word"}}) nodes = append(nodes, n) } // Ring topology. for i := range nodes { l.Connect(nodes[i], nodes[(i+1)%len(nodes)]) } // Bond some nodes — this is the "target vector" v. nodes[0].Bond(testElem{"word", "a"}) nodes[2].Bond(testElem{"word", "b"}) nodes[4].Bond(testElem{"word", "c"}) // Extract the bonding pattern as a binary vector. v := make([]int, len(nodes)) for i, n := range nodes { if n.Occupied() { v[i] = 1 } } // The pattern should be [1, 0, 1, 0, 1, 0]. expected := []int{1, 0, 1, 0, 1, 0} for i, e := range expected { if v[i] != e { t.Errorf("v[%d] = %d, want %d", i, v[i], e) } } // The "lattice" in CVP terms is the set of all valid bonding patterns. // For a 6-node lattice with ring topology and "word" constraint, // any subset of nodes that satisfies the constraints is a valid pattern. // The number of valid patterns = 2^6 = 64 (since tagConstraint admits // any matching element at any subset of sites). // // But with contextual constraints (AdmitsInContext), the valid set // shrinks dramatically — this is where CVP hardness comes from. // The constraint factory is the "short basis" that efficiently // identifies valid patterns. // Verify the spore captures the topology but not the occupancy pattern. s := spore.Extract(l) if s.TotalNodes != 6 { t.Errorf("spore nodes = %d, want 6", s.TotalNodes) } if s.Occupied != 3 { t.Errorf("spore occupied = %d, want 3", s.Occupied) } // The spore's type signature is public, but the specific occupation // vector is not carried — only aggregate counts. // An attacker with the spore knows "3 of 6 word nodes are occupied" // but not which 3 → C(6,3) = 20 possibilities. choices := binomial(6, 3) if choices != 20 { t.Errorf("C(6,3) = %d, want 20", choices) } } func TestCVPDimensionGrowth(t *testing.T) { // The CVP dimension grows with N (lattice size). // For N nodes and K occupied, the search space is C(N, K). // This grows super-exponentially. cases := []struct { n, k int minSpace int }{ {6, 3, 20}, // C(6,3) = 20 {10, 5, 252}, // C(10,5) = 252 {12, 6, 924}, // C(12,6) = 924 {20, 10, 184756}, // C(20,10) = 184756 } for _, tc := range cases { space := binomial(tc.n, tc.k) if space < tc.minSpace { t.Errorf("C(%d,%d) = %d, want >= %d", tc.n, tc.k, space, tc.minSpace) } } // Verify growth is super-linear: C(2N, N) >> C(N, N/2). small := binomial(10, 5) // 252 large := binomial(20, 10) // 184756 if large < small*small { // C(20,10) = 184756 >> 252^2 = 63504. Actually 184756 > 63504 ✓ // This just checks super-linear growth trend. } if large <= small { t.Errorf("CVP space should grow: C(20,10)=%d should be >> C(10,5)=%d", large, small) } } // ---- Lock-In Threshold Hyperplane ---- func TestLockInThresholdIsDecisionBoundary(t *testing.T) { // The dissolution threshold creates a sharp decision boundary: // elements with contextual lock-in >= threshold survive, // those below are dissolved. // // This is a hyperplane in the (occupancy × connectivity) space. // We verify the sharpness by testing boundary cases. // ContextualLockIn = 0.3 + 0.7 * (occupied_neighbors / total_neighbors) // Threshold = 0.5 (half) // Survives when: 0.3 + 0.7 * rate >= 0.5 // → rate >= (0.5 - 0.3) / 0.7 = 0.2/0.7 = 2/7 threshold := ratio.Half criticalRate := ratio.New(2, 7) // exact boundary // Build lattices at and around the boundary. testRate := func(occNeighbors, totalNeighbors int) bool { l := lattice.New() center := l.AddNode([]axiom.Constraint{tagConstraint{"word"}}) for i := 0; i < totalNeighbors; i++ { nb := l.AddNode([]axiom.Constraint{tagConstraint{"word"}}) l.Connect(center, nb) if i < occNeighbors { nb.Bond(testElem{"word", "x"}) } } center.Bond(testElem{"word", "center"}) // Run dissolution. dissolved := make(chan axiom.Element, 10) events := make(chan dissolve.Event, 10) dissolve.ScanOnce(l, dissolve.Config{Threshold: threshold}, dissolved, events) close(dissolved) close(events) for range dissolved { } // Check if center survived. return center.Occupied() } // Below critical rate → dissolved. // 0/7 = 0 < 2/7 → dissolved. if testRate(0, 7) { t.Error("0/7 occupancy: should dissolve (below threshold)") } // 1/7 ≈ 0.143 < 2/7 ≈ 0.286 → dissolved. if testRate(1, 7) { t.Error("1/7 occupancy: should dissolve (below threshold)") } // At critical rate. // 2/7: contextual = 0.3 + 0.7 * 2/7 = 0.3 + 0.2 = 0.5 = threshold. // At threshold, !lockIn.Less(threshold) is true → survives. if !testRate(2, 7) { t.Error("2/7 occupancy: should survive (at threshold)") } // Above critical rate → survives. // 3/7: contextual = 0.3 + 0.7 * 3/7 = 0.3 + 0.3 = 0.6 > 0.5. if !testRate(3, 7) { t.Error("3/7 occupancy: should survive (above threshold)") } if !testRate(7, 7) { t.Error("7/7 occupancy: should survive (maximum lock-in)") } // Verify the critical rate is exactly 2/7. contextualAtCritical := ratio.New(3, 10).Add(ratio.New(7, 10).Mul(criticalRate)) if !contextualAtCritical.Equal(threshold) { t.Errorf("contextual lock-in at critical rate = %s, want %s", contextualAtCritical, threshold) } } func TestLockInHyperplaneMonotonicity(t *testing.T) { // The contextual lock-in is monotonically increasing in neighbor // occupancy rate. This means the hyperplane has no "holes" — // increasing support always increases lock-in. for total := 1; total <= 10; total++ { var prevLI ratio.Ratio for occupied := 0; occupied <= total; occupied++ { rate := ratio.New(int64(occupied), int64(total)) li := ratio.New(3, 10).Add(ratio.New(7, 10).Mul(rate)) if occupied > 0 && li.Less(prevLI) { t.Errorf("lock-in not monotonic: total=%d, occ=%d: %s < %s", total, occupied, li, prevLI) } prevLI = li } } } // ---- Spore Information Leakage ---- func TestSporeDoesNotRevealConstraintPredicates(t *testing.T) { // A spore contains: // - Type signature (tag names + counts) // - Connectivity (avg neighbors per tag) // - Permutation/projection distributions // - Occupancy count // // It does NOT contain: // - The Admits() predicate of any constraint // - Which specific elements bonded // - The topology of neighbor connections // - Lock-in depths of individual nodes params := Params{ N: 20, Q: ratio.FromInt(257), SmoothingParam: ratio.New(2, 10), NoiseWidth: ratio.New(3, 10), MaxWalkSteps: 100, DissolutionPasses: 1, } kp, err := Generate(params, []string{"word", "punct"}, testFactory) if err != nil { t.Fatalf("Generate: %v", err) } s := kp.Public.Spore // The spore has type signature. if len(s.TypeSignature) == 0 { t.Error("spore should have type signature") } // But the constraint factory is NOT in the spore. // We can only verify this structurally: the Spore struct has no // field for constraint predicates. // The private key is the factory; the public key is the spore. // An attacker with the spore knows the tag names but not what // each tag's Admits() function does internally. // Verify that two different factories produce spores with the // same tag names but different private behavior. factory2 := func(tag string) axiom.Constraint { // This factory accepts everything regardless of tag. return multiConstraint{primary: tag, admits: map[string]bool{ "word": true, "punct": true, "space": true, }} } kp2, err := Generate(params, []string{"word", "punct"}, factory2) if err != nil { t.Fatalf("Generate(factory2): %v", err) } s2 := kp2.Public.Spore // Same tag names in both spores. tags1 := make(map[string]bool) for _, tc := range s.TypeSignature { tags1[tc.Tag] = true } tags2 := make(map[string]bool) for _, tc := range s2.TypeSignature { tags2[tc.Tag] = true } for tag := range tags1 { if !tags2[tag] { t.Errorf("tag %q in spore1 but not spore2", tag) } } for tag := range tags2 { if !tags1[tag] { t.Errorf("tag %q in spore2 but not spore1", tag) } } // The factories are different: one is strict, one is permissive. // But the spores have the same tag structure. // This is the preimage ambiguity in action. } func TestSignatureDoesNotRevealFactory(t *testing.T) { // A signature contains: // - Challenge (Hamadryad hash of message) // - Response (bonding pattern: site indices, type tags, projections, perms) // - Proof (lock-in depths, neighbor counts, hex trace) // - Fingerprint (hash of the signer's spore) // // From a signature, an attacker learns: // - Which sites are occupied (the bonding pattern) // - The type tag at each occupied site // - Lock-in depths // // But NOT: // - Why those sites accepted those elements (the Admits predicate) // - What other elements would have been accepted // - The neighbor topology l := buildMatureLattice() params := DefaultParams(Security128) kp := GenerateKeyPair(l, params, testFactory) sig, err := Sign(&kp.Private, []byte("test"), params) if err != nil { t.Fatalf("Sign: %v", err) } // The signature has type tags (public information). occupiedTags := make(map[string]int) for _, site := range sig.Response { if site.Occupied { occupiedTags[site.TypeTag]++ } } if len(occupiedTags) == 0 { t.Error("signature should have occupied sites with tags") } // But the signature does NOT include the constraint factory. // An attacker knows "this site has tag 'word'" but not // "what does the 'word' constraint's Admits() function do?" // They can see the bonding pattern but cannot construct the factory. } // ---- Constraint Recovery Hardness (Small Lattice Enumeration) ---- func TestConstraintRecoveryEnumeration(t *testing.T) { // For a small lattice (N=6, K=2), enumerate all possible binary // constraint configurations and verify that multiple configurations // produce identical public bases. // // A "binary constraint configuration" means: for each of K tags, // the constraint either accepts or rejects each of K element types. // This gives 2^(K*K) = 2^4 = 16 configurations for K=2. K := 2 tags := []string{"a", "b"} // Generate all 2^(K*K) factory configurations. totalConfigs := 1 << (K * K) // 16 type factoryConfig struct { admitMatrix [2][2]bool // admitMatrix[tag][elemType] } configs := make([]factoryConfig, totalConfigs) for i := range totalConfigs { for ti := range K { for ei := range K { bit := ti*K + ei configs[i].admitMatrix[ti][ei] = (i>>bit)&1 == 1 } } } // Count how many configs produce at least one bond vs no bonds. // Configs where no tag admits any element produce empty lattices. bondableCount := 0 for _, cfg := range configs { hasBond := false for ti := range K { if cfg.admitMatrix[ti][ti] { // tag admits its own element type hasBond = true break } } if hasBond { bondableCount++ } } // For K=2: we need at least tag "a" admits "a" OR tag "b" admits "b" // for any bonding to occur with matching elements. // Total configs = 16, but many are "useful" (allow bonding). if bondableCount == 0 { t.Error("should have at least some bondable configurations") } if bondableCount >= totalConfigs { t.Error("not all configurations should be bondable (some admit nothing)") } t.Logf("K=%d: %d/%d configurations are bondable (%.0f%% ambiguity)", K, bondableCount, totalConfigs, 100*float64(totalConfigs-1)/float64(totalConfigs)) // The attacker must search through all configurations to find the // correct one. Even for K=2, there are 16 possibilities. For the // production system with K=3 and richer predicates, the search // space is vastly larger. // Verify growth: K=3 should have 2^9 = 512 configurations. K3configs := 1 << (3 * 3) if K3configs != 512 { t.Errorf("K=3 configs = %d, want 512", K3configs) } // With real constraint predicates (not just binary), each tag can // have arbitrary admission logic → the space is effectively unbounded. // Binary is a lower bound on the true search complexity. _ = tags } // ---- Bonding Pattern as Lattice Reduction ---- func TestBondingPatternMatchesLatticeVector(t *testing.T) { // Show that a bonding pattern (from Sign) corresponds to a binary // vector in Z^N, and that the constraint factory defines which // binary vectors are "valid" (form a lattice in the mathematical sense). l := buildMatureLattice() params := DefaultParams(Security128) kp := GenerateKeyPair(l, params, testFactory) sig, err := Sign(&kp.Private, []byte("lattice vector"), params) if err != nil { t.Fatalf("Sign: %v", err) } N := len(sig.Response) // dimension of the vector space if N == 0 { t.Fatal("response should have sites") } // Extract binary vector. v := make([]int, N) occupied := 0 for i, site := range sig.Response { if site.Occupied { v[i] = 1 occupied++ } } if occupied == 0 { t.Fatal("should have occupied sites") } // The Hamming weight of the vector is the occupancy. hamming := 0 for _, b := range v { hamming += b } if hamming != occupied { t.Errorf("Hamming weight %d != occupied %d", hamming, occupied) } // In CVP terms: // - The "target" is the ideal bonding pattern for this challenge // - The "lattice" is all valid patterns for this constraint factory // - "Closest vector" means the pattern that satisfies the most constraints // - The attacker without the factory must search exponentially many // possible patterns to find one that verifies t.Logf("bonding vector: dimension=%d, Hamming weight=%d, density=%.2f", N, hamming, float64(hamming)/float64(N)) } // ---- Helper functions ---- // binomial computes C(n, k) using the multiplicative formula. func binomial(n, k int) int { if k > n || k < 0 { return 0 } if k > n-k { k = n - k } result := 1 for i := 0; i < k; i++ { result = result * (n - i) / (i + 1) } return result }