A lightweight mutual authentication protocol is proposed for RFID systems in which both the tags and the reader can be authenticated to each other. The proposed protocol is based on the McEliece cryptosystem without requiring Radio Frequency IDentification (RFID) tags to store the large matrices needed in the McEliece cryptosystem. Complex computational operations in the McEliece cryptosystem are removed from the RFID tags, as they only perform simple binary operations on short vectors. The size of the memory needed in the RFID tag is trivial and suitable for low-cost tags. Readers perform most of the encryption and decryption involved in the authentication protocol using McEliece functions.