Date Added: Apr 2009
In previous RFID protocols, a hash-chain is used to achieve good privacy. Each tag is associated with a chain of Q hash values. To identify one tag out of a total of N tags, a server searches a table of size NQ. A naive search takes either ?(NQ) time or ?(NQ) memory, and therefore it does not scale well. A time-space tradeo technique can mitigate the scalability problem. However, with the time-memory tradeo, either time or space is still at least ?((NQ)2=3). This paper proposes a novel RFID protocol to solve the scalability problem. The server "Solves", instead of "Searches", for a tag ID.