The significance of radio frequency identification (RFID) security is increasing explosively, leading to a research trend. The current most severe RFID security issues are privacy and authentication security. The renewable identity (ID) approach with a central database is the current dominating approach to achieve user privacy and authentication security. Although, the approach will cause more problems that renewable ID will increase RFID tag cost and will enable denial of service (DoS) attacks while the central database will reduce system mobility. To solve the dilemma, a new protocol with two original approaches, which are the label sharing approach to protect customer and the removable central database approach to enhance system mobility is proposed in this paper. The security properties of the new scheme are verified by using Colored Petri Net (CPN) and algebra proofs.