Reducing RFID reader load with the meet-in-the-middle strategy

When tag privacy is required in radio frequency identification (ID) system, a reader needs to identify, and optionally authenticate, a multitude of tags without revealing their IDs. One approach for identification with lightweight tags is that each tag performs pseudo-random function with his unique embedded key. In this case, a reader (or a back-end server) needs to perform a brute-force search for each tag-reader interaction, whose cost gets larger when the number of tags increases. In this paper, we suggest a simple and efficient identification technique that reduces readers computation to O(√N log N) without increasing communication cost. Our technique is based on the well-known "meet-in-the- middle" strategy used in the past to attack symmetric ciphers.