Collisions of uniformly distributed identifiers with an application to MAC address anonymization
The main contribution of this paper consists in theoretical approximations of the collision rate of n random identifiers uniformly distributed in m (> n) buckets—along with bounds on the approximation errors. A secondary contribution is a decentralized anonymization system of media access control (MAC) addresses with a low collision rate. The main contribution supports the secondary one in that it quantifies its collision rate, thereby allowing designers to minimize m while attaining specific collision rates. Recent works in crowd monitoring based on WiFi probe requests, for which collected MAC addresses should be anonymized, have inspired this research.
READ FULL TEXT