An efficient authentication mechanism is proposed for RFID tags, based on error-correcting codes. The proposed scheme is an asymmetric design benefiting from advantages of the public-key infrastructure. The security of our protocol is guaranteed based on the difficulty of the syndrome decoding problem. Our protocol is rearranged in a novel way to meet the practical requirements of RFID tags. Complex computational operations are removed from the RFID tags, and they only perform simple binary operations on short vectors. The proposed protocol is considered zero-knowledge, as tags can be easily authenticated by readers without sharing the tag's secret with the readers.