We propose a method for prevention of tracking RFID tags. We consider the model in which the adversary may eavesdrop a large fraction of interactions, but not all of them.

We propose a scheme that we call Chameleon RFID. It is based on dynamic changes of identity during each interaction – flipping half of bits at random positions. The scheme is not based on any secrets shared by the systems and the tags but on their continuous interaction.

We prove privacy properties of the scheme with means of rapid mixing of Markov chains and provide concrete estimations and experimental evaluation of the rate of convergence to the uniform distribution. We also present some specific applications of the method proposed. The most important one is leaving traces of unauthorized tag activation.