Fighting Censorship with Algorithms

A dynamic binary-tree partitioning algorithm solves the proxy distribution problem with at most k(1 + ⌈log₂(n/k)⌉) total proxy keys: partition n users into k groups in round 1, then halve each compromised group on each compromise event. Each of k adversaries can trigger at most ⌈log₂(n/k)⌉ compromises, bounding total proxy expenditure tightly.

§4 Theorem 3 defense ip-blocking cnir

A simple entropy argument proves the dynamic key distribution problem requires at least Ω(k log(n/k) / log(k + log n)) keys: the algorithm must identify which k of n users are adversaries from at most ℓ log ℓ bits of feedback (ℓ round outcomes each indexing one of ℓ keys), and distinguishing among C(n,k) adversary sets requires log C(n,k) = Ω(k log(n/k)) bits.

§4 Theorem 6 evaluation generic

The static proxy distribution problem — giving k²-adversarial users keys from m proxies so that all n−k legitimate users retain at least one uncompromised proxy — requires at most O(k² log n) keys and cannot be solved with fewer than Ω(k log(n/k)) keys. This establishes the information-theoretic cost of one-shot proxy distribution against k colluding informants among n users.

§3 Theorem 2 defense ip-blocking cnir

By reusing keys already held by trusted (non-suspicious) users for ℓ−1 of ℓ subgroups when bisecting the suspicious cohort — issuing only one fresh key per round — the total proxy count drops from O(k log n) to O(k² log n / log log n) in expectation. The information-theoretic lower bound is Ω(k log(n/k) / log(k + log n)), so this bound is tight in n up to a factor of k.

§4 Theorems 4–6 defense ip-blocking generic

In invitation-based proxy networks (modeled on Psiphon's trust-tree), a single adversary can invite fake accounts as children in the trust tree, multiplying the effective adversary count k and invalidating sublogarithmic key budgets. For k=1 adversary on a trust tree of depth O(log n), an O(log n)-key algorithm exists by keeping the 'suspicious group' always rooted at a subtree boundary; for k>1 this remains an open problem.

§5 Theorem 7 defense ip-blocking cnir