Abstract
The observable output of a probabilistic system that processes a secret input might reveal some information about that input. The system can be modelled as an information-theoretic channel that specifies the probability of each output, given each input. Given a prior distribution on those inputs, entropy-like measures can then quantify the amount of information leakage caused by the channel. But it turns out that the conventional channel representation, as a matrix, contains structure that is redundant with respect to that leakage, such as the labeling of columns, and columns that are scalar multiples of each other. We therefore introduce abstract channels by quotienting over those redundancies.
A fundamental question for channels is whether one is worse than another, from a leakage point of view. But it is difficult to answer this question robustly, given the multitude of possible prior distributions and leakage measures. Indeed, there is growing recognition that different leakage measures are appropriate in different circumstances, leading to the recently proposed g-leakage measures, which use gain functions g to model the operational scenario in which a channel operates: the strong g-leakage pre-order requires that channel A never leak more than channel B, for any prior and any gain function. Here we show that, on abstract channels, the strong g-leakage pre-order is antisymmetric, and therefore a partial order.
It was previously shown [1] that the strong g-leakage ordering is implied by a structural ordering called composition refinement, which requires that A = BR, for some channel R; but the converse was not established in full generality, left open as the so-called Coriaceous Conjecture. Using ideas from [2], we here confirm the Coriaceous Conjecture. Hence the strong g-leakage ordering and composition refinement coincide, giving our partial order both structural- and leakage-testing significance.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Alvim, M.S., Chatzikokolakis, K., Palamidessi, C., Smith, G.: Measuring information leakage using generalized gain functions. In: Proc. 25th IEEE Computer Security Foundations Symposium (CSF 2012), pp. 265–279 (June 2012)
McIver, A., Meinicke, L., Morgan, C.: Compositional closure for Bayes risk in probabilistic noninterference. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010. LNCS, vol. 6199, pp. 223–235. Springer, Heidelberg (2010)
Shannon, C.E.: A mathematical theory of communication. Bell System Technical Journal 27, 379–423, 623–656 (1948)
Massey, J.L.: Guessing and entropy. In: Proc. 1994 IEEE International Symposium on Information Theory, p. 204 (1994)
Smith, G.: On the foundations of quantitative information flow. In: de Alfaro, L. (ed.) FOSSACS 2009. LNCS, vol. 5504, pp. 288–302. Springer, Heidelberg (2009)
Landauer, J., Redmond, T.: A lattice of information. In: Proc. 6th IEEE Computer Security Foundations Workshop (CSFW 1993), pp. 65–70 (June 1993)
Yasuoka, H., Terauchi, T.: Quantitative information flow — verification hardness and possibilities. In: Proc. 23rd IEEE Computer Security Foundations Symposium (CSF 2010), pp. 15–27 (2010)
Malacaria, P.: Algebraic foundations for information theoretical, probabilistic and guessability measures of information flow. CoRR abs/1101.3453 (2011)
McIver, A., Meinicke, L., Morgan, C.: Compositional closure for Bayes risk in probabilistic noninterference. CoRR abs/1007.1054 (2010) (Draft full version of [2] with appendices)
Cover, T.M., Thomas, J.A.: Elements of Information Theory, 2nd edn. John Wiley & Sons, Inc. (2006)
McIver, A., Meinicke, L., Morgan, C.: Hidden-Markov program algebra with iteration. At arXiv:1102.0333v1 (2011) (To appear in Mathematical Structures in Computer Science in 2012)
Desoer, C.A.: Communication through channels in cascade. PhD thesis, Massachusetts Institute of Technology (1953)
Gallager, R.G.: Information Theory and Reliable Communication. John Wiley & Sons, Inc. (1968)
McIver, A., Meinicke, L., Morgan, C.: Draft proof of the Coriaceous Conjecture (November 2012), http://www.dagstuhl.de/mat/index.en.phtml?12481
McIver, A., Morgan, C.: Abstraction, Refinement and Proof for Probabilistic Systems. Technical Monographs in Computer Science. Springer, New York (2005)
Trustrum, K.: Linear Programming. Library of Mathematics. Routledge and Kegan Paul, London (1971)
McIver, A., Meinicke, L., Morgan, C.: A Kantorovich-monadic powerdomain for information hiding, with probability and nondeterminism. In: Proc. 27th IEEE Symposium on Logic in Computer Science (LICS 2012), pp. 461–470 (2012)
van Breugel, F.: The metric monad for probabilistic nondeterminism (2005), Draft available at http://www.cse.yorku.ca/~franck/research/drafts/monad.pdf
Giry, M.: A categorical approach to probability theory. In: Categorical Aspects of Topology and Analysis. Lecture Notes in Mathematics, vol. 915, pp. 68–85. Springer (1981)
Pliam, J.O.: On the incomparability of entropy and marginal guesswork in brute-force attacks. In: Roy, B., Okamoto, E. (eds.) INDOCRYPT 2000. LNCS, vol. 1977, pp. 67–79. Springer, Heidelberg (2000)
Santhi, N., Vardy, A.: On an improvement over Rényi’s equivocation bound. In: 44th Annual Allerton Conference on Communication, Control, and Computing (2006)
Chatzikokolakis, K., Palamidessi, C., Panangaden, P.: On the Bayes risk in information-hiding protocols. Journal of Computer Security 16(5), 531–571 (2008)
Braun, C., Chatzikokolakis, K., Palamidessi, C.: Quantitative notions of leakage for one-try attacks. In: Proc. 25th Conference on Mathematical Foundations of Programming Semantics (MFPS 2009). ENTCS, vol. 249, pp. 75–91 (2009)
Sabelfeld, A., Sands, D.: A PER model of secure information flow. Higher-Order and Symbolic Computation 14(1), 59–91 (2001)
Braun, C., Chatzikokolakis, K., Palamidessi, C.: Compositional methods for information-hiding. In: Amadio, R.M. (ed.) FOSSACS 2008. LNCS, vol. 4962, pp. 443–457. Springer, Heidelberg (2008)
McIver, A., Morgan, C., Meinicke, L., Smith, G., Espinoza, B.: Abstract channels, gain functions and the information order. In: FCS 2013 Workshop on Foundations of Computer Security (2013), http://prosecco.gforge.inria.fr/personal/bblanche/fcs13/fcs13proceedings.pdf
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
McIver, A., Morgan, C., Smith, G., Espinoza, B., Meinicke, L. (2014). Abstract Channels and Their Robust Information-Leakage Ordering. In: Abadi, M., Kremer, S. (eds) Principles of Security and Trust. POST 2014. Lecture Notes in Computer Science, vol 8414. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-54792-8_5
Download citation
DOI: https://doi.org/10.1007/978-3-642-54792-8_5
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-54791-1
Online ISBN: 978-3-642-54792-8
eBook Packages: Computer ScienceComputer Science (R0)