Tree-Based RFID Yoking Proof

RFID (radio frequency identification) yoking proof protocol allows a verifier to collect the proof of the simultaneous presence of two tags in the communication range of a specified reader. This proof has found several interesting applications. However, in the existing RFID yoking schemes, the computational cost of identifying a tag in the back-end server is O(N), where N is the number of tags. This paper proposes a tree-based yoking-proof scheme, which employs the tree structure to organize the tags and treats the dynamically updated paths of tags as the secrets to identify the tags. This arrangement results in great improvement of only O(1) computational cost to identifying the tag.