International Association
for Cryptologic Research

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.