Aiming at the problems that existing RFID systems cannot resist quantum attacks, low security efficiency, and privacy leakage, an RFID mutual authentication protocol based on the R-LWE cryptosystem was proposed. The protocol can resist quantum attacks, and has short key, fast encryption and decryption speed and small storage space. By using the R-LWE-based cryptosystem to encrypt the ID of the tag, the ciphertext information was stored directly in the tag, and random numbers was added to ensure the freshness and uncertainty of the encrypted information. Combined with the tag authentication protocol, not only the security problems such as counterfeit attacks, replay attacks, denial of service attack were solved, but also the mutual authentication among tags, readers, and backend databases was realized. Compared with other protocols, this protocol not only has high security and computational efficiency, but also suitable for lowcost tags with limited resources. The protocol is proved formalized by GNY logic, by which the feasibility of the protocol is demonstrated.