Who counterfeited my ViagraTM? (Probabilistic item removal detection via RFID tag cooperation)

We leverage RFID tag cooperation to enforce tampering detection. That is, we provide a set of probabilistic protocols that detect the absence of a tag from a system composed of a set of tags and a reader. Our proposals are able to detect which tag and for how long it has been taken away from the system. The grain of the detection can be tuned with respect to the resources available on the tags. Another merit of our solutions is to provide a proof-of-concept that a small level of cooperation among tags can further extend the range of applications RFID can support, possibly opening new veins of research. The proposed protocols fit the resource constraints of the several classes of RFID available on the market. In particular, the memory requirement ranges from few memory slots to a number of memory slots that is proportional to the number of rounds the presence of a tag is going to be checked. Computation is just one hash per round. This fully fledged set of protocols is thought to trade off the detection grain with the resources on the tag: the finer the item removal detection grain, the more resources a protocol requires. A thorough analysis for the removal detection probability is provided. Finally, extensive simulations support the analytical results, showing the viability of the proposed solutions.