# Smart Grid Security: A PUF-Based Authentication and Key Agreement Protocol
## 5 Security Analysis of PPSG
### Formal Security Evaluation--RoR  
Throughout the remaining part of this section, we conduct a comprehensive security evaluation of PPSG within the framework of the real-or-random (RoR) model. In this model, an initial random selection is made where a bit \(b\) is uniformly chosen; when \(b=0\), it represents the random world (\(\mathit{RW}\)), and when \(b=1\), it signifies the real world (targetprotocol). The adversary's objective is to accurately distinguish the value of \(b\) in this scenario. To do this, the adversary \(\mathcal{A}\) can run the following query types [39]:  
* Execute: it models a passive adversary \(\mathcal{A}\), which eavesdrops transferred messages over public channel;
* Send: it models an active adversary on the public channel;
* Reveal (\(N_{i}\)): its output is the session key that is held by the instance \(N_{i}\);
* Test (\(N_{i}\)): it returns the session key for instance \(N_{i}\) if \(b=1\) or a random value of the same size if \(b=0\). Consider protocol \(\mathcal{P}\), in which \(\mathcal{A}\) is given access to the Execute, Send, Reveal (\(N_{i}\)) and Test (\(N_{i}\)) oracles, and outputs a guess bit \(b_{0}\). The adversary wins the semantic security game in the RoR sense if \(b_{0}=b\) and its advantage to win this game, \(Adv^{RaR}_{D,\mathcal{P}}(t,R)\), is defined as follows:  
\[Adv^{RaR}_{D,\mathcal{P}}(t,R) = \big{(}(Pr(\mathcal{A}\to b_{0}=1:b=1)-(Pr(\mathcal{A}\to b_{0}=1:b=0)) )\big{)}\]  
\(\mathcal{P}\) offers RoR semantic security if:  
\[Adv^{RaR}_{\mathcal{D},\mathcal{P}(t,R)}<\varepsilon(.)\]  
with \(\varepsilon(. )\) being some negligible function. In this section, as outlined in [39], we conduct a formal assessment of PPSG's security within the RoR model. This evaluation involves gauging the adversary's advantage in differentiating PPSG from the random world (\(RW\)). Theorem 3.1: _Let \(q_{\text{exec}}\), \(q_{\text{send}}\), \(q_{\text{Reval}}\), and \(q_{\text{test}}\), respectively, represent the number of queries to Execute, Send, Reveal, and Test oracles on PPSG/\(RW\), then:_  
\[Adv^{RaR}_{\mathcal{D},PPSG}(t,q_{\text{exec}};q_{\text{send}};q _{\text{Reval}};q_{\text{test}}) -\] \[Adv^{RaR}_{\mathcal{D},RW}(t,q_{\text{exec}};q_{\text{send}};q _{\text{Reval}};q_{\text{test}}) \leq\] \[3.q.\varepsilon_{\text{ECC}}+4.q.\varepsilon_{H}+q.\varepsilon_{ PUF}\]  
_In the given context, \(\varepsilon_{\text{ECC}}\) represents the utmost advantage an adversary can gain in solving ECDLP or EC-CDHP with each query. Additionally, \(\varepsilon_{H}\) signifies the maximum advantage in challenging the collision resistance property of \(H(. )\), while \(\varepsilon_{PUF}\) denotes the maximum advantage in distinguishing the output of \(PUF(. )\) from a random sequence. Here, \(q\) is calculated as the sum of \(q_{\text{exec}}\), \(q_{\text{send}}\), \(q_{\text{Reval}}\), and \(q_{\text{test}}\)._  
Proof: Consider the scenario where \(SM_{i}\) and \(NAN_{j}\) engage in communication to establish a session key \(SK\). Let \(\mathcal{A}\) denote an adversary aiming to challenge the semantic security of PPSG within the real-or-random (RoR) model. To establish the theorem, a game-based methodology is employed. This approach involves defining a sequence of games denoted as \(\mathcal{G}\), initiating from the random world \(RW\), and concluding in the real-world PPSG. Each game, represented as \(\mathcal{G}_{n}\), introduces an event \(Adv^{RaR-\mathcal{G}_{n}}_{\mathcal{D},\mathcal{P}}(t,R)\). This event signifies the adversary's advantage in accurately determining the hidden bit \(b\) involved in the Test queries. It should be noted the structure of the transferred messages is identical in \(RW\) and PPSG, including plain values such as timestamps; otherwise distinguishing them is trivial. Game \(\mathcal{G}_{0}\). It is corresponding to \(RW\) and \(Adv^{RaR-\mathcal{G}_{0}}_{\mathcal{D},RW}(t,R)=0\). Game \(\mathcal{G}_{1}\). In this game, any instance follows the structure of the generated and transferred messages in PPSG, e.g., \((SK,R1_{SM},\ldots)\).