Randomized pseudo-random function tree walking algorithm for secure radio-frequency identification

Privacy and security are two main concerns in radio frequency identification (RFID) systems. We first extend the analysis of the randomized tree walking algorithm for RFID tag collision avoidance, which is secure against passive adversaries. Then, we devise a new randomized pseudo-random function (PRF) tree walking algorithm, which is secure against active eavesdroppers and allows for the efficient interrogation of many tags. Our algorithm accommodates the addition and removal of tags from the system, and dynamically adapts to security and privacy policy changes.