Privacy and security are central issues in the deployment of an RFID system. It is vulnerable to several attacks, such as replay attacks, location tracking, man-in-middle attack, de-synchronization attack, etc., due to the inherent weaknesses of underlying wireless communications. In order to tackle these privacy and security concerns, this paper presents an ultralightweight authentication protocol based on group homomorphism and maximum distance separable (MDS) code. We use group homomorphism properties to make a server lookup table that reduces searching complexity and overcomes scalability issues. We develop an ultralightweight protocol using MDS code properties that employs only bit-wise operators. Formal and informal security analysis of the proposed protocol shows that our proposed protocol resists various attacks. In addition, we use automated security protocol verification tools, AVISPA and Scyther, to validate the security features of the proposed protocol. We demonstrate the correctness proof of the proposed protocol using BAN logic. To measure the level of privacy of the proposed protocol, we use two benchmark metrics to simulate the proposed protocol. The performance analysis indicates that the proposed protocol is efficient for a low-cost environment.