skip to main content
10.1145/1179601.1179604acmconferencesArticle/Chapter ViewAbstractPublication PagesccsConference Proceedingsconference-collections
Article

On the effectiveness of k;-anonymity against traffic analysis and surveillance

Published: 30 October 2006 Publication History

Abstract

The goal of most research on anonymity, including all currently used systems for anonymity, is to achieve anonymity through unlinkability: an adversary should not be able to determine the correspondence between the input and output messages of the system. An alternative anonymity goal is unobservability: an adversary should not be able to determine who sends and who receives messages. We study the effect of k-anonymity, a weak form of unobservability, on two types of attacks against systems that provide only unlinkability.

References

[1]
A. Beimel and S. Dolev. Buses for anonymous message delivery. Journal of Cryptology, 16(1):25--39, 2003.]]
[2]
O. Berthold and H. Langos. Dummy traffic against long term intersection attacks. In R. Dingledine and P. Syverson, editors, Proceedings of Privacy Enhancing Technologies workshop (PET 2002). Springer-Verlag, LNCS 2482, April 2002.]]
[3]
O. Berthold, A. Pfitzmann, and R. Standtke. The disadvantages of free MIX routes and how to overcome them. In H. Federrath, editor, Proceedings of Designing Privacy Enhancing Technologies: Workshop on Design Issues in Anonymity and Unobservability, pages 30--45. Springer-Verlag, LNCS 2009, July 2000.]]
[4]
D. Chaum. The dining cryptographers problem: Unconditional sender and recipient untraceability. Journal of Cryptology, 1:65--75, 1988.]]
[5]
W. Dai. Pipenet 1.1. Usenet post, August 1996.]]
[6]
G. Danezis. Statistical disclosure attacks: Traffic confirmation in open environments. In Gritzalis, Vimercati, Samarati, and Katsikas, editors, Proceedings of Security and Privacy in the Age of Uncertainty, (SEC2003), pages 421--426, Athens, May 2003. IFIP TC11, Kluwer.]]
[7]
G. Danezis and B. Wittneben. The economics of mass surveillance and the questionable value of anonymous communications. In Proceedings of the 5th Workshop on The Economics of Information Security (WEIS 2006), June 2006.]]
[8]
S. Dolev and R. Ostrobsky. Xor-trees for efficient anonymous multicast and reception. ACM Trans. Inf. Syst. Secur., 3(2):63--84, 2000.]]
[9]
O. Goldreich. Foundations of Cryptography: Basic Tools. Cambridge University Press, New York, NY, USA, 2000.]]
[10]
P. Golle and A. Juels. Dining cryptographers revisited. In Proceedings of Eurocrypt 2004, May 2004.]]
[11]
D. Kesdogan, D. Agrawal, and S. Penz. Limits of anonymity in open environments. In F. Petitcolas, editor, Proceedings of Information Hiding Workshop (IH 2002). Springer-Verlag, LNCS 2578, October 2002.]]
[12]
N. Mathewson and R. Dingledine. Practical traffic analysis: Extending and resisting statistical disclosure. In Proceedings of Privacy Enhancing Technologies (PET 2004), volume 3424 of LNCS, May 2004.]]
[13]
A. Pfitzmann and M. Waidner. Networks without user observability -- design options. In Proceedings of EUROCRYPT 1985. Springer-Verlag, LNCS 219, 1985.]]
[14]
J.-F. Raymond. Traffic Analysis: Protocols, Attacks, Design Issues, and Open Problems. In H. Federrath, editor, Proceedings of Designing Privacy Enhancing Technologies: Workshop on Design Issues in Anonymity and Unobservability, pages 10--29. Springer-Verlag, LNCS 2009, July 2000.]]
[15]
R. Sherwood, B. Bhattacharjee, and A. Srinivasan. P5: A protocol for scalable anonymous communication. In Proceedings of the 2002 IEEE Symposium on Security and Privacy, May 2002.]]
[16]
L. Sweeney. k-anonymity: a model for protecting privacy. Int. J. Uncertain. Fuzziness Knowl.-Based Syst., 10(5):557--570, 2002.]]
[17]
L. von Ahn, A. Bortz, and N. J. Hopper. k-anonymous message transmission. In V. Atluri and P. Liu, editors, Proceedings of the 10th ACM Conference on Computer and Communications Security (CCS 2003), pages 122--130. ACM Press, October 2003.]]
[18]
M. Waidner and B. Pfitzmann. The dining cryptographers in the disco: unconditional sender and recipient untraceability with computationally secure servicability. In Proceedings of EUROCRYPT 1989. Springer-Verlag, LNCS 434, 1990.]]
[19]
S. Wasserman, K. Faust, D. Iacobucci, and M. Granovetter. Social Network Analysis: Methods and Applications. Cambridge University Press, 1995.]]
[20]
D. J. Watts and S. H. Strogatz. Collective dynamics of 'small-world' networks. Nature, 393:440--442, June 1998.]]

Cited By

View all
  • (2019)A Survey on Measuring Anonymity in Anonymous Communication SystemsIEEE Access10.1109/ACCESS.2019.29193227(70584-70609)Online publication date: 2019
  • (2018)A traffic analysis attack to compute social network measuresMultimedia Tools and Applications10.1007/s11042-018-6217-978:21(29731-29745)Online publication date: 14-Jun-2018
  • (2013)Hang with your buddies to resist intersection attacksProceedings of the 2013 ACM SIGSAC conference on Computer & communications security10.1145/2508859.2516740(1153-1166)Online publication date: 4-Nov-2013

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
WPES '06: Proceedings of the 5th ACM workshop on Privacy in electronic society
October 2006
128 pages
ISBN:1595935568
DOI:10.1145/1179601
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 30 October 2006

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. k;-anonymity
  2. mass surveillance
  3. statistical disclosure

Qualifiers

  • Article

Conference

CCS06
Sponsor:

Acceptance Rates

Overall Acceptance Rate 106 of 355 submissions, 30%

Upcoming Conference

CCS '25

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)5
  • Downloads (Last 6 weeks)0
Reflects downloads up to 27 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2019)A Survey on Measuring Anonymity in Anonymous Communication SystemsIEEE Access10.1109/ACCESS.2019.29193227(70584-70609)Online publication date: 2019
  • (2018)A traffic analysis attack to compute social network measuresMultimedia Tools and Applications10.1007/s11042-018-6217-978:21(29731-29745)Online publication date: 14-Jun-2018
  • (2013)Hang with your buddies to resist intersection attacksProceedings of the 2013 ACM SIGSAC conference on Computer & communications security10.1145/2508859.2516740(1153-1166)Online publication date: 4-Nov-2013

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media