The limited computational and memory resources available in the Radio Frequency Identification (RFID) tags constitute the essential challenge to find a technique that satisfies high security requirements. In this paper, security and privacy requirements for an RFID authentication system are defined. Although some of the conventional cryptographic operations provide these requirements partially, they are not considered as suitable solution for RFID applications because operations cost is high especially for RFID tags. An unconventional use of homomorphic encryption is proposed to provide low-cost security and privacy in this research. HEADA is proposed as a novel authentication technique, which consists of deployment and authentication process stages. The homomorphic encryption is used solely in the generation of keys during deployment stage. These keys are used by RFID tags to generate anonymous authentication keys during the authentication process using only integer addition operations. Moreover, some of the conventional approaches have to use a brute-force search in the server side to identify a tag. Unlike these techniques, HEADA enables the server to identify a tag only by a binary search. It is shown that HEADA is the only technique to satisfy all security and privacy requirements using low-cost operations in both tag and server sides. Copyright (C) 2016 John Wiley & Sons, Ltd.