In this paper, we introduce a randomized bit encoding scheme that can strengthen the privacy protection on RFID tags. This scheme is used together with the backward channel protection method proposed by Choi and Roh (2006), which serves to protect the unique identifier of an RFID tag from disclosure to close-range eavesdroppers. Choi and Roh's method faces the 'same-bit' problem, in which some bits of the unique identifier could be disclosed, thereby revealing critical information. Our proposed scheme alleviates the 'same-bit' problem to a negligible level. Furthermore, we propose an enhanced system model that can protect the unique tag identifier from disclosure not only against eavesdroppers, but against unauthorized interrogators as well. A metric based on entropy was defined and used to measure the amount of protection offered by the scheme. A method to construct an optimal randomized n-bit encoding scheme was also described. In addition, theoretical analysis and simulations were conducted, which show that the proposed encoding scheme provides significant improvement (achieving almost twice the entropy) over no encoding.