Privacy-preserving RFID authentication protocols based on symmetric-key cryptography technology have increasingly become popular. However, current RFID authentication protocols are inefficient due to the requirement of full search for all the RFID tags in the systems. In this paper, a new efficient method is proposed to construct highly effective privacy preserving RFID protocols. Based on pseudorandom functions with single output bit, this protocol can significantly improve the performance of tag searching process. Moreover, the protocol satisfies anonymity, authenticity, and efficiency requirements in the large-scale systems.