# Two-Level-Composite-Hashing Facilitating Highly Efficient Anonymous IoT and D2D Authentication
## 2 Related Work
Even though this approach protects against attackers from getting the real identities, it should frequently update the pseudonyms and the related public keys/CLPKs; otherwise, by correlating the repeatedly used pseudonyms in the transmissions, it could be used to link the transmissions from the same device or even derive sensitive information. Unfortunately, renewing pseudonym-bound certificates/CLPKs with their trusted authority (TA)/key generating center (KGC) is very costly. This weakness causes the application of the approach in a serious dilemma. Therefore, we would like to design a novel pseudonym renewing mechanism that is automatic and highly efficient. As anonymity/unlinkability is one important focus of this work, we would further elaborate more details of the existing approaches of anonymity protection as follows. 1. Updating-and-synchronizing pseudonym. The challenges of adopting pseudonyms to achieve anonymity include (a) how do we efficiently maintain the pool of pseudonyms, and (b) how do we synchronize the pseudonyms to avoid possible desynchronization-based DoS attacks. Preloading lots of pseudonyms are suggested in some publications; however, it is not suitable for those resource-limited devices. Other systems update and synchronize the pseudonym during each authentication session. Updating-and-synchronizing pseudonyms per session does not require large storage space, but it should tackle the threats of possible desynchronization attacks or it incurs very costly overhead to renew the corresponding certificates or CLPKs. 2. Group signature [27] and ring signature [28]. A group signature facilitates one member to sign a signature on behalf of its group without disclosing its identity. A ring signature enables the signer to generate signatures embedded with all members' identities. These two mechanisms can hide the signer's identity under the umbrella of a group of members, even to the authenticators; however, they all demand heavy computations, and have poor scalability and poor dynamic membership management. 3. Probabilistic encryption. Applying an IND-CCA2-secure encryption [29] on the identities could conceal the identities. The limitation of this approach is its heavy computations, and it does not fit resource-limited devices. 4. Double Hashing: [PERSON] et al. [30] used two hashing functions to protect untraceability: the first-level hashing is to update the seed, and another hash function is applied on the seed value to have a random pseudonym. Unfortunately, the scheme needs to perform exhaustive search, and replay attacks are not tackled. 5. Error correction codes (ECC) with secret parameters: Encoding the identities using a code word with some random errors can securely deliver the message to the entities who own the secret generator matrix. The schemes like [31; 32; 33; 34] adopted this approach. However, the schemes either suffer from some security attacks [31] or demand costly computations that low-end devices cannot afford [32]. The schemes [33; 34] have solved the previous weaknesses, but their scalability is limited. 6. Encryption of identities using an ephemeral Diffie-Hellman (D-H) key: In this approach, two parties try to establish an ephemeral Diffie-Hellman (D-H) key, and then encrypt the identities, using the key. The authentication between the level-1 devices and the server in [12] adopts this approach. This approach is promising as long as the device has the capacities to hold all the CLPKs or PKCs of the potential receivers. In [35], [PERSON] proposed a 1-Level composite hashing (ILCH); based on 1 LCH, [PERSON] proposed an anonymous D2S protocol, and an anonymous server-assist device-to-server-to-device (D2S2D) protocol; however, the ordinary hash function is used as the message authentication code in the scheme, which might result in forgery attacks. This paper corrects the weakness, and greatly extends the previous work [35] in several respects.