hash-function family,suitable for extremely constrained missing.It indicates that the server-less RFID authentication is devices such as passive RFID tag. not ubiquitous too.The proposed protocol utilizes cloud Readers capability requirement.All operations computing in which SaaS (Software as a service)is a kind of to authenticate tags are executed by the backend sever in the user-oriented web service.The cloud-based RFID authentication is unrelated to the used device (reader),user's protocol [16].The readers are only required to relay messages between tags and the backend server,and support PRNG to location,or logging time.It is only related to the login user's defend against replay attacks.Whereas in the protocol [3],all identity (RID),therefore,is ubiquitous. operations to authenticate tags are executed by reader-selves. Deployment cost.The RFID system based on a backend The readers are required to support hash functions beside server (like in the protocol [16])has great potential in PRNG.In the proposed protocol,storing and searching upgrading hardware to serve large-scale applications. operations are executed by the cloud,meanwhile,other However,the updating deployment is inflexible that resource computing operations such as hashing,encryption,decryption, for the peak load is wasted at idle.The server-less protocol 3 etc,are executed by readers.The readers are required to is not suitable for large-scale applications because the system support symmetric encryption and decryption due to the use of performance depends on a single reader limited in updating EHT which keeps client's privacy from revealing to the cloud. hardware.The proposed cloud-based protocol views RFID However,it is not a high requirement for readers.Even mobile authentication as a pay-on-demand service.It is applicable to readers,which are generally embedded in portable digital large-scale applications without over-preparing extravagant device,have adequate capability to support symmetric resource for peak load,especially meeting the needs of algorithm like AES,let alone fixed readers with much more medium and small size enterprises. hardware resource. B.Security and Privacy Scalability,i.e.computational complexity to verify a tag Mutual authentication means that a tag authenticates a The scalability of an RFID authentication protocol is generally reader while the reader authenticates the tag.It is useful for evaluated according to the complexity that a verifier(reader or access control of tags.The server-less protocol 3 only backend server)identifies a tag.Both the protocols [3]and [16] achieves unilateral authentication.The protocol [16]as well as depend on a brute-force search through the database or the AL to find a matched TID.It makes the computational complexity the proposed protocol achieves mutual authentication which is essential for a protocol based on state-update.Attackers are to verify a tag become O(N),where N denotes the number of feasible to successfully launch desynchronization attacks by tags.It means these protocols are not well scalable in a large- pretend to be an authorized reader and sending fake state- scale application with a huge number of tags.In the proposed protocol,H(RTS)as an index is generated by a tag,then sent update messages without mutual authentication. to a reader.The reader can therefore read the matched record Resistance against desynchronization.It is fatal to the from the EHT by only one time of accurate indexing,instead of protocols based on state-update.The protocol [3]has native launching a brute-force searching through all TIDs,which is immunity against desynchronization because it is not state- generally essential in a O(N)scheme.Thus,the complexity of update based.The protocol [16]has been proved to be the proposed scheme is only O(1)which means better vulnerable to desynchronization attacks in [18.It is untenable scalability than most current RFID authentication protocols. to claim that the proposed protocol is immune against desynchronization without formal verification.However,it is Offline authentication is to authenticate tags with an offline tenable to view it as resistant to desynchronization because reader without connecting to a backend database.The protocol there are six precautionary and reparative designs as follows. [3]is specially designed for offline authentication,meanwhile. (1)A reader notifies a tag to update its state(i.e.the last SID) the protocol 16]based on a database in a backend server and after confirming the successful state-update of the EHT.(2) the proposed protocol based on the EHT in the cloud,cannot The reader notifies the cloud to update the EHT through a VPN work in offline scenarios.The developments of pervasive connection,preventing the state-update messages from being computing and mobile networking,however,make offline manipulated by attackers.(3)The use of PRNG makes it scenarios less and less. infeasible to replay a previous state-update message to the tag Pervasive (ubiquitous)authentication is to authenticate tags (4)The tag verifies the state-update message as well as the by whatever reader device wherever and whenever,provided reader's identity before actual execution of the state-update.(5) that the user logins in the RFID system with a constant Although attackers are able to keep the tag from synchronizing username.The protocol [16],like most backend-server-based by blocking all state-update messages,the tag is still able to be protocols,depends on private intranet connections to the authenticated by readers.The desynchronization only enables database.Lacking of large-scale mobility makes the backend- the attackers to trace the tag before repaired.(6)The reader server-based protocols unsuitable to the requirement of checks the status of synchronization and tries to repair it if pervasive authentication.The protocol 3]replaces the backend needed in each session.To the best of our knowledge,the database with an AL downloaded into a specific reader.So it is proposed protocol is invulnerable to all existing types of device-related.That is,a user cannot use other reader device to desynchronization attacks. identify his/her tags if the original reader storing the AL ishash-function family, suitable for extremely constrained devices such as passive RFID tag. Readers capability requirement. All operations to authenticate tags are executed by the backend sever in the protocol [16]. The readers are only required to relay messages between tags and the backend server, and support PRNG to defend against replay attacks. Whereas in the protocol [3], all operations to authenticate tags are executed by reader-selves. The readers are required to support hash functions beside PRNG. In the proposed protocol, storing and searching operations are executed by the cloud, meanwhile, other computing operations such as hashing, encryption, decryption, etc, are executed by readers. The readers are required to support symmetric encryption and decryption due to the use of EHT which keeps client's privacy from revealing to the cloud. However, it is not a high requirement for readers. Even mobile readers, which are generally embedded in portable digital device, have adequate capability to support symmetric algorithm like AES, let alone fixed readers with much more hardware resource. Scalability, i.e. computational complexity to verify a tag. The scalability of an RFID authentication protocol is generally evaluated according to the complexity that a verifier (reader or backend server) identifies a tag. Both the protocols [3] and [16] depend on a brute-force search through the database or the AL to find a matched TID. It makes the computational complexity to verify a tag become O(N), where N denotes the number of tags. It means these protocols are not well scalable in a large￾scale application with a huge number of tags. In the proposed protocol, H(R|T|S) as an index is generated by a tag , then sent to a reader. The reader can therefore read the matched record from the EHT by only one time of accurate indexing, instead of launching a brute-force searching through all TIDs, which is generally essential in a O(N) scheme. Thus, the complexity of the proposed scheme is only O(1) which means better scalability than most current RFID authentication protocols. Offline authentication is to authenticate tags with an offline reader without connecting to a backend database. The protocol [3] is specially designed for offline authentication, meanwhile, the protocol [16] based on a database in a backend server and the proposed protocol based on the EHT in the cloud, cannot work in offline scenarios. The developments of pervasive computing and mobile networking, however, make offline scenarios less and less. Pervasive (ubiquitous) authentication is to authenticate tags by whatever reader device wherever and whenever, provided that the user logins in the RFID system with a constant username. The protocol [16], like most backend-server-based protocols, depends on private intranet connections to the database. Lacking of large-scale mobility makes the backend￾server-based protocols unsuitable to the requirement of pervasive authentication. The protocol [3] replaces the backend database with an AL downloaded into a specific reader. So it is device-related. That is, a user cannot use other reader device to identify his/her tags if the original reader storing the AL is missing. It indicates that the server-less RFID authentication is not ubiquitous too. The proposed protocol utilizes cloud computing in which SaaS (Software as a service) is a kind of user-oriented web service. The cloud-based RFID authentication is unrelated to the used device (reader), user’s location, or logging time. It is only related to the login user’s identity (RID), therefore, is ubiquitous. Deployment cost. The RFID system based on a backend server (like in the protocol [16]) has great potential in upgrading hardware to serve large-scale applications. However, the updating deployment is inflexible that resource for the peak load is wasted at idle. The server-less protocol [3] is not suitable for large-scale applications because the system performance depends on a single reader limited in updating hardware. The proposed cloud-based protocol views RFID authentication as a pay-on-demand service. It is applicable to large-scale applications without over-preparing extravagant resource for peak load, especially meeting the needs of medium and small size enterprises. B. Security and Privacy Mutual authentication means that a tag authenticates a reader while the reader authenticates the tag. It is useful for access control of tags. The server-less protocol [3] only achieves unilateral authentication. The protocol [16] as well as the proposed protocol achieves mutual authentication which is essential for a protocol based on state-update. Attackers are feasible to successfully launch desynchronization attacks by pretend to be an authorized reader and sending fake state￾update messages without mutual authentication. Resistance against desynchronization. It is fatal to the protocols based on state-update. The protocol [3] has native immunity against desynchronization because it is not state￾update based. The protocol [16] has been proved to be vulnerable to desynchronization attacks in [18]. It is untenable to claim that the proposed protocol is immune against desynchronization without formal verification. However, it is tenable to view it as resistant to desynchronization because there are six precautionary and reparative designs as follows. (1) A reader notifies a tag to update its state (i.e. the last SID) after confirming the successful state-update of the EHT. (2) The reader notifies the cloud to update the EHT through a VPN connection, preventing the state-update messages from being manipulated by attackers. (3) The use of PRNG makes it infeasible to replay a previous state-update message to the tag. (4) The tag verifies the state-update message as well as the reader's identity before actual execution of the state-update. (5) Although attackers are able to keep the tag from synchronizing by blocking all state-update messages, the tag is still able to be authenticated by readers. The desynchronization only enables the attackers to trace the tag before repaired. (6) The reader checks the status of synchronization and tries to repair it if needed in each session. To the best of our knowledge, the proposed protocol is invulnerable to all existing types of desynchronization attacks