On the computation of covert channel
capacity (joint work with E. Asarin)
We address the problem of computing the capacity of a covert channel, modeled as a nondeterministic transducer. We give three possible statements of the notion of ``covert channel capacity'' and relate the different definitions. We then provide several methods allowing the computation of lower and upper bounds for the capacity of a channel. We show that, in some cases, including the case of input-deterministic channels, the capacity of the channel can be computed exactly (e.g. in the form of ``the largest root of some polynomial'').
RAIRO – Informatique Théorique et Applications, vol. 44, p. 37-58, 2010. Preliminary version presented at Journées Montoises 2008, Mons, Belgium, September 1-4 2008.