We provide several concrete implementations of a generic method given by Vaudenay to construct secure privacy-preserving RFID authentication and identification systems. More precisely, we give the first instantiation of the Vaudenay’s result by using the IND-CCA secure DHAES cryptosystem. Next we argue that weaker cryptosystems can also be used by recalling the WIPR RFID system and giving a new protocol based on the El Gamal encryption scheme. After that, we introduce a new generic construction based on the use of any IND-CPA secure public key cryptosystem together with a MAC scheme and describe a possibility using the Hash El Gamal cryptosystem. We finally compare all these schemes, both in terms of implementation and security, proving that, nowadays the DHAES and our Hash El Gamal based solutions appear as the most promising schemes.