Recently, RFID system is a main technology to realize ubiquitous computing environments, but the feature of the RFID system may bring about various privacy problems. So, many kinds of protocols to resolve these problems have been researched. In this paper, we analyze the privacy problems of the previous protocols and propose more secure and effective authentication protocol to protect user’s privacy. Then we analyze the security and effectiveness of the proposed protocol comparing with the previous protocols. The proposed protocol is based on Challenge-Response using one-way hash function and random number. The proposed protocol is secure against the replay the attack, spoofing attack and so on. In addition, the proposed protocol is fitted for distributed database environment.