# PUF and Chaotic Map-Based Authentication Protocol for Underwater Acoustic Networks
## 4 Formal Security Analysis  
This section will formally analyze the security of the proposed scheme. The results demonstrated that our scheme was proven secure. The notions of the model used in this paper are defined as follows:  
Participants: In the proposed scheme, \(\mathcal{P}\), denoted as \(P\), the participants include the user \(U\), the gateway \(GW\), and the sensor node \(Sn\). In the \(i^{th}\) instance, the participants, the user, the gateway, and the sensor node are denoted as \(INS^{i}_{P}\), \(INS^{i}_{U}\), \(INS^{i}_{GW}\), and \(INS^{i}_{Sn}\), respectively. States of Oracle: Oracle in our scheme has three states: \(ACCEPT\), \(REJECT\), and \(\bot\). If an oracle receives a correct request message, the state is \(ACCEPT\), if the request message is illegal, the state is \(REJECT\). When the above conditions do not occur, the state is \(\bot\). We defined that if the oracle \(INS^{i}_{U}\) (\(INS^{i}_{Sn}\)) is \(ACCEPT\), and the session key \(SK^{i}_{U}\) (\(SK^{i}_{SN}\)) has been negotiated with \(INS^{i}_{P}\), then \(INS^{i}_{U}\) (\(INS^{i}_{Sn}\)) obtains its session identity \(SID^{i}_{U}\) (\(SID^{i}_{Sn}\)), and the corresponding participant identity \(PID^{i}_{Sn}\) (\(PID^{i}_{U}\)). Partnering: If the following conditions are satisfied, \(INS^{i}_{U}\) and \(INS^{i}_{Sn}\) are \(ACCEPT\), and the session key has been negotiated, then \(INS^{i}_{U}\) and \(INS^{i}_{Sn}\) are considered as partners. 1. The session key \(SK^{i}_{U}\) generated by \(INS^{i}_{U}\) equals \(INS^{i}_{Sn}\)'s session key, \(SK^{i}_{SN}\). 2. \(INS^{i}_{U}\) and \(INS^{i}_{Sn}\) are in the same session; that is, \(SID^{i}_{U}=SID^{i}_{Sn}\). 3. The participant identities of \(INS^{i}_{U}\) and \(INS^{i}_{Sn}\) are equal to \(INS^{i}_{Sn}\) and \(INS^{i}_{U}\), respectively. Queries: To simulate multiple attacks, queries are defined as follows: Execute (\(INS^{i}_{P}\)): Execute simulates the eavesdropping attack, and \(A\) executes this query to obtain all the transcripts. Send (\(INS^{i}_{P}\), _message_): This query simulates the sending operation executed by the adversary, \(A\). The message is sent to oracle \(INS^{i}_{P}\); if the message is correct, \(INS^{i}_{P}\) responds to \(A\) based on \(\mathcal{P}\), otherwise, the message is neglected. Reveal (\(INS^{i}_{P}\)): If the session key has been negotiated, \(INS^{i}_{Sn}\) and \(INS^{i}_{U}\) are in \(ACCEPT\), and the query Test has not been executed yet. The query Reveal will reveal the session key when it is executed. Otherwise, the output is null. Corrupt (\(INS^{i}_{U}\)): This query simulates a corruption attack. It will return the message \(\{h(. ),M_{0},M_{1}\}\) to the adversary, which is stored in the smart card. Test (\(INS^{i}_{P}\)): This query is allowed to be executed at most once. The query generates a random bit \(r\); if \(r=1\) and the session key has been generated, the session key is sent to the adversary. Otherwise, \(A\) receives a random number. Freshness: An instance \(INS^{i}_{P}\) can be identified as fresh if it satisfies the following conditions:  
1. Reveal query has not been executed. 2. Corrupt is executed at most once. 3. \(INS^{i}_{Sn}\) and \(INS^{i}_{U}\) are in \(ACCEPT\). Semantic Security: As the definition of the Test query shows, \(r\) determines if the output is the session key. Furthermore, \(A\) generates a random bit \(r_{a}\); if \(r_{a}=r\), \(A\) knows the correctness. The possibility is \(Adv^{\alpha}_{P}=|2\text{Pr}[r=r_{a}]-1|=|2\text{Pr}[suc(A)]-1|\). If \(Adv^{\alpha}_{P}\geq\eta\), \(\mathcal{P}\) is not secure, where \(\eta\) is sufficiently small. CMDLP: The chaotic map-based discrete logarithm problem (CMDLP) is distributed as: considering \(x,y\in Z^{*}_{P}\), where \(y=T_{r}(x)mod\ p\). Computing \(r\) is computationally hard. The advantage of CMDLP is \(Adv^{\zeta CMDLP}_{A}=2\text{Pr}\big{[}A(x,y)=r:r\in Z^{*}_{P},y=T_{r}(x)mod\ p \big{]}\). **Theorem 1**. : Assume \(A\) is the adversary that tries to break \(\mathcal{P}\) in PPT.