Tree-Based RFID authentication protocols are definitively not privacy-friendly

Authentication for low-cost Radio-Frequency IDentification (RFID) is a booming research topic. The challenge is to develop secure protocols using lightweight cryptography, yet ensuring privacy. A current trend is to design such protocols upon the Learning Parity from Noise (LPN) problem. The first who introduced this solution were Hopper and Blum in 2001. Since then, many protocols have been designed, especially the protocol of Halevi, Saxena, and Halevi (HSH) that combines LPN and the tree-based key infrastructure suggested by Molnar and Wagner. In this paper, we introduce a new RFID authentication protocol that is less resource consuming than HSH, relying on the same adversary model and security level, though. Afterwards, we show that, if an adversary can tamper with some tags, the privacy claimed in HSH is defeated. In other words, either tags are tamper-resistant, then we suggest a protocol more efficient than HSH, or they are not, then we suggest a significative attack against the untraceability property of HSH