Affiliations: [a] INRIA and LIX, École Polytechnique Palaiseau, Palaiseau, France | [b] Institute for Computing and Information Sciences, Radboud University, Nijmegen, The Netherlands
Correspondence:
[*]
Corresponding author: Catuscia Palamidessi, LIX, École Polytechnique, Rue de Saclay, 91128 Palaiseau Cedex, France. Tel.: +33 1 69 33 41 17; E-mail: [email protected].
Abstract: We consider the problem of defining the information leakage in interactive systems where secrets and observables can alternate during the computation. We show that the information-theoretic approach which interprets such systems as (simple) noisy channels is no longer valid. However, the principle can be recovered if we consider channels of a more complicated kind, that in Information Theory are known as channels with memory and feedback. We show that there is a complete correspondence between interactive systems and such channels. Furthermore, we show that the capacity of the channels associated to such systems is a continuous function with respect to a pseudometric based on the Kantorovich metric.
Keywords: Probabilistic systems, information flow and anonymity, information-theoretic channel, Kantorovich metric
