Refinement Metrics for Quantitative Information Flow

Konstantinos Chatzikokolakis (1, 2) , Geoffrey Smith (3)

1 NKUA - National and Kapodistrian University of Athens
2 COMETE - Concurrency, Mobility and Transactions
3 FIU | CIS - Knight Foundation - School of Computing and Information Sciences [Miami]

In Quantitative Information Flow, refinement expresses the strong property that one channel never leaks more than another. Since two channels are then typically incomparable, here we explore a family of refinement quasimetrics offering greater flexibility. We show these quasimetrics let us unify refinement and capacity, we show that some of them can be computed efficiently via linear programming, and we establish upper bounds via the Earth Mover's distance. We illustrate our techniques on the Crowds protocol.

Domaines: Informatique [cs]; Cryptographie et sécurité [cs.CR]

Konstantinos Chatzikokolakis, Geoffrey Smith. Refinement Metrics for Quantitative Information Flow. Mário S. Alvim; Kostas Chatzikokolakis; Carlos Olarte; Frank Valencia. The Art of Modelling Computational Systems: A Journey from Logic and Concurrency to Security and Privacy. Essays Dedicated to Catuscia Palamidessi on the Occasion of Her 60th Birthday., 11760, Springer, pp.397-416, 2019, Lecture Notes in Computer Science, 978-3-030-31174-2. ⟨10.1007/978-3-030-31175-9_23⟩. ⟨hal-02350777⟩