Practical Minimalist Cryptography for RFID Privacy Marc Langheinrich and Remo Marti - Submitted for Publication Abstract The fear of unauthorized, hidden readouts has dominated the RFID privacy debate. Virtually all proposed privacy mechanisms so far require consumers to actively and explicitly protect read access to their tagged items - either by jamming rogue readers or by encrypting or pseudonymizing their tags. While this approach might work well for activists and highly concerned individuals, it is unlikely (and rather undesirable) that the average consumer should be outfitted with RFID jamming devices before stepping outside, or that anyone would bother pseudonymizing every can of soda they buy with a personal PIN code. Juels' "minimalist cryptography" offers a simple, yet effective identification and tracking protection based on simple ID rotation, but it requires that the corresponding mappings (i.e., from pseudonyms to real IDs) are electronically exchanged whenever a product changes hands (e.g., for buying a pack of chewing gums at a kiosk) - a rather impractical requirement. Our work extends Juels' concept in order to alleviate the need for passing ID mapping tables. Using carefully assembled sets of IDs based on the cryptographic principle of secret shares, we can create RFID tags that yield virtually no information to casual "hit-and-run" attackers, but only reveal their true ID after continuous and undisturbed reading from up-close - something that can hardly go unnoticed by an item's owner. This paper introduces the underlying mechanism of our extension to Juels' proposal, called "Shamir Tag", analyzes its tracking resistance and identification performance, and discusses deployment aspects.