Quantifying maximal loss of anonymity in protocols

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Quantifying maximal loss of anonymity in protocols

Full text

Pdf (793 KB)

Source

ASIAN ACM Symposium on Information, Computer and Communications Security archive
Proceedings of the 4th International Symposium on Information, Computer, and Communications Security table of contents

Sydney, Australia

SESSION: Anonymity and privacy table of contents

Pages 206-217

Year of Publication: 2009

ISBN:978-1-60558-394-5

Authors

Han Chen	Queen Mary University of London
Pasquale Malacaria	Queen Mary University of London

Sponsor

SIGSAC: ACM Special Interest Group on Security, Audit, and Control

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 10, Downloads (12 Months): 73, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1533057.1533087 What is a DOI?

ABSTRACT

There is a natural intuitive match between anonymity and information theory. In particular, the maximal anonymity loss in anonymity protocols can be matched to the information theoretical notion of channel capacity.

However, there is also a significant mismatch between the theories and reality: current theories can only characterize channel capacity based upon certain assumptions of symmetry, which are rarely satisfied in the real world.

This paper aims to resolve this mismatch by appealing to powerful mathematical techniques. A generic methodology using Lagrange multiplier method is proposed to characterize channel capacity in anonymity protocols.

This Lagrangian approach is proved to be able to generalize previous work on the channel capacity of protocols. Further, we present analyses on three well known protocols, namely Dining Cryptographers, Crowds and Onion Routing to demonstrate the application of our methodology.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Mohit Bhargava , Catuscia Palamidessi, Probabilistic anonymity, CONCUR 2005 - Concurrency Theory, Springer-Verlag, London, 2005 [doi>10.1007/11539452_16]
	2	Michele Boreale: Quantifying Information Leakage in Process Calculi. ICALP (2) 2006: 119--131
	3	D. Chaum, The dining cryptographers problem: unconditional sender and recipient untraceability, Journal of Cryptology, v.1 n.1, p.65-75, 1988
	4	K. Chatzikokolakis, C. Palamidessi, P. Panangaden. Anonymity Protocols as Noisy Channels, in: Postproceedings of the Symp. on Trustworthy Global Computing, Lecture Notes in Computer Science, Springer, 2006.
	5	Han Chen , Pasquale Malacaria, Quantitative analysis of leakage for multi-threaded programs, Proceedings of the 2007 workshop on Programming languages and analysis for security, June 14-14, 2007, San Diego, California, USA [doi>10.1145/1255329.1255335]
	6	Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
	7	David Clark , Sebastian Hunt , Pasquale Malacaria, A static analysis for quantifying information flow in a simple imperative language, Journal of Computer Security, v.15 n.3, p.321-371, August 2007
	8	David Clark, Sebastian Hunt, Pasquale Malacaria: Quantitative Analysis of the leakage of confidential data. Electronic Notes in Theoretical Computer Science 59, 2002
	9	Dorothy Elizabeth Robling Denning, Cryptography and data security, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1982
	10	George Danezis, Claudia Diaz and Carmela Troncoso. Two-Sided Statistical Disclosure Attack. In Proc. PET 2007, LNCS 4476, pp. 30--44, 2007.
	11	Dorothy E. Denning, A lattice model of secure information flow, Communications of the ACM, v.19 n.5, p.236-243, May 1976 [doi>10.1145/360051.360056]
	12	C. Díaz, S. Seys, J Claessens and B. Preneel: Towards measuring anonymity. Proceedings of Privacy Enhancing Technologies Workshop (PET 2002), Springer-Verlag, LNCS 2482.
	13	Matthew Edman, Fikret Sivrikaya, Bulent Yener. A Combinatorial Approach to Measuring Anonymity. In Proc. Intelligence and Security Informatics, 2007 IEEE, 2007, pages 356--363.
	14	Joan Feigenbaum , Aaron Johnson , Paul Syverson, Probabilistic analysis of onion routing in a black-box model, Proceedings of the 2007 ACM workshop on Privacy in electronic society, October 29-29, 2007, Alexandria, Virginia, USA [doi>10.1145/1314333.1314335]
	15	Matthias Franz, Bernd Meyer and Andreas Pashalidis, Attacking Unlinkability: The Importance of Context. In Proc. PET 2007, LNCS 4776, pp. 1--16, 2007.
	16	James W Gray III: Toward a methematical foundataion for information flow security. Proc. 1991 IEEE Symposium on Security and Privacy. Oakland, California, May 1991.
	17	Yong Guan, Xinwen Fu, Riccardo Bettati, and Wei Zhao: A quantitative analysis of anonymous communications. IEEE Transactions on Reliability, Page 103--115, Volume 53(1), March 2004.
	18	S. Kullback: Information Theory and Statistics. Dover Publications. 1997.
	19	John Mclean: Security models and information flow. Proc. 1990 IEEE Symposium on Security and Privacy. Oakland, California, May 1990.
	20	Jonathan Millen: Covert channel capacity. Proc. 1987 IEEE Symposium on Research in Security and Privacy.
	21	Pasquale Malacaria , Han Chen, Lagrange multipliers and maximum information leakage in different observational models, Proceedings of the third ACM SIGPLAN workshop on Programming languages and analysis for security, June 07-13, 2008, Tucson, AZ, USA [doi>10.1145/1375696.1375713]
	22	Pasquale Malacaria, Assessing security threats of looping constructs, Proceedings of the 34th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages, January 17-19, 2007, Nice, France
	23	Andreas Pashalidis and Bernd Meyer Linking Anonymous Transactions: The Consistent View Attack. In Proc. PET 2006, LNCS 4258, pp. 384--392, 2006.
	24	Paul F. Syverson , David M. Goldschlag , Michael G. Reed, Anonymous Connections and Onion Routing, Proceedings of the 1997 IEEE Symposium on Security and Privacy, p.44, May 04-07, 1997
	25	Michael K. Reiter , Aviel D. Rubin, Crowds: anonymity for Web transactions, ACM Transactions on Information and System Security (TISSEC), v.1 n.1, p.66-92, Nov. 1998 [doi>10.1145/290163.290168]
	26	Claude E. Shannon , Warren Weaver, A Mathematical Theory of Communication, University of Illinois Press, Champaign, IL, 1963
	27	A. Serjantov, G. Danezis. Towards an Information Theoretic Metric for Anonymity. Proceedings of Privacy Enhancing Technologies Workshop (PET 2002), Springer-Verlag, LNCS 2482.
	28	M. Wright, M. Adler, B. Levine, and C. Shields. An analysis of the degradation of anonymous protocols. In ISOC Network and Distributed System Security Symposium (NDSS), 2002.
	29	Vitaly Shmatikov. Probabilistic model checking of an anonymity system. Journal of Computer Security, vol 12, 2004.
	30	Vitaly Shmatikov , Ming-Hsiu Wang, Measuring relationship anonymity in mix networks, Proceedings of the 5th ACM workshop on Privacy in electronic society, October 30-30, 2006, Alexandria, Virginia, USA [doi>10.1145/1179601.1179611]