Abstract: In this study an Elliptic Curves Cryptography (ECC)-based tree-structure radio frequency identification (RFID) grouping-proof protocol is proposed to overcome low efficiency and vulnerability to various security threats of existing RFID grouping-proof protocols. Security performance is improved because of the design of the key structure, authentication approaches and procedures for the ECC-based tree-structure RFID grouping-proof protocol. During protocol interaction, grouping-proof efficiency is improved by introducing the tag-reader mutual authentication mechanism to reduce interaction with unauthentic RFID readers and tag computing workload and to complete proof information acquisition with less computation. There are a detailed description and a security analysis of the protocol in this study. As analysis results show, the protocol meets security and privacy requirements. Compared with existing grouping-proof protocols, the proposed protocol is of high efficiency and availability as it brings enhanced security and performance with less computational complexity.