In this paper, we propose a set of extremely lightweight (optionally mutual) authentication protocols between a tag and a database (sharing a secret value) which protect the identity of the tag. However, if, for some practical reasons, the identity of the tag needs to be revealed to the reader, an additional optional last step can be added at the end of our protocols to satisfy this requirement. Our proposals are inspired by the protocol of Chien et al. but they are more efficient, since they operate in $O(1)$ at database side, whilst covering security flaws and enforcing privacy protection. We examine the adequacy of our solutions regarding the chosen security requirements and their strengths against some well-known and more exotic attacks.