×

zbMATH — the first resource for mathematics

On the foundations of quantitative information flow. (English) Zbl 1234.68101
de Alfaro, Luca (ed.), Foundations of software science and computational structures. 12th international conference, FOSSACS 2009, held as part of the joint European conferences on theory and practice of software, ETAPS 2009, York, UK, March 22–29, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-00595-4/pbk). Lecture Notes in Computer Science 5504, 288-302 (2009).
Summary: There is growing interest in quantitative theories of information flow in a variety of contexts, such as secure information flow, anonymity protocols, and side-channel analysis. Such theories offer an attractive way to relax the standard noninterference properties, letting us tolerate “small” leaks that are necessary in practice. The emerging consensus is that quantitative information flow should be founded on the concepts of Shannon entropy and mutual information. But a useful theory of quantitative information flow must provide appropriate security guarantees: if the theory says that an attack leaks \(x\) bits of secret information, then \(x\) should be useful in calculating bounds on the resulting threat. In this paper, we focus on the threat that an attack will allow the secret to be guessed correctly in one try. With respect to this threat model, we argue that the consensus definitions actually fail to give good security guarantees – the problem is that a random variable can have arbitrarily large Shannon entropy even if it is highly vulnerable to being guessed. We then explore an alternative foundation based on a concept of vulnerability (closely related to Bayes risk) and which measures uncertainty using Rényi’s min-entropy, rather than Shannon entropy.
For the entire collection see [Zbl 1157.68009].

MSC:
68P30 Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science)
94A15 Information theory (general)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Sabelfeld, A., Myers, A.C.: Language-based information flow security. IEEE Journal on Selected Areas in Communications 21(1), 5–19 (2003) · doi:10.1109/JSAC.2002.806121
[2] Chatzikokolakis, K., Palamidessi, C., Panangaden, P.: Anonymity protocols as noisy channels. Information and Computation 206, 378–401 (2008) · Zbl 1147.68394 · doi:10.1016/j.ic.2007.07.003
[3] Köpf, B., Basin, D.: An information-theoretic model for adaptive side-channel attacks. In: Proceedings 14th ACM Conference on Computer and Communications Security, Alexandria, Virginia (2007) · doi:10.1145/1315245.1315282
[4] Sabelfeld, A., Sands, D.: Dimensions and principles of declassification. In: Proceedings 18th IEEE Computer Security Foundations Workshop (June 2005) · doi:10.1109/CSFW.2005.15
[5] Denning, D.: Cryptography and Data Security. Addison-Wesley, Reading (1982) · Zbl 0573.68001
[6] Gray III, J.W.: Probabilistic interference. In: Proceedings 1990 IEEE Symposium on Security and Privacy, Oakland, CA, pp. 170–179 (May 1990) · doi:10.1109/RISP.1990.63848
[7] Clark, D., Hunt, S., Malacaria, P.: Quantitative analysis of the leakage of confidential data. Electronic Notes in Theoretical Computer Science 59(3) (2002) · doi:10.1016/S1571-0661(04)00290-7
[8] Clark, D., Hunt, S., Malacaria, P.: Quantitative information flow, relations and polymorphic types. Journal of Logic and Computation 18(2), 181–199 (2005) · Zbl 1101.68560 · doi:10.1093/logcom/exi009
[9] Clark, D., Hunt, S., Malacaria, P.: A static analysis for quantifying information flow in a simple imperative language. Journal of Computer Security 15, 321–371 (2007) · Zbl 05430439 · doi:10.3233/JCS-2007-15302
[10] Malacaria, P.: Assessing security threats of looping constructs. In: Proceedings 34th Symposium on Principles of Programming Languages, Nice, France, pp. 225–235 (January 2007) · Zbl 1295.68089 · doi:10.1145/1190216.1190251
[11] Malacaria, P., Chen, H.: Lagrange multipliers and maximum information leakage in different observational models. In: Proc. PLAS 2008: ACM SIGPLAN Workshop on Programming Languages and Analysis for Security, Tucson, Arizona, USA, pp. 135–146 (June 2008) · doi:10.1145/1375696.1375713
[12] Clarkson, M., Myers, A., Schneider, F.: Belief in information flow. In: Proceedings 18th IEEE Computer Security Foundations Workshop, Aix-en-Provence, France, pp. 31–45 (June 2005) · doi:10.1109/CSFW.2005.10
[13] Chatzikokolakis, K., Palamidessi, C., Panangaden, P.: Probability of error in information-hiding protocols. In: Proceedings 20th IEEE Computer Security Foundations Symposium, pp. 341–354 (2007) · doi:10.1109/CSF.2007.27
[14] Lowe, G.: Quantifying information flow. In: Proceedings 15th IEEE Computer Security Foundations Workshop, Cape Breton, Nova Scotia, Canada, pp. 18–31 (June 2002) · doi:10.1109/CSFW.2002.1021804
[15] Di Pierro, A., Hankin, C., Wiklicky, H.: Approximate non-interference. In: Proceedings 15th IEEE Computer Security Foundations Workshop, Cape Breton, Nova Scotia, Canada, pp. 1–17 (June 2002) · Zbl 1015.68069 · doi:10.1109/CSFW.2002.1021803
[16] Rényi, A.: On measures of entropy and information. In: Proceedings of the 4th Berkeley Symposium on Mathematics, Statistics and Probability 1960, pp. 547–561 (1961)
[17] Tóth, G., Hornák, Z., Vajda, F.: Measuring anonymity revisited. In: Liimatainen, S., Virtanen, T. (eds.) Proceedings of the Ninth Nordic Workshop on Secure IT Systems, Espoo, Finland, pp. 85–90 (2004)
[18] Shmatikov, V., Wang, M.H.: Measuring relationship anonymity in mix networks. In: WPES 2006: Proceedings of the 5th ACM workshop on Privacy in Electronic Society, Alexandria, Virginia, pp. 59–62 (2006) · doi:10.1145/1179601.1179611
[19] Smith, G.: Adversaries and information leaks (Tutorial). In: Barthe, G., Fournet, C. (eds.) TGC 2007. LNCS, vol. 4912, pp. 383–400. Springer, Heidelberg (2008) · Zbl 05256631 · doi:10.1007/978-3-540-78663-4_25
[20] Shannon, C.E.: A mathematical theory of communication. Bell System Technical Journal 27, 379–423 (1948) · Zbl 1154.94303 · doi:10.1002/j.1538-7305.1948.tb01338.x
[21] Gallager, R.G.: Information Theory and Reliable Communication. John Wiley and Sons, Inc., Chichester (1968) · Zbl 0198.52201
[22] Cover, T.M., Thomas, J.A.: Elements of Information Theory, 2nd edn. John Wiley & Sons, Inc., Chichester (2006) · Zbl 1140.94001
[23] Massey, J.L.: Guessing and entropy. In: Proceedings 1994 IEEE International Symposium on Information Theory, p. 204 (1994) · doi:10.1109/ISIT.1994.394764
[24] Cachin, C.: Entropy Measures and Unconditional Security in Cryptography. PhD thesis, Swiss Federal Institute of Technology (1997)
[25] Dodis, Y., Ostrovsky, R., Reyzin, L., Smith, A.: Fuzzy extractors: How to generate strong keys from biometrics and other noisy data. SIAM Journal of Computing 38(1), 97–139 (2008) · Zbl 1165.94326 · doi:10.1137/060651380
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.