A survey of state-of-the-art in anonymity metrics

ABSTRACT

Anonymization enables organizations to protect their data and systems from a diverse set of attacks and preserve privacy; however, in the area of anonymized network data, few, if any, are able to precisely quantify how anonymized their information is for any particular dataset. Indeed, recent research indicates that many anonymization techniques leak some information. An ability to confidently measure this information leakage and any changes in anonymity levels plays a crucial role in facilitating the free-flow of cross-organizational network data sharing and promoting wider adoption of anonyimzation techniques. Fortunately, multiple methods of analyzing anonymity exist. Typical approaches use simple quantifications and probabilistic models; however, to the best of our knowledge, only one network data anonymization metric has been proposed. More importantly, no one-stop-shop paper exists that comprehensively surveys this area for other candidate measures; therefore, this paper explores the state-of-the-art of anonymity metrics. The objective is to provide a macro-level view of the systematic analysis of anonymity preservation, degradation, or elimination for data anonymization as well as network communciations anonymization.

REFERENCES

• 1: G. F. Coull, C. V. Wright, A. D. Keromytis, F. Monrose, and M. Reiter, "Taming the Devil: Techniques for Evaluating Anonymized Network Data," presented at Internet Society (ISOC) Symposium on Network and Distributed Systems Security (SNDSS), San Diego, CA, 2008.
• 2: C. E. Shannon, "A Mathematical Theory of Communication," Bell System Technical Journal, vol. 27, pp. 379--423, 623--656, 1948.
• 3: C. Diaz, S. Seys, J. Claessens, and B. Preneel, "Towards Measuring Anonymity," presented at Privacy Enhancing Technologies Workshop (PET), 2002.
• 4: C. Diaz, J. Claessens, S. Seys, and B. Preneel, "Information Theory and Anonymity," presented at 23rd Symposium on Information Theory in the Benelux, Louvain la Neuve, Belgium, 2002.
• 5: 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]
• 6: M. Wright, M. Adler, B. Levine, and C. Shields, "An Analysis of the Degradation of Anonymous Protocols," presented at Network and Distributed Security Symposium (NDSS), 2002.
• 7: Vitaly Shmatikov, Probabilistic Analysis of Anonymity, Proceedings of the 15th IEEE workshop on Computer Security Foundations, p.119, June 24-26, 2002
• 8: G. Shafer, A Mathematical Theory of Evidence. Princeton, NJ: Princeton University Press, 1976.
• 9: R. Yager, "Entropy and Specificity in a Mathematical Theory of Evidence," International Journal of General Systems, vol. 9, pp. 249--260, 1983.
• 10: F. Cuzzolin, "The Theory of Evidence," 2005.
• 11: H. Dijiang, "On Measuring Anonymity For Wireless Mobile Ad-hoc Networks," presented at 31st IEEE Local Computer Networks Conference, 2006.
• 12: Steve Schneider , Abraham Sidiropoulos, CSP and Anonymity, Proceedings of the 4th European Symposium on Research in Computer Security: Computer Security, p.198-218, September 25-27, 1996
• 13: Vitaly Shmatikov, Probabilistic analysis of an anonymity system, Journal of Computer Security, v.12 n.3,4, p.355-377, May 2004
• 14: Flavio D. Garcia , Ichiro Hasuo , Wolter Pieters , Peter van Rossum, Provable anonymity, Proceedings of the 2005 ACM workshop on Formal methods in security engineering, November 11-11, 2005, Fairfax, VA, USA [doi>10.1145/1103576.1103585]
• 15: P. F. Syverson , J. W. , Iii Gray, The epistemic representation of information flow security in probabilistic systems, Proceedings of the 8th IEEE workshop on Computer Security Foundations, p.152, March 13-15, 1995
• 16: Paul F. Syverson , Stuart G. Stubblebine, Group Principals and the Formalization of Anonymity, Proceedings of the Wold Congress on Formal Methods in the Development of Computing Systems-Volume I, p.814-833, September 20-24, 1999
• 17: Jan van Eijck , Simona Orzan, Epistemic Verification of Anonymity, Electronic Notes in Theoretical Computer Science (ENTCS), 168, p.159-174, February, 2007 [doi>10.1016/j.entcs.2006.08.026]
• 18: A. Pfitzmann and M. Kohntopp, "Anonymity, Unobservability, and Pseudonymity -- A Proposal for Terminology," presented at Workshop on Design Issues in Anonymity and Unobservability, Berkeley, CA, USA, 2000.
• 19: Latanya Sweeney, k-anonymity: a model for protecting privacy, International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, v.10 n.5, p.557-570, October 2002 [doi>10.1142/S0218488502001648]
• 20: Ashwin Machanavajjhala , Johannes Gehrke , Daniel Kifer , Muthuramakrishnan Venkitasubramaniam, \ell -Diversity: Privacy Beyond \kappa -Anonymity, Proceedings of the 22nd International Conference on Data Engineering, p.24, April 03-07, 2006 [doi>10.1109/ICDE.2006.1]
• 21: Michael K. Reiter , Aviel D. Rubin, Anonymous Web transactions with Crowds, Communications of the ACM, v.42 n.2, p.32-48, Feb. 1999 [doi>10.1145/293411.293778]
• 22: A. Serjantov and G. Danezis, "Towards an Information Theoretic Metric for Anonymity," presented at Privacy Enhancing Technologies Workshop (PET), 2002.
• 23: N. Li, T. Li, and S. Venkatasubramanian, "t-Closeness: Privacy Beyond k-Anonymity and l-Diversity," presented at IEEE 23rd International Conference on Data Engineering, 2007.
• 24: Xiaokui Xiao , Yufei Tao, M-invariance: towards privacy preserving re-publication of dynamic datasets, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247556]
• 25: M. Edman, F. Sivrikaya, and B. Yener, "A Combinatorial Approach to Measuring Anonymity," presented at IEEE Intelligence and Security Informatics, 2007.
• 26: W. Xiaoxin and E. Bertino, "Achieving K-anonymity in Mobile Ad Hoc Networks," presented at 1st IEEE ICNP Workshop on Secure Network Protocols (NPSec'05). , 2005.

INDEX TERMS

Primary Classification:
  A. General Literature
  A.1 INTRODUCTORY AND SURVEY

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General
          Subjects: Security and protection (e.g., firewalls)

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Distribution functions

General Terms:
Measurement, Security

Keywords:
anonymity, communication networks, metrics, network data, privacy