Radio frequency identification (RFID) is a fast growing technology for automatically identification in various industries. However, RFID system arises many security and privacy problems. Due to resource constraints in RFID tags, ultralightweight authentication schemes are an effective way to avoid these problems. In this paper, we present an ultralightweight authentication scheme which integrates cyclic redundancy check and syndrome decoding mechanism to enhance the security and privacy functionality without increasing any computation cost. In the proposed scheme, the server needs to store a generator matrix and corresponding parity-check matrix of a linear code for tag matching and authentication. Also, tags need to store only a codeword of the linear code as a unique identification number and a secret key. Our security analysis shows that the scheme provides higher security to prevent existing possible attacks. Performance evaluation illustrates that the scheme uses very less resources on tags in terms of computational operations and memory storage. © 2017, Springer Science+Business Media New York.