## 3 Pre-deployed Keys and Cryptographic Notations  
Before deployment, each node \(N\) knows the public key \(pk(S)\) of the sink \(S\) and also its own pair of public and private keys, denoted \((pk(N),sk(N))\) respectively. Based on ECC (Elliptic Curve Cryptography), we have that \(pk(N)=sk(N)\times G\), where \(G\) is a public generator point of the elliptic curve. Using this material, each node \(N\) can compute a shared key with the sink \(S\) using a variation of the Diffie-Hellman key exchange without interaction between the nodes, denoted \(K_{DH}(N,S)\). These computations can be done by the sink and by all nodes before deployment in order to preserve their energy. * The sink knows its own secret key \(sk(S)\) and the public key \(pk(N)\) of a node \(N\). The sink computes \(K_{DH}(N,S)=sk(S)\times pk(N)\). * Node \(N\) multiplies its secret key \(sk(N)\) by the public key of the sink \(pk(S)\) to get \(K_{DH}(N,S)\). Both computations give the same shared key since:  
\[K_{DH}(N,S)=sk(N)\times pk(S)=sk(N)\times(sk(S)\times G)=(sk(N)\times G)\times sk (S)=pk(N)\times sk(S)\]  
In what follows, we use the following notations to describe exchanged messages in our protocols:  
* \(I\): a new node that initiates the protocol,
* \(N\): a neighbour of node \(I\),
* \(R\): a node multi-hop away from \(I\) called responder,
* \(S\): the sink of the network (also called base station),  
\begin{table}
\begin{tabular}{c c c c c c} \hline \hline
**Proposed Scheme** & **Standard Algorithms** & **Cryptographic Technique** & **Simulation** & **Implementation** & **Verification** \\ \hline \begin{tabular}{c} [PERSON] _et al._, 2002 [19] \\ [PERSON] _et al._, 2005 [22] \\ [PERSON] _et al._, 2009 [23] \\ [PERSON] _et al._, 2010 [21] \\ [PERSON] _et al._, 2011 [14] \\ [PERSON] _et al._, 2012 [17] \\ [PERSON] _et al._, 2012 [12] \\ [PERSON] _et al._, 2012 [15] \\ [PERSON] _et al._, 2013 [16] \\ Our schemes \\ \end{tabular}  & \begin{tabular}{c} yes \\ not specified \\ not specified \\ not specified \\ not specified \\ not specified \\ not specified \\ not specified \\ symmetric/asymmetric \\ symmetric/asymmetric \\ symmetric/asymmetric \\ symmetric/asymmetric \\ symmetric/asymmetric \\ symmetric/asymmetric \\ symmetric/asymmetric \\ symmetric/asymmetric \\ symmetric/asymmetric \\ symmetric/asymmetric \\ symmetric/asymmetric \\ symmetric/asymmetric \\ \hline \hline \end{tabular}  & \begin{tabular}{c} none \\ yes \\ symmetric \\ not specified \\ symmetric \\ not specified \\ symmetric \\ non \\ symmetric/asymmetric \\ symmetric \\ non \\ symmetric/asymmetric \\ symmetric/asymmetric \\ symmetric/asymmetric \\ symmetric/asymmetric \\ symmetric/asymmetric \\ symmetric/asymmetric \\ symmetric/asymmetric \\ symmetric/asymmetric \\ symmetric/asymmetric \\ symmetric/asymmetric \\ symmetric/asymmetric \\ \hline \hline \end{tabular}  & \begin{tabular}{c} none \\ yes \\ symmetric \\ non \\ yes \\ symmetric/asymmetric \\ non \\ symmetric/asymmetric \\ symmetric/asymmetric \\ symmetric/asymmetric \\ symmetric/asymmetric \\ symmetric/asymmetric \\ symmetric/asymmetric \\ symmetric/asymmetric \\ symmetric/asymmetric \\ symmetric/asymmetric \\ symmetric/asymmetric \\ symmetric/asymmetric \\ \hline \hline \end{tabular}  & \begin{tabular}{c} none \\ yes \\ symmetric \\ non \\ yes \\ symmetric/asymmetric \\ non \\ symmetric/asymmetric \\ symmetric/asymmetric \\ symmetric/asymmetric \\ symmetric/asymmetric \\ symmetric/asymmetric \\ symmetric/asymmetric \\ symmetric/asymmetric \\ symmetric/asymmetric \\ \hline \hline \end{tabular}  & \ \begin{tabular}{c} none \\ yes \\ symmetric \\ non \\ yes \\ symmetric/asymmetric \\ non \\ symmetric/asymmetric \\ symmetric/asymmetric \\ symmetric/asymmetric \\ \end{tabular}