In order to solve the various privacy and security problems in RFID system, a new low-cost RFID mutual authentication protocol based on ID updating mechanics is proposed. In the proposed scheme, the backend server keeps both the current ID and potential next ID for each tag, thus to solve the possible problem of de-synchronization attack in the most ID updating-based schemes, In the security analysis section, comparing several protocols in property required and attacker resistances, the comparison results show that the proposed protocol provides strong authentication and strong integrity of the transmissions and can withstand most the possible attacks that break the security of the previous schemes, In the performance evaluation section, the analysis results also indicate that, in terms of computational cost and storage requirement, the proposed scheme is safer, more efficient, more suitable for low-cost tag and more feasible in practice.