Information-Theoretic Deniability and the Forest Analogy

Information-Theoretic Deniability and the Forest Analogy This paper establishes information-theoretic deniability through a precise structural argument: the Forest Analogy. The central result is a symmetry property showing that an attacker who possesses a valid alibi chain stands in exactly the same position as an attacker who knows only the public parameter N. The verification function cannot distinguish the real authentication chain from any alibi chain. This property holds without cryptographic assumptions — it is information-theoretic, not computational. The authentication chain is built on the linear Diophantine system N = 19A + 9B, in which every number N has approximately N/171 valid representations per layer. A three-layer Matryoshka structure produces a multiplicatively structured search space of approximately 10¹¹² operations. The key insight is that this search space is symmetric: it is equally large and equally unnavigable from outside the system as from within it. Uniform Sampling and the Generation Algorithm Uniform sampling means here that every valid chain — consisting of A, B, a1, b1, a2, b2 satisfying 19A + 9B = N, 19a1 + 9b1 = A, 19a2 + 9b2 = a1, and the digit-root conditions — has exactly equal probability of being generated as the real authentication chain. The generation algorithm achieves this through a hierarchical weighted CDF sampler (cumulative distribution function), operating as follows: 1. The distribution over all valid A-values is computed, where the weight assigned to a given A equals the exact number of valid chains on layers 1 and 2 that can be extended from that A. 2. A is sampled according to this weighted distribution. 3. Given A, the value a1 is sampled in the same manner, with weights determined by the exact number of valid (a2, b2) -pairs beneath that a1. 4. Finally, (a2, b2) is chosen uniformly at random from all solutions to 19a2 + 9b2 = a1. All weights are computed exactly. This hierarchical weighted sampling procedure therefore induces a provably uniform distribution over all complete chains, without requiring the generator to enumerate or store them explicitly. Proposition (Uniform Chain Distribution): Let N be a fixed public parameter. Let Omega (N) denote the set of all valid chains C = (A, B, a1, b1, a2, b2) satisfying: - 19A + 9B = N - 19a1 + 9b1 = A - 19a2 + 9b2 = a1 - and the digit-root conditions on each layer. Then the hierarchical weighted CDF sampler generates each chain C in Omega (N) with probability exactly 1 / |Omega (N) |. Proof. Define the following counting functions: - w2 (a1) = | (a2, b2): 19a2 + 9b2 = a1, digit-root conditions satisfied| - w1 (A) = sum over all valid a1 of w2 (a1), where the sum runs over all a1 satisfying 19a1 + 9b1 = A for some valid b1 - w0 = sum over all valid A of w1 (A) = |Omega (N) | The sampler proceeds in three steps: Step 1. A is drawn with probability P (A) = w1 (A) / w0. Step 2. Given A, a1 is drawn with probability P (a1 | A) = w2 (a1) / w1 (A). Step 3. Given a1, the pair (a2, b2) is drawn uniformly with probability P (a2, b2 | a1) = 1 / w2 (a1). The joint probability of generating the complete chain C = (A, B, a1, b1, a2, b2) is: P (C) = P (A) * P (a1 | A) * P (a2, b2 | a1) = w1 (A) / w0 * w2 (a1) / w1 (A) * 1 / w2 (a1) = 1 / w0 = 1 / |Omega (N) | Since this holds for every C in Omega (N), the sampler induces the uniform distribution over Omega (N). "Remark" B and b1 are uniquely determined once A, a1, a2, and b2 are fixed, via the Diophantine equations. They do not need to be sampled separately. The uniformity therefore holds over all complete chains, including these values. Theorem (Forest Symmetry): Let N be a public parameter and let C = (A, B, a1, b1, a2, b2) be any valid verification chain. Then for every valid alibi chain C': P (C is authentic | verification succeeds, C') = P (C is authentic | verification succeeds) Proof: The verification function evaluates solely against N. By Proposition (Uniform Chain Distribution), every valid chain is generated with identical probability 1 / |Omega (N) |. The alibi C' therefore carries no information about which chain is authentic. Formally, C' and the event "C is authentic" are conditionally independent given that verification succeeds. The posterior probability is thus unaffected by knowledge of C'. The Forest Analogy: The Forest Analogy makes the symmetry precise. The public parameter N is the forest. Each representation (A, B) on layer zero is a tree. Each sub-representation on layer one is a branch. Each leaf is a layer-two representation. All leaves are identical — every chain verifies correctly against N. An attacker holding a valid alibi leaf cannot determine which leaf is the real one, because the verification function provides no distinguishing information. *This work is licensed under CC BY-SA 4. 0. Commercial licensing (without ShareAlike) available on request: elissaₒui@outlook. com*