Refresh: Weak Privacy Model for RFID Systems

Privacy-Preserving Authentication (PPA) is crucial for Radio Frequency Identifcation (RFID)-enabled applications. Without appropriate formal privacy models, it is difficult for existing PPA schemes to explicitly prove their privacy. Even worse, RFID systems cannot discover potential security flaws that are vulnerable to new attacking patterns. Recently, researchers propose a formal model, termed as Strong Privacy, which strictly requires tags randomly generate their output. Adopting the Strong Privacy model, PPA schemes have to employ brute-force search in tags´ authentications, which incurs unacceptable overhead and delay to large-scale RFID systems. Instead of adopting Strong Privacy, most PPA schemes improve the authentication efficiency at the cost of the privacy degradation. Due to the lack of proper formal models, it cannot be theoretically proven that the degraded PPA schemes can achieve acceptable privacy in practical RFID systems. To address these issues, we propose a weak privacy model, Refresh, for designing PPA schemes with high efficiency as well as acceptable privacy. Based on Refresh, we show that many well-known PPA schemes do not provide satisfied privacy protection, even though they achieve relatively high authentication efficiency. We further propose a Light-weight privAcy-preServing authenTication scheme, LAST, which can guarantee the privacy based on the Refresh model and realize O(1) authentication efficiency, simultaneously.