zbMATH — the first resource for mathematics

Anonymity protocols as noisy channels. (English) Zbl 1147.68394
Summary: We consider a framework in which anonymity protocols are interpreted as noisy channels in the information-theoretic sense, and we explore the idea of using the notion of capacity as a measure of the loss of anonymity. Such idea was already suggested by Moskowitz, Newman and Syverson, in their analysis of the covert channel that can be created as a result of non-perfect anonymity. We consider the case in which some leak of information is intended by design, and we introduce the notion of conditional capacity to rule out this factor, thus retrieving a natural correspondence with the notion of anonymity. Furthermore, we show how to compute the capacity and the conditional capacity when the anonymity protocol satisfies certain symmetries. We also investigate how the adversary can test the system to try to infer the user’s identity, and we study how his probability of success depends on the characteristics of the channel. We then illustrate how various notions of anonymity can be expressed in this framework, and show the relation with some definitions of probabilistic anonymity in literature. Finally, we show how to compute the matrix of the channel (and hence the capacity and conditional capacity) using model checking.

68M12 Network protocols
model checking
Full Text: DOI
[1] Schneider, S.; Sidiropoulos, A., CSP and anonymity, (), 198-218
[2] Ryan, P.Y.; Schneider, S., Modelling and analysis of security protocols, (2001), Addison-Wesley
[3] P.F. Syverson, S.G. Stubblebine, Group principals and the formalization of anonymity, in: World Congress on Formal Methods (1), 1999, pp. 814-833. · Zbl 0948.94013
[4] Halpern, J.Y.; O’Neill, K.R., Anonymity and information hiding in multiagent systems, Journal of computer security, 13, 3, 483-512, (2005)
[5] Hughes, D.; Shmatikov, V., Information hiding anonymity and privacy: a modular approach, Journal of computer security, 12, 1, 3-36, (2004)
[6] Sweene, L., K-anonymity: a model for protecting privacy, International journal of uncertainty, fuzziness and knowledge-based systems, 10, 5, 557-570, (2002) · Zbl 1085.68589
[7] Sweene, L., Achieving k-anonymity privacy protection using generalization and suppression, International journal of uncertainty, fuzziness and knowledge-based systems, 10, 5, 571-588, (2002) · Zbl 1084.68537
[8] Chaum, D., The dining cryptographers problem: unconditional sender and recipient untraceability, Journal of cryptology, 1, 65-75, (1988) · Zbl 0654.94012
[9] Bhargava, M.; Palamidessi, C., Probabilistic anonymity, (), 171-185 · Zbl 1134.68426
[10] Reiter, M.K.; Rubin, A.D., Crowds: anonymity for web transactions, ACM transactions on information and system security, 1, 1, 66-92, (1998)
[11] Chatzikokolakis, K.; Palamidessi, C., Probable innocence revisited, Theoretical computer science, 367, 1-2, 123-138, (2006) · Zbl 1153.94451
[12] Serjantov, A.; Danezis, G., Towards an information theoretic metric for anonymity, (), 41-53 · Zbl 1045.68913
[13] Díaz, C.; Seys, S.; Claessens, J.; Preneel, B., Towards measuring anonymity, (), 54-68 · Zbl 1045.68694
[14] I.S. Moskowitz, R.E. Newman, D.P. Crepeau, A.R. Miller, Covert channels and anonymizing networks, in: S. Jajodia, P. Samarati, P.F. Syverson (Eds.), WPES, ACM, 2003, pp. 79-88.
[15] I.S. Moskowitz, R.E. Newman, P.F. Syverson, Quasi-anonymous channels, in: IASTED CNIS, 2003, pp. 126-131.
[16] Y. Zhu, R. Bettati, Anonymity vs. information leakage in anonymity systems, in: Proc. of ICDCS, IEEE Computer Society, 2005, pp. 514-524.
[17] M.R. Clarkson, A.C. Myers, F.B. Schneider, Belief in information flow, in: Proceedings of the 18th IEEE Computer Security Foundations Workshop (CSFW’05), IEEE, 2005, pp. 31-45.
[18] Deng, Y.; Pang, J.; Wu, P., Measuring anonymity with relative entropy, (), 65-79
[19] J. McLean, Security models and information flow, in: IEEE Symposium on Security and Privacy, 1990, pp. 180-189.
[20] J.W. Gray, III, Toward a mathematical foundation for information flow security, in: Proceedings of the 1991 IEEE Computer Society Symposium on Research in Security and Privacy (SSP ’91), IEEE, Washington- Brussels-Tokyo, 1991, pp. 21-35.
[21] D. Clark, S. Hunt, P. Malacaria, Quantitative analysis of the leakage of confidential data, in: Proc. of QAPL 2001, Electr. Notes Theor. Comput. Sci., vol. 59 (3), Elsevier Science B.V., 2001, pp. 238-251.
[22] Clark, D.; Hunt, S.; Malacaria, P., Quantified interference for a while language, (), 149-166 · Zbl 1272.68100
[23] Lowe, G., Quantifying information flow, (), 18-31
[24] Maurer, U.M., Authentication theory and hypothesis testing, IEEE transactions on information theory, 46, 4, 1350-1356, (2000) · Zbl 1001.94033
[25] Pierro, A.D.; Hankin, C.; Wiklicky, H., Approximate non-interference, Journal of computer security, 12, 1, 37-82, (2004)
[26] Pierro, A.D.; Hankin, C.; Wiklicky, H., Measuring the confinement of probabilistic systems, Theoretical computer science, 340, 1, 3-56, (2005) · Zbl 1142.68444
[27] Cover, T.M.; Thomas, J.A., Elements of information theory, (1991), John Wiley & Sons, Inc. · Zbl 0762.94001
[28] Sabelfeld, A.; Sands, D., Probabilistic noninterference for multi-threaded programs, (), 200-214
[29] Y. Deng, C. Palamidessi, J. Pang, Weak probabilistic anonymity, in: Proceedings of the 3rd International Workshop on Security Issues in Concurrency (SecCo), Electronic Notes in Theoretical Computer Science, vol. 180 (1), Elsevier Science B.V., 2007, pp. 55-76. · Zbl 1277.68027
[30] M.Z. Kwiatkowska, G. Norman, D. Parker, PRISM 2.0: A tool for probabilistic model checking, in: Proceedings of the First International Conference on Quantitative Evaluation of Systems (QEST) 2004, IEEE Computer Society, 2004, pp. 322-323.
[31] V. Shmatikov, Probabilistic analysis of anonymity, in: 15th IEEE Computer Security Foundations Workshop (CSFW), 2002, pp. 119-128.
[32] M. Wright, M. Adler, B. Levine, C. Shields, An analysis of the degradation of anonymous protocols, in: ISOC Network and Distributed System Security Symposium (NDSS), 2002.
[33] K. Chatzikokolakis, C. Palamidessi, P. Panangaden, Probability of error in information-hiding protocols, in: Proceedings of the 20th IEEE Computer Security Foundations Symposium (CSF20), IEEE Computer Society, 2007, pp. 341-354.
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.