FINDING · DEFENSE

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.

From 2010-mahdian-fighting — Fighting Censorship with Algorithms · §3 Theorem 2 · 2010 · International Conference on Fun with Algorithms

Implications

For one-shot proxy lists broadcast to n users with an estimated k% informant rate, budget O(k² log n) distinct proxy addresses — far more than naively expected — to guarantee all legitimate users survive a single compromise cycle.
Any static distribution scheme with fewer than Ω(k log(n/k)) proxies is provably breakable; treat that as a hard floor when sizing bridge pools.