Implementable privacy for RFID systems

Radio Frequency Identification (RFID) technology bridges the physical and virtual worlds by enabling computers to track the movement of objects. Within a few years, RFID tags will replace barcodes on consumer items to increase the efficiency in logistics processes. The same tags, however, can be used to monitor business processes of competitors and to track individuals by the items they carry or wear. This work seeks to diminish this loss of privacy by adding affordable privacy protection to RFID systems.;Technical privacy measures should be integrated in RFID tags in order to thwart rogue scanning and preserve the privacy of individuals and corporations. To be available for the upcoming deployment of item-level tags, protection measures must not substantially increase the costs of RFID systems. Previously proposed solutions, however, would unacceptably increase the costs of RFID tags, because the solutions use building blocks which were not optimized for privacy applications. Privacy, therefore, has been considered too expensive to be included in low-cost tags. This dissertation instead argues that privacy can be achieved at very low cost within the tight constraints of the smallest RFID tags and the largest installations.;Designing more economical protection systems requires a better understanding of what properties are crucial for privacy. By modeling the incentives of attackers and measuring the extent to which different protection measures rescind these incentives, protection systems can be found that prevent different attacks. Sufficient protection is achieved if the cost of rogue scanning exceeds its expected return for all likely attackers. Perfect protection is neither possible nor necessary to achieve strong privacy.;Protection can be realized through the combination of purposefully designed cryptographic primitives and optimized private identification protocols. These protocols achieve privacy only probabilistically, but---when parameterized well---disclose very little information. Adding noise to tag responses is one example for a protocol-level measure that provides a tradeoff between privacy and cost. The noise makes most tags indistinguishable to rogue readers while only modestly increasing the workload for the backend system.;Privacy protocols rely on cryptographic functions, but all available functions are too expensive for RFID tags. New functions should not provide expensive properties that are not necessary for privacy, but be an order of magnitude cheaper. Adapting small noise-based hash functions proposed for authentication is one alternative to achieving some of the properties of cryptographic functions without incurring their costs. Another alternative is designing new cryptographic primitives to share resources with functions already present on RFID tags. Such functions can be found through automated tests that measure the cryptographic strength of a large number of possible designs.;To achieve maximal privacy within a given cost budget, all design choices need to be considered concurrently, as similar tradeoffs often exist in different building blocks. This dissertation provides the building blocks needed to achieve strong privacy at low cost as well as a design method for building private systems from these building blocks. Towards this end, contributions are made in modeling the value of information, measuring privacy, optimizing privacy protocols, and designing cryptographic primitives.