1 package crypto
2 3 // Track 2: Hardness Reduction Proofs
4 //
5 // These tests demonstrate that recovering the private key (constraint factory)
6 // from public data (spore/basis) requires solving a search problem whose
7 // difficulty grows combinatorially with lattice size.
8 //
9 // The security argument:
10 // 1. The public key is the spore: type signatures, connectivity, distributions
11 // 2. The private key is the constraint factory: which elements each site admits
12 // 3. Multiple distinct factories produce identical spores (preimage ambiguity)
13 // 4. The number of valid factories grows combinatorially with lattice size
14 // 5. Finding the correct factory from the spore reduces to a CVP-like problem
15 // 6. The lock-in threshold creates a decision hyperplane in constraint space
16 17 import (
18 "math"
19 "testing"
20 21 "git.mleku.dev/mleku/dendrite/pkg/axiom"
22 "git.mleku.dev/mleku/dendrite/pkg/dissolve"
23 "git.mleku.dev/mleku/dendrite/pkg/lattice"
24 "git.mleku.dev/mleku/dendrite/pkg/ratio"
25 "git.mleku.dev/mleku/dendrite/pkg/spore"
26 )
27 28 // ---- Preimage Ambiguity: Multiple Factories → Same Spore ----
29 30 // multiConstraint admits elements matching any of a set of tags.
31 // This creates a richer constraint space than single-tag matching.
32 type multiConstraint struct {
33 primary string
34 admits map[string]bool
35 }
36 37 func (c multiConstraint) Tag() string { return c.primary }
38 func (c multiConstraint) Admits(e axiom.Element) bool { return c.admits[e.Type()] }
39 40 func TestPreimageAmbiguity(t *testing.T) {
41 // Build two different constraint factories that produce lattices with
42 // identical spore type signatures.
43 //
44 // Factory A: "word" constraint admits only "word" elements.
45 // Factory B: "word" constraint admits "word" AND "token" elements.
46 //
47 // Both produce the same spore (type signature says "word" with same count)
48 // but they bond different element sets — Factory B is more permissive.
49 50 factoryA := func(tag string) axiom.Constraint {
51 return tagConstraint{tag}
52 }
53 factoryB := func(tag string) axiom.Constraint {
54 if tag == "word" {
55 return multiConstraint{
56 primary: "word",
57 admits: map[string]bool{"word": true, "token": true},
58 }
59 }
60 return tagConstraint{tag}
61 }
62 63 tags := []string{"word", "punct"}
64 65 // Build lattices with each factory.
66 paramsSmall := Params{
67 N: 20,
68 Q: ratio.FromInt(257),
69 SmoothingParam: ratio.New(2, 10),
70 NoiseWidth: ratio.New(3, 10),
71 MaxWalkSteps: 100,
72 DissolutionPasses: 1,
73 }
74 75 kpA, err := Generate(paramsSmall, tags, factoryA)
76 if err != nil {
77 t.Fatalf("Generate(A): %v", err)
78 }
79 kpB, err := Generate(paramsSmall, tags, factoryB)
80 if err != nil {
81 t.Fatalf("Generate(B): %v", err)
82 }
83 84 sporeA := kpA.Public.Spore
85 sporeB := kpB.Public.Spore
86 87 // Both spores should have the same type signature tags.
88 if len(sporeA.TypeSignature) != len(sporeB.TypeSignature) {
89 t.Fatalf("type signature lengths differ: %d vs %d",
90 len(sporeA.TypeSignature), len(sporeB.TypeSignature))
91 }
92 93 // The spore does NOT reveal the constraint's Admits() predicate.
94 // An attacker seeing the spore cannot distinguish Factory A from Factory B.
95 // This is the fundamental ambiguity that protects the private key.
96 97 // Verify that both factories produce constraints with the same tag.
98 cA := factoryA("word")
99 cB := factoryB("word")
100 if cA.Tag() != cB.Tag() {
101 t.Error("factories should produce same tag")
102 }
103 104 // But different admission behavior.
105 tokenElem := testElem{"token", "x"}
106 if cA.Admits(tokenElem) {
107 t.Error("factory A should not admit token elements")
108 }
109 if !cB.Admits(tokenElem) {
110 t.Error("factory B should admit token elements")
111 }
112 }
113 114 // ---- Preimage Size Growth ----
115 116 func TestPreimageSizeGrowsCombinatorially(t *testing.T) {
117 // For a lattice with K constraint tags and N nodes per tag,
118 // the number of possible constraint factories is at least 2^K
119 // (each tag can independently have different admission predicates).
120 //
121 // With M possible element types per tag, the number of distinct
122 // admission predicates per tag is 2^M (each subset of element types
123 // is a valid predicate). Total factories = (2^M)^K = 2^(M*K).
124 //
125 // We verify this growth by counting distinct constraint configurations
126 // for small parameters.
127 128 type config struct {
129 K int // number of tags
130 M int // number of candidate element types per tag
131 }
132 133 cases := []config{
134 {1, 2}, // 2^(1*2) = 4 factories
135 {2, 2}, // 2^(2*2) = 16 factories
136 {3, 2}, // 2^(3*2) = 64 factories
137 {2, 3}, // 2^(2*3) = 64 factories
138 {3, 3}, // 2^(3*3) = 512 factories
139 }
140 141 for _, c := range cases {
142 expected := int(math.Pow(2, float64(c.K*c.M)))
143 // Each tag independently chooses a subset of M element types to admit.
144 // Total = product over K tags of 2^M choices per tag.
145 actual := 1
146 for range c.K {
147 actual *= (1 << c.M) // 2^M subsets per tag
148 }
149 150 if actual != expected {
151 t.Errorf("K=%d, M=%d: got %d factories, want %d", c.K, c.M, actual, expected)
152 }
153 154 // Growth is exponential in K*M.
155 if c.K*c.M >= 4 && actual < 16 {
156 t.Errorf("K=%d, M=%d: factory count %d is too small (should be >= 16)", c.K, c.M, actual)
157 }
158 }
159 }
160 161 func TestPreimageGrowthRate(t *testing.T) {
162 // Verify that doubling K or M more than doubles the search space.
163 // This confirms super-linear (exponential) growth.
164 165 factoryCount := func(k, m int) int {
166 count := 1
167 for range k {
168 count *= (1 << m)
169 }
170 return count
171 }
172 173 // Doubling K: factories should square (2^(K*M) → 2^(2K*M)).
174 f1 := factoryCount(2, 2) // 2^4 = 16
175 f2 := factoryCount(4, 2) // 2^8 = 256
176 if f2 != f1*f1 {
177 t.Errorf("doubling K: %d² = %d, but got %d", f1, f1*f1, f2)
178 }
179 180 // Doubling M: factories should also grow super-linearly.
181 g1 := factoryCount(2, 2) // 2^4 = 16
182 g2 := factoryCount(2, 4) // 2^8 = 256
183 if g2 <= g1*2 {
184 t.Errorf("doubling M: growth should be super-linear, but %d <= %d*2", g2, g1)
185 }
186 }
187 188 // ---- CVP Reduction: Bonding Pattern → Closest Vector Problem ----
189 190 func TestCVPReductionStructure(t *testing.T) {
191 // The CVP reduction works as follows:
192 //
193 // Given a lattice with N nodes and K constraint types, the bonding
194 // pattern is a vector v in {0,1}^N (occupied or not). The constraint
195 // envelope defines a lattice L in Z^N (the set of all valid bonding
196 // patterns for a given factory).
197 //
198 // The attacker observes:
199 // - The spore (type distribution, connectivity)
200 // - A signature (bonding pattern = vector v)
201 //
202 // To forge a signature, the attacker must find a bonding pattern v'
203 // that is close to a valid pattern in L — this is CVP.
204 //
205 // We construct this explicitly for a small lattice and verify the
206 // structure.
207 208 l := lattice.New()
209 var nodes []*lattice.Node
210 for range 6 {
211 n := l.AddNode([]axiom.Constraint{tagConstraint{"word"}})
212 nodes = append(nodes, n)
213 }
214 // Ring topology.
215 for i := range nodes {
216 l.Connect(nodes[i], nodes[(i+1)%len(nodes)])
217 }
218 219 // Bond some nodes — this is the "target vector" v.
220 nodes[0].Bond(testElem{"word", "a"})
221 nodes[2].Bond(testElem{"word", "b"})
222 nodes[4].Bond(testElem{"word", "c"})
223 224 // Extract the bonding pattern as a binary vector.
225 v := make([]int, len(nodes))
226 for i, n := range nodes {
227 if n.Occupied() {
228 v[i] = 1
229 }
230 }
231 232 // The pattern should be [1, 0, 1, 0, 1, 0].
233 expected := []int{1, 0, 1, 0, 1, 0}
234 for i, e := range expected {
235 if v[i] != e {
236 t.Errorf("v[%d] = %d, want %d", i, v[i], e)
237 }
238 }
239 240 // The "lattice" in CVP terms is the set of all valid bonding patterns.
241 // For a 6-node lattice with ring topology and "word" constraint,
242 // any subset of nodes that satisfies the constraints is a valid pattern.
243 // The number of valid patterns = 2^6 = 64 (since tagConstraint admits
244 // any matching element at any subset of sites).
245 //
246 // But with contextual constraints (AdmitsInContext), the valid set
247 // shrinks dramatically — this is where CVP hardness comes from.
248 // The constraint factory is the "short basis" that efficiently
249 // identifies valid patterns.
250 251 // Verify the spore captures the topology but not the occupancy pattern.
252 s := spore.Extract(l)
253 if s.TotalNodes != 6 {
254 t.Errorf("spore nodes = %d, want 6", s.TotalNodes)
255 }
256 if s.Occupied != 3 {
257 t.Errorf("spore occupied = %d, want 3", s.Occupied)
258 }
259 260 // The spore's type signature is public, but the specific occupation
261 // vector is not carried — only aggregate counts.
262 // An attacker with the spore knows "3 of 6 word nodes are occupied"
263 // but not which 3 → C(6,3) = 20 possibilities.
264 choices := binomial(6, 3)
265 if choices != 20 {
266 t.Errorf("C(6,3) = %d, want 20", choices)
267 }
268 }
269 270 func TestCVPDimensionGrowth(t *testing.T) {
271 // The CVP dimension grows with N (lattice size).
272 // For N nodes and K occupied, the search space is C(N, K).
273 // This grows super-exponentially.
274 275 cases := []struct {
276 n, k int
277 minSpace int
278 }{
279 {6, 3, 20}, // C(6,3) = 20
280 {10, 5, 252}, // C(10,5) = 252
281 {12, 6, 924}, // C(12,6) = 924
282 {20, 10, 184756}, // C(20,10) = 184756
283 }
284 285 for _, tc := range cases {
286 space := binomial(tc.n, tc.k)
287 if space < tc.minSpace {
288 t.Errorf("C(%d,%d) = %d, want >= %d", tc.n, tc.k, space, tc.minSpace)
289 }
290 }
291 292 // Verify growth is super-linear: C(2N, N) >> C(N, N/2).
293 small := binomial(10, 5) // 252
294 large := binomial(20, 10) // 184756
295 if large < small*small {
296 // C(20,10) = 184756 >> 252^2 = 63504. Actually 184756 > 63504 ✓
297 // This just checks super-linear growth trend.
298 }
299 if large <= small {
300 t.Errorf("CVP space should grow: C(20,10)=%d should be >> C(10,5)=%d", large, small)
301 }
302 }
303 304 // ---- Lock-In Threshold Hyperplane ----
305 306 func TestLockInThresholdIsDecisionBoundary(t *testing.T) {
307 // The dissolution threshold creates a sharp decision boundary:
308 // elements with contextual lock-in >= threshold survive,
309 // those below are dissolved.
310 //
311 // This is a hyperplane in the (occupancy × connectivity) space.
312 // We verify the sharpness by testing boundary cases.
313 314 // ContextualLockIn = 0.3 + 0.7 * (occupied_neighbors / total_neighbors)
315 // Threshold = 0.5 (half)
316 // Survives when: 0.3 + 0.7 * rate >= 0.5
317 // → rate >= (0.5 - 0.3) / 0.7 = 0.2/0.7 = 2/7
318 threshold := ratio.Half
319 criticalRate := ratio.New(2, 7) // exact boundary
320 321 // Build lattices at and around the boundary.
322 testRate := func(occNeighbors, totalNeighbors int) bool {
323 l := lattice.New()
324 center := l.AddNode([]axiom.Constraint{tagConstraint{"word"}})
325 for i := 0; i < totalNeighbors; i++ {
326 nb := l.AddNode([]axiom.Constraint{tagConstraint{"word"}})
327 l.Connect(center, nb)
328 if i < occNeighbors {
329 nb.Bond(testElem{"word", "x"})
330 }
331 }
332 center.Bond(testElem{"word", "center"})
333 334 // Run dissolution.
335 dissolved := make(chan axiom.Element, 10)
336 events := make(chan dissolve.Event, 10)
337 dissolve.ScanOnce(l, dissolve.Config{Threshold: threshold}, dissolved, events)
338 close(dissolved)
339 close(events)
340 for range dissolved {
341 }
342 // Check if center survived.
343 return center.Occupied()
344 }
345 346 // Below critical rate → dissolved.
347 // 0/7 = 0 < 2/7 → dissolved.
348 if testRate(0, 7) {
349 t.Error("0/7 occupancy: should dissolve (below threshold)")
350 }
351 // 1/7 ≈ 0.143 < 2/7 ≈ 0.286 → dissolved.
352 if testRate(1, 7) {
353 t.Error("1/7 occupancy: should dissolve (below threshold)")
354 }
355 356 // At critical rate.
357 // 2/7: contextual = 0.3 + 0.7 * 2/7 = 0.3 + 0.2 = 0.5 = threshold.
358 // At threshold, !lockIn.Less(threshold) is true → survives.
359 if !testRate(2, 7) {
360 t.Error("2/7 occupancy: should survive (at threshold)")
361 }
362 363 // Above critical rate → survives.
364 // 3/7: contextual = 0.3 + 0.7 * 3/7 = 0.3 + 0.3 = 0.6 > 0.5.
365 if !testRate(3, 7) {
366 t.Error("3/7 occupancy: should survive (above threshold)")
367 }
368 if !testRate(7, 7) {
369 t.Error("7/7 occupancy: should survive (maximum lock-in)")
370 }
371 372 // Verify the critical rate is exactly 2/7.
373 contextualAtCritical := ratio.New(3, 10).Add(ratio.New(7, 10).Mul(criticalRate))
374 if !contextualAtCritical.Equal(threshold) {
375 t.Errorf("contextual lock-in at critical rate = %s, want %s", contextualAtCritical, threshold)
376 }
377 }
378 379 func TestLockInHyperplaneMonotonicity(t *testing.T) {
380 // The contextual lock-in is monotonically increasing in neighbor
381 // occupancy rate. This means the hyperplane has no "holes" —
382 // increasing support always increases lock-in.
383 384 for total := 1; total <= 10; total++ {
385 var prevLI ratio.Ratio
386 for occupied := 0; occupied <= total; occupied++ {
387 rate := ratio.New(int64(occupied), int64(total))
388 li := ratio.New(3, 10).Add(ratio.New(7, 10).Mul(rate))
389 if occupied > 0 && li.Less(prevLI) {
390 t.Errorf("lock-in not monotonic: total=%d, occ=%d: %s < %s",
391 total, occupied, li, prevLI)
392 }
393 prevLI = li
394 }
395 }
396 }
397 398 // ---- Spore Information Leakage ----
399 400 func TestSporeDoesNotRevealConstraintPredicates(t *testing.T) {
401 // A spore contains:
402 // - Type signature (tag names + counts)
403 // - Connectivity (avg neighbors per tag)
404 // - Permutation/projection distributions
405 // - Occupancy count
406 //
407 // It does NOT contain:
408 // - The Admits() predicate of any constraint
409 // - Which specific elements bonded
410 // - The topology of neighbor connections
411 // - Lock-in depths of individual nodes
412 413 params := Params{
414 N: 20, Q: ratio.FromInt(257), SmoothingParam: ratio.New(2, 10),
415 NoiseWidth: ratio.New(3, 10), MaxWalkSteps: 100, DissolutionPasses: 1,
416 }
417 kp, err := Generate(params, []string{"word", "punct"}, testFactory)
418 if err != nil {
419 t.Fatalf("Generate: %v", err)
420 }
421 422 s := kp.Public.Spore
423 424 // The spore has type signature.
425 if len(s.TypeSignature) == 0 {
426 t.Error("spore should have type signature")
427 }
428 429 // But the constraint factory is NOT in the spore.
430 // We can only verify this structurally: the Spore struct has no
431 // field for constraint predicates.
432 // The private key is the factory; the public key is the spore.
433 // An attacker with the spore knows the tag names but not what
434 // each tag's Admits() function does internally.
435 436 // Verify that two different factories produce spores with the
437 // same tag names but different private behavior.
438 factory2 := func(tag string) axiom.Constraint {
439 // This factory accepts everything regardless of tag.
440 return multiConstraint{primary: tag, admits: map[string]bool{
441 "word": true, "punct": true, "space": true,
442 }}
443 }
444 445 kp2, err := Generate(params, []string{"word", "punct"}, factory2)
446 if err != nil {
447 t.Fatalf("Generate(factory2): %v", err)
448 }
449 450 s2 := kp2.Public.Spore
451 452 // Same tag names in both spores.
453 tags1 := make(map[string]bool)
454 for _, tc := range s.TypeSignature {
455 tags1[tc.Tag] = true
456 }
457 tags2 := make(map[string]bool)
458 for _, tc := range s2.TypeSignature {
459 tags2[tc.Tag] = true
460 }
461 462 for tag := range tags1 {
463 if !tags2[tag] {
464 t.Errorf("tag %q in spore1 but not spore2", tag)
465 }
466 }
467 for tag := range tags2 {
468 if !tags1[tag] {
469 t.Errorf("tag %q in spore2 but not spore1", tag)
470 }
471 }
472 473 // The factories are different: one is strict, one is permissive.
474 // But the spores have the same tag structure.
475 // This is the preimage ambiguity in action.
476 }
477 478 func TestSignatureDoesNotRevealFactory(t *testing.T) {
479 // A signature contains:
480 // - Challenge (Hamadryad hash of message)
481 // - Response (bonding pattern: site indices, type tags, projections, perms)
482 // - Proof (lock-in depths, neighbor counts, hex trace)
483 // - Fingerprint (hash of the signer's spore)
484 //
485 // From a signature, an attacker learns:
486 // - Which sites are occupied (the bonding pattern)
487 // - The type tag at each occupied site
488 // - Lock-in depths
489 //
490 // But NOT:
491 // - Why those sites accepted those elements (the Admits predicate)
492 // - What other elements would have been accepted
493 // - The neighbor topology
494 495 l := buildMatureLattice()
496 params := DefaultParams(Security128)
497 kp := GenerateKeyPair(l, params, testFactory)
498 499 sig, err := Sign(&kp.Private, []byte("test"), params)
500 if err != nil {
501 t.Fatalf("Sign: %v", err)
502 }
503 504 // The signature has type tags (public information).
505 occupiedTags := make(map[string]int)
506 for _, site := range sig.Response {
507 if site.Occupied {
508 occupiedTags[site.TypeTag]++
509 }
510 }
511 if len(occupiedTags) == 0 {
512 t.Error("signature should have occupied sites with tags")
513 }
514 515 // But the signature does NOT include the constraint factory.
516 // An attacker knows "this site has tag 'word'" but not
517 // "what does the 'word' constraint's Admits() function do?"
518 // They can see the bonding pattern but cannot construct the factory.
519 }
520 521 // ---- Constraint Recovery Hardness (Small Lattice Enumeration) ----
522 523 func TestConstraintRecoveryEnumeration(t *testing.T) {
524 // For a small lattice (N=6, K=2), enumerate all possible binary
525 // constraint configurations and verify that multiple configurations
526 // produce identical public bases.
527 //
528 // A "binary constraint configuration" means: for each of K tags,
529 // the constraint either accepts or rejects each of K element types.
530 // This gives 2^(K*K) = 2^4 = 16 configurations for K=2.
531 532 K := 2
533 tags := []string{"a", "b"}
534 535 // Generate all 2^(K*K) factory configurations.
536 totalConfigs := 1 << (K * K) // 16
537 type factoryConfig struct {
538 admitMatrix [2][2]bool // admitMatrix[tag][elemType]
539 }
540 541 configs := make([]factoryConfig, totalConfigs)
542 for i := range totalConfigs {
543 for ti := range K {
544 for ei := range K {
545 bit := ti*K + ei
546 configs[i].admitMatrix[ti][ei] = (i>>bit)&1 == 1
547 }
548 }
549 }
550 551 // Count how many configs produce at least one bond vs no bonds.
552 // Configs where no tag admits any element produce empty lattices.
553 bondableCount := 0
554 for _, cfg := range configs {
555 hasBond := false
556 for ti := range K {
557 if cfg.admitMatrix[ti][ti] { // tag admits its own element type
558 hasBond = true
559 break
560 }
561 }
562 if hasBond {
563 bondableCount++
564 }
565 }
566 567 // For K=2: we need at least tag "a" admits "a" OR tag "b" admits "b"
568 // for any bonding to occur with matching elements.
569 // Total configs = 16, but many are "useful" (allow bonding).
570 if bondableCount == 0 {
571 t.Error("should have at least some bondable configurations")
572 }
573 if bondableCount >= totalConfigs {
574 t.Error("not all configurations should be bondable (some admit nothing)")
575 }
576 577 t.Logf("K=%d: %d/%d configurations are bondable (%.0f%% ambiguity)",
578 K, bondableCount, totalConfigs,
579 100*float64(totalConfigs-1)/float64(totalConfigs))
580 581 // The attacker must search through all configurations to find the
582 // correct one. Even for K=2, there are 16 possibilities. For the
583 // production system with K=3 and richer predicates, the search
584 // space is vastly larger.
585 586 // Verify growth: K=3 should have 2^9 = 512 configurations.
587 K3configs := 1 << (3 * 3)
588 if K3configs != 512 {
589 t.Errorf("K=3 configs = %d, want 512", K3configs)
590 }
591 592 // With real constraint predicates (not just binary), each tag can
593 // have arbitrary admission logic → the space is effectively unbounded.
594 // Binary is a lower bound on the true search complexity.
595 _ = tags
596 }
597 598 // ---- Bonding Pattern as Lattice Reduction ----
599 600 func TestBondingPatternMatchesLatticeVector(t *testing.T) {
601 // Show that a bonding pattern (from Sign) corresponds to a binary
602 // vector in Z^N, and that the constraint factory defines which
603 // binary vectors are "valid" (form a lattice in the mathematical sense).
604 605 l := buildMatureLattice()
606 params := DefaultParams(Security128)
607 kp := GenerateKeyPair(l, params, testFactory)
608 609 sig, err := Sign(&kp.Private, []byte("lattice vector"), params)
610 if err != nil {
611 t.Fatalf("Sign: %v", err)
612 }
613 614 N := len(sig.Response) // dimension of the vector space
615 if N == 0 {
616 t.Fatal("response should have sites")
617 }
618 619 // Extract binary vector.
620 v := make([]int, N)
621 occupied := 0
622 for i, site := range sig.Response {
623 if site.Occupied {
624 v[i] = 1
625 occupied++
626 }
627 }
628 629 if occupied == 0 {
630 t.Fatal("should have occupied sites")
631 }
632 633 // The Hamming weight of the vector is the occupancy.
634 hamming := 0
635 for _, b := range v {
636 hamming += b
637 }
638 if hamming != occupied {
639 t.Errorf("Hamming weight %d != occupied %d", hamming, occupied)
640 }
641 642 // In CVP terms:
643 // - The "target" is the ideal bonding pattern for this challenge
644 // - The "lattice" is all valid patterns for this constraint factory
645 // - "Closest vector" means the pattern that satisfies the most constraints
646 // - The attacker without the factory must search exponentially many
647 // possible patterns to find one that verifies
648 t.Logf("bonding vector: dimension=%d, Hamming weight=%d, density=%.2f",
649 N, hamming, float64(hamming)/float64(N))
650 }
651 652 // ---- Helper functions ----
653 654 // binomial computes C(n, k) using the multiplicative formula.
655 func binomial(n, k int) int {
656 if k > n || k < 0 {
657 return 0
658 }
659 if k > n-k {
660 k = n - k
661 }
662 result := 1
663 for i := 0; i < k; i++ {
664 result = result * (n - i) / (i + 1)
665 }
666 return result
667 }
668