Widespread deployment of RFID system arises security and privacy concerns of users. There are several proposals in the literature to avoid these concerns, but most of them provide reasonable privacy at the cost of search complexity on the server side. The search complexity increases linearly with the number of tags in the system. Some schemes use a group based approach to solve the search complexity problem. In this paper, we proposed a group based authentication protocol for RFID system which is based on some characteristics of cyclic groups. The scheme uses only bitwise XOR, circular left shift (≪) and modulo operations for the computational work. Also, the scheme does not use any pseudo-random number generator on the tag side. We use two benchmark metric based on anonymity set to measure the privacy level of the system when some tags are compromised by an adversary. We present some simulation results which show that the scheme preserves the high level of privacy and discloses very less amount of information when some tags are compromised. Furthermore, its formal and informal analysis show that our scheme preserves information privacy as well as un-traceability and also withstand various well-known attacks. © 2018, Springer Science+Business Media, LLC, part of Springer Nature.