The content of an Radio Frequency IDentification (RFID) tag should be protected from unauthorized access and only trusted readers should be able to modify the data on the tag. Providing security for RFID systems is a challenging task mainly due to the hardware limitations and economical constraints of RFID systems. In this work, we focus on the problem of authenticating readers to RFID tags or Backward Link Authentication. Most authentication schemes for RFID systems function on a password-based protocol or a symmetric-key algorithm, which often lacks strong security or has the key-management problem. In this work, we propose an adaptation of an asymmetric cryptosystem, i.e. McEliece cryptosystem, to design an authentication scheme suitable for RFID systems. We show that the proposed authentication scheme has a small overhead and can be efficiently implemented in low-cost RFID tags. The same authentication system with slight modifications can be reused to provide communication confidentiality. Our modifications of McEliece cryptosystem in the proposed authentication scheme is provably secure. © 2011 IEEE.