Abstract: In RFID systems, tags and readers wirelessly communication is carried out by sending RF signals. The contactless way brings much convenience to object identification, but it also make the system unsafe. All kinds of attacks may reveal or falsify the data stored in the tags, even make the whole system collapse. Therefore, designing a high-performance privacy-preserving authentication (PPA) has important significance for protecting RFID systems. In this paper, a kind of PPA based on public-key cryptography standards was proposed. The data was encrypted in the tag by public key, and the cipher text was deciphered in the database. In this way the mutual authentication was realized between tags and readers. After analyzing, the protocol has good performance in resisting attacks. In order to improve the execution efficiency, a sparse tree organizing tags is employed in the database, which avoids the large computation brought by linear search in the database. The time complexity is decreased to O(log_qN).