## 3 Renewal and Revocation Protocols
### Renewing Asymmetric Keys  
In what follows, we describe four protocols to renew asymmetric keys of the network. These protocols use the existing key infrastructure to securely replace the asymmetric keys between the sink and all nodes of the network. For this, the sink creates its own new public/private keys \((pk^{\prime}(S),sk^{\prime}(S))\) and a new pair of public/private keys \((pk^{\prime}(I),sk^{\prime}(I))\) for each node \(I\) in the network. Our four protocols (RAKnk\({}_{a}\), RAKnk\({}_{b}\), RAKdh\({}_{a}\) and RAKdh\({}_{b}\)) are based on the same idea: first, \(S\) securely sends \(pk^{\prime}(S)\) and the new pair of keys for node \(I\); then, node \(I\) replies by sending back its identity with the new shared key \(K^{\prime}_{DH}(S,I)\). We use different cryptographic mechanisms to distribute these new keys.  
In Figure 4, we present two protocols, RAKnk\({}_{a}\) and RAKnk\({}_{b}\), where the new public key of the sink \(pk^{\prime}(S)\) is broadcast to all nodes using the network key (\(NK\)). In the first protocol RAKnk\({}_{a}\), depicted in Figure 3(a), the sink only sends to each node \(I\) the new pair of keys using \(K_{DH}(S,I)\). Then, \(I\) computes the new shared key \(K^{\prime}_{DH}(S,I)=sk^{\prime}(I)\times pk^{\prime}(S)\). In order to save computation time for node \(I\), we propose a second version RAKnk\({}_{b}\) described in Figure 3(b), where the sink pre-computes \(K^{\prime}_{DH}(S,I)=sk^{\prime}(S)\times pk^{\prime}(I)\) without using the secret key of \(I\).  
\begin{table}
\begin{tabular}{c c c c c c} \hline \hline
**Protocol** & **Name** & **Figure** & **Time with \(S\) (ms)** & **Time without \(S\) (ms)** & **Gain** & **Standard Deviation (ms)** \\ \hline \multirow{2}{*}{Join Protocols [11]} & DJS & 1a & 10,112.62 & 4082.05 & 59\% & 78.09 \\ \cline{2-6}  & JJS & 1b & 10,180.81 & 10,049.45 & 1\% & 111.94 \\ \hline Revocation & KR & 2 & 155.37 & 87.58 & 44\% & 3.82 \\ \hline Renewing SymKey & RSK & 3 & 10,042.32 & 10,042.32 & 0\% & 76.49 \\ \hline \multirow{4}{*}{Renewing AsymKey} & RAKnk\({}_{a}\) & 4a & 6797.75 & 3436.24 & 49\% & 4.26 \\ \cline{2-6}  & RAKnk\({}_{b}\) & 4b & 3646.05 & 254.62 & 93\% & 3.95 \\ \cline{2-6}  & RAKdh\({}_{a}\) & 5a & 6797.75 & 3436.24 & 49\% & 4.26 \\ \cline{2-6}  & RAKdh\({}_{b}\) & 5b & 3646.05 & 254.62 & 93\% & 3.95 \\ \hline Renewing Network Key & RNK & 6 & 221.09 & 121.40 & 45\% & 3.73 \\ \hline \multirow{2}{*}{Multihop Shared Key} & MSK\({}_{a}\) & 7a & 6893.76 & 6631.91 & 4\% & 5.76 \\ \cline{2-6}  & MSK\({}_{b}\) & 7b & 3682.53 & 301.42 & 91\% & 5.25 \\ \hline \hline \end{tabular}
\end{table}
Table 2: Execution time of all protocols.  
Figure 3: RSK: renewing a symmetric or session key.  
An alternative is to use the pre-shared key \(K_{DH}(S,I)\) instead of \(NK\) in the distribution of \(pk^{\prime}(S)\), as depicted in Figure 5. In Figure 5a, we explain the protocol RAKdh\({}_{a}\) with the computation of the new key performed by node \(I\). In Figure 5b, we present the protocol RAKdh\({}_{b}\) where the sink pre-computes \(K^{\prime}_{DH}(S,I)\). These two protocols use symmetric shared keys on each hop, preventing an intruder from learning the new key of the sink by learning the network key, as is the case in the protocols of Figure 4. Nevertheless, this solution requires more load on the network, since the transmission of the public key of the sink is not a broadcast using the network key, but a unicast using a symmetric shared key between two nodes. For instance, for a line of four nodes (\(S\), \(A\), \(B\) and \(C\)), in one case, three messages are enough to broadcast \(pk^{\prime}(S)\), and in the other situation, it requires \(1+2+3=6\) messages to send \(pk^{\prime}(S)\).  
Figure 4: Two protocols for renewing asymmetric keys of a node \(I\), where \(S\) uses the network key \(NK\) to broadcast \(pk^{\prime}(S)\). (**a**) Protocol RAKnk\({}_{a}\): \(S\) and \(I\) compute \(K^{\prime}_{DH}(S,I)\); (**b**) protocol RAKnk\({}_{b}\): \(S\) computes \(K^{\prime}_{DH}(S,I)\) and sends it to \(I\).