International Journal of Computer Network and Information Security(IJCNIS)

ISSN: 2074-9090 (Print), ISSN: 2074-9104 (Online)

Published By: MECS Press

IJCNIS Vol.1, No.1, Oct. 2009

Tree-Based Matched RFID Yoking Making It More Practical and Efficient

Full Text (PDF, 194KB), PP.1-7

Views:147   Downloads:14


Hung-Yu Chien

Index Terms

Security, RFID, grouping proof, tree


A Radio Frequency Identification (RFID) yoking proof allows an off-line verifier to make sure whether two tags are simultaneously present. Due to off-line property, a reader cannot differentiate valid from invalid proof records when it probes tags, and would generate lots of useless data. This paper proposes a tree-based matched RFID yoking scheme which enhances the cost of identification from O(log N) to O(1), where N is the number of tags, and allows the reader to collect only those matched tags such that it significantly reduces useless data for the verifier to validate off-line.

Cite This Paper

Hung-Yu Chien,"Tree-Based Matched RFID Yoking Making It More Practical and Efficient", IJCNIS, vol.1, no.1, pp.1-7, 2009.


[1]A. Juels, Yoking proofs for RFID Tags, Proceedings of the First International Workshop on Pervasive Computing and Communication Security, IEEE Press, 2004.

[2]M. Burmester, B. de Medeiros, and R. Motta, “Provably secure grouping-proof for RFID tags”, IACR Eprint, October 2007,

[3]A. Juels. Generalized “yoking-proofs” for a group of RFID tags. In MOBIQUITOUS 2006, 2006.

[4]P. Peris Lopez, J. Hernandez-Castro, J.M. Estevez-Tapiador, and A. Ribagorda, “Solving the Simultaneous Scanning problem Anonymously: Clumping proofs for RFID Tags”, Unpublished Manuscript, Carlos III University of Madrid, 2007.

[5]S. Piramuthu, “On existence proofs for multiple RFID tags”, In IEEE International Conference on Pervasive Services, Workshop on Security, Privacy and Trust in Pervasive and Ubiquitous Computing SecPerU 2006, Lyon, France, June 2006. IEEE Computer Society Press.

[6]J. Saito and K. Sakurai, “Grouping proof for RFID tags”, In 19th International Conference on Advanced Information Networking and Applications, AINA 2005., volume 2, pages 621–624, March 2005.

[7]Hung-Yu Chien, Shih-Bin Liu, “Tree-Based RFID Yoking Proof“, nswctc, vol. 1, pp.550-553, 2009 International Conference on Networks Security, Wireless Communications and Trusted Computing, 2009.

[8]S.A. Weis, S.E. Sarma, R. Rivest, D.W. Engels, Security and privacy aspects of low-cost radio frequency identification systems, Proceedings of the 1st Security in Pervasive Computing, LNCS, vol. 2802, 2004, pp. 201–212.

[9]D. Monlar and D. Wagner, “Privacy and Provably Security in Library RFID Issue, Practices, and Architectures,” CCS, 2004.

[10]L. Lu, J. Han, L. Hu, Y. Liu, and L. M. Ni, “Dynamic Key-Updating: Privacy-Preserving Authentication for RFID Systems,” in Proceedings of IEEE PerCom, 2007.

[11]W. Wang, Y. Li, Lei H. and L. Lu, “Storage-Awareness: RFID Private Authentication based on Sparse Tree” Third International Workshop on SecPerU 2007.

[12]H. Y. Chien, “SASI: A New Ultra-Lightweight RFID Authentication Protocol Providing Strong Authentication and Strong Integrity”, IEEE Transactions on Dependable and Secure Computing 4(4), pp. 337-340, October, 2007.

[13]Hung-Yu Chien • Tzong-Chen Wu, “Improving Varying-Pseudonym-Based RFID Authentication Protocols to Resist Denial-of-Service Attacks“, Journal of the Korea Institute of Information Security and Cryptology (ISSN : 1598-3986) v.18, n.6B, pp.259-269, 2008.

[14]Duc, D. N., Park, J., Lee, H., and Kim, K.: ‘Enhancing Security of EPCglobal Gen-2 RFID Tag against Traceability and Cloning’. The 2006 Symposium on Cryptography and Information Security, 2006.

[15]M. Ohkubo, K. Suzuki, and S. Kinoshita, “Cryptographic approach to ‘Privacy-friendly’ tag,” in RFID Privacy workshop, MIT, USA, 2003.

[16]G. Avoine, E. Dysli, and P. Oechslin, “Reducing time complexity in RFID systems,” The 12th Annual Workshop on Selected Areas in Cryptography (SAC), LNCS 3897, pp. 291-306, Springer, 2006.

[17]A. D. Henrici, and P. MÄuller, “Hash-based Enhancement of Location Privacy for Radio-Frequency Identification Devices using Varying Identifiers,” in the Proceedings of IEEE PerCom 2004, pp.149-153, 2004.

[18]H.-Y. Chien, C.-W. Huang, “Security of Ultra-Lightweight RFID Authentication Protocols and Its Improvements,” ACM Operating System Reviews 41(2), pp. 83-86, 2007.

[19]J. Yang, K. Ren and K. Kim, “Security and privacy on authentication protocol for low-cost radio,” The 2005 Symposium on Cryptography and Information Security, 2005.

[20]K. Rhee, J. Kwak, S. Kim, and D. Won, “Challenge-response based RFID authentication protocol for distributed database environment,” International Conference on Security in Pervasive Computing – SPC 2005, pp. 70–84, 2005.