T-MATCH: Privacy-preserving item matching for storage-only RFID tags

RFID-based tag matching allows a reader Rk to determine whether two tags Ti and Tj store
some attributes that jointly fulfill a boolean constraint. The challenge in designing a matching mechanism is tag privacy. While cheap tags are unable to perform any computation, matching has to be achieved without revealing the tags' attributes. In this paper, we present T-MATCH, a protocol for secure and privacy preserving RFID tag matching. T-MATCH involves a pair of tags Ti and Tj , a reader Rk, and a backend server S. To ensure tag privacy against Rk and S, T-MATCH employs a new technique based on secure two-party computation that prevents Rk and S from disclosing tag attributes. For tag privacy against eavesdroppers, each tag Ti in T-MATCH stores an IND-CPA encryption of its attribute.
Such an encryption allows Rk to update the state of Ti by merely re-encrypting Ti's ciphertext.
T-MATCH targets cheap tags that cannot perform any computation, but are only required to store 150 bytes.