Combining Rabin cryptosystem and error correction codes to facilitate anonymous authentication with un-traceability for low-end devices

Secure authentication of low cost Radio Frequency Identification (RFID) with low computing capacity is a big challenge, due to the constraint of the limited resources and the privacy concern of their mobility and traceability. Here, we not only concern authentication but also privacy (anonymity and un-traceability) to protect privacy of these mobile devices and their holders. In this paper, we delicately combine Rabin cryptosystem and error correction codes to design lightweight authentication scheme with anonymity and un-traceability. Compared to its previous counterpart [4], the proposed schemes improve the number of supported tags from O(k) to O(2^k), where k is the dimension of the codes. The scheme is attractive to low-end devices, especially those low-cost cryptographic RFIDs. We, additionally, show the security weaknesses of a recently published Rabin cryptosystem-based RFID authentication scheme.