Anonymity and k-Choice Identities

                    Jacek Cichon and Miroslaw Kutylowski

We consider pervasive systems and identifiers for the objects in 
these systems. Using unique identifiers there has two disadvantages: 
increasing the size of the ID's and, what is crucial, severe privacy 
threats. 

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. 
This yields an~opportunity to re-use the IDs and in this way 
anonimize the objects. The problem is that we cannot predict 
which objects will be included in which system while for many 
application scenarios we  cannot change an already assigned ID.  
Random predistribution of ID's is a technique that is simple 
to implement, but has drawbacks due to the birthday paradox.

We propose that each object holds  k  different ID's (where k is a small 
parameter like k=2,3,...). While entering a local environment, 
the object selects one of its ID's not used so far in this local
environment. We analyze mathematically probability of conflict 
in this scenario, and show that the size of IDs may be significantly 
reduced. Apart from implementation advantages it contributes 
to privacy protection. Namely, since globally a large number 
of objects holds the same ID, privacy threats are reduced.

Keywords: anonymity set, identifier, two-choice paradigm, birthday paradox