[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

Anonymity and k-Choice Identities

  • Conference paper
Information Security and Cryptology (Inscrypt 2007)

Part of the book series: Lecture Notes in Computer Science ((LNSC,volume 4990))

Included in the following conference series:

Abstract

We consider pervasive systems and identifiers for objects in these systems. Using unique global identifiers for these objects increases the size of the ID’s and requires some global coordination. However, severe privacy threats are the key issues here.

On the other hand, for performing the goals of a pervasive system the identifiers are normally used in small local environments, and we need uniqueness limited to these environments only. This yields an opportunity to re-use the ID’s and in this way anonymize the objects. The problem is that we cannot predict assignment of the objects to local environment or set it in advance, while on the other hand in many application scenarios we cannot change an ID already assigned to an object. Random predistribution of ID’s is a technique that partially solves this problem, but has drawbacks due to the birthday paradox.

We propose a solution in which each object holds k preinstalled ID’s (where k is a small parameter like k = 2,3,...). While entering a local environment, one of its ID’s not used so far in this local environment is chosen for the object. We analyze probability of a conflict, i.e. of the event that no identity can be chosen for this object. We show that the size of ID’s may be significantly reduced compared to random predistribution without increasing conflict probability. Apart from implementation advantages it contributes to privacy protection: since globally a large number of objects holds the same ID, privacy threats are reduced.

The paper is partially supported by EU within the 6th Framework Programme under contract 001907 (DELIS).

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Azar, Y., Broder, A., Karlin, A., Upfal, E.: Balanced Allocations. SIAM J. Comput. 29(1), 180–200 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  2. Azar, Y., Broder, A., Karlin, A.: Online Load Balancing. In: 33rd Annual Symposium on Foundations of Computer Science, pp. 218–225. IEEE Computer Society, Los Alamitos (1992)

    Chapter  Google Scholar 

  3. Berenbrink, P., Czumaj, A., Steger, A., Vöcking, B.: Balanced Allocations: The Heavily Loaded Case. SIAM J. Computing 35(6), 1350–1385 (2006)

    Article  MATH  Google Scholar 

  4. Bloom, D.: A Birthday Problem. American Mathematical Monthly 80, 1141–1142 (1973)

    Article  MathSciNet  Google Scholar 

  5. Cichoń, J., Klonowski, M., Kutyłowski, M.: Privacy Protection for Dynamic Systems Based on RFID Tags. In: 4th IEEE International Workshop on Pervasive Computing and Communication Security, Proceedings of PERCOM 2007 Workshops, pp. 235–240. IEEE Computer Society, Los Alamitos (2007)

    Google Scholar 

  6. Flajolet, P., Sedgewick, R.: Analytic Combinatorics, http://algo.inria.fr/flajolet/Publications/books.html

  7. Mitzenmacher, M.: The Power of Two Choices in Randomized Load Balancing. IEEE Trans. Parallel Distrib. Syst. 12(10), 1094–1104 (2001)

    Article  Google Scholar 

  8. Klamkin, M.S., Newman, D.J.: Extensions of the Birthday Surprise. J. Combin. Theory 3, 279–282 (1967)

    Article  MathSciNet  Google Scholar 

  9. Ren, K., Lou, W.: Privacy-enhanced, Attack-resilient Access Control in Pervasive Computing Environments with Optional Context Authentication Capability. Mobile Networks and Applications (MONET) 12, 79–92 (2007)

    Article  Google Scholar 

  10. Suzuki, K., Tonien, D., Kurosawa, K., Toyota, K.: Birthday Paradox for Multi-Collisions. In: Rhee, M.S., Lee, B. (eds.) ICISC 2006. LNCS, vol. 4296, pp. 29–40. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  11. Tsaban, B.: Bernoulli Numbers and the Probability of a Birthday Surprise. arXiv:math.NA/0304028 v3, November 9 (2004)

    Google Scholar 

  12. PRIME - Privacy and Identity Management for Europe, https://www.prime-project.eu/

  13. RAPID (Roadmap for Advanced research in Privacy and IDentity management), ec.europa.eu/information_society/activities/egovernment_research/doc/rapid_roadmap.doc

Download references

Author information

Authors and Affiliations

  1. Institute of Mathematics and Computer Science, Wrocław University of Technology, Poland

    Jacek Cichoń & Mirosław Kutyłowski

Authors
  1. Jacek Cichoń
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Mirosław Kutyłowski
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Dingyi Pei Moti Yung Dongdai Lin Chuankun Wu

Rights and permissions

Reprints and permissions

Copyright information

© 2008 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Cichoń, J., Kutyłowski, M. (2008). Anonymity and k-Choice Identities. In: Pei, D., Yung, M., Lin, D., Wu, C. (eds) Information Security and Cryptology. Inscrypt 2007. Lecture Notes in Computer Science, vol 4990. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-79499-8_23

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-79499-8_23

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-79498-1

  • Online ISBN: 978-3-540-79499-8

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation