# Public Key-Based Authentication and En-Route Filtering Scheme in Wireless Sensor Networks
## 4 The Proposed Scheme
### Deployment and Initialization  
A cluster of sensor nodes and a group of forwarding nodes are prepared for each event area to be monitored. The BS distributes a unique cluster ID for each cluster and generates a secret polynomial \(f_{Si}(x)=a_{0}+a_{1}x+a_{2}x^{2}+\ldots+a_{t-1}x^{t-1}\) for each cluster, where \(a_{0}\),..., \(a_{t-1}\) are random numbers picked in the finite field F\(p\) (\(p\) is an odd prime number) and \(S_{i}\) is the cluster private key which can be picked as \(S_{i}=a_{0}\). Therefore, the corresponding cluster public key should be \(Q_{i}=S_{i}P\), where \(P\) is the base point of order \(q\) in the group of points of the elliptic curve E(F\(p\)). Subsequent to that, the BS calculates the secret share of \(S_{i}\) (denoted as \(x_{j}=f_{si}(ID_{j})\)) for each node \(v_{IDj}\) in the cluster, then calculates \(x_{j}P\) which will be used for verifying the partial signature of \(v_{IDj}\). Prior to network deployment, each cluster node \(v_{IDj}\) has to be preloaded with its unique node ID (\(ID_{j}\)), cluster ID, cluster public key \(Q_{i}\), its secret share \(x_{j}\)\(x_{k}P\) of each other node \(v_{IDk}\) in the same cluster, the elliptic curve domain parameters, and the system parameters (\(t\) and \(T_{Tv}\)). The forwarding nodes will be preloaded with its unique node ID, cluster ID, \(Q_{i}\), the elliptic curve domain parameters, and the system parameters.  
Note: (1) Each cluster node stores \(x_{k}P\) of each other node \(v_{IDk}\) in the same cluster so it can verify the partial signature of \(v_{IDk}\). (2) Having each cluster node store \(x_{k}P\) rather than \(x_{k}\) is to prevent the adversary from deriving \(x_{k}\) from \(x_{k}P\). (3) Each cluster node holds a unique share of the cluster private key \(S_{i}\), and any \(t\) cluster nodes can jointly reconstruct \(S_{i}\) by using a Lagrange interpolation \(S_{i}=\sum\limits_{j=1}^{t}l_{j}x_{j}\), where \(l_{j}=\prod_{k=1,k\
eq j}^{t}\frac{ID_{j}}{ID_{k}-ID_{j}}\) is the Lagrange coefficient. However, it is impossible to reconstruct \(S_{i}\) with fewer than \(t\) cluster nodes.  
Following network deployment, each node calculates its _level_ (its distance to the BS) as follows: the BS broadcasts a CL message including its level \(Lev\_BS\) (\(Lev\_BS=0\)), asking each node to calculate its level. Once a node \(v_{i}\) without an assigned level hears this message, it assigns its level \(Lev\_i\) to be the level in the CL message plus one. Then, \(v_{i}\) broadcasts the CL message with its own level. The CL message floods down until all nodes have been assigned a level. Subsequent to that, each node broadcasts its basic information [node ID, cluster ID, level, location] which will be stored by all of its neighbors. Then, each node transmits its location to the BS. Additionally, each node establishes an empty isolation list and a trusted neighbor list in which the trust values of all its neighbors are initialized to 1. Assume that the above procedure is safe during which no node is compromised. To further improve the security of the keys, the cluster public key and the share of cluster private key on each node can be updated periodically. One can refer to the literature [26; 27] for the key management and distribution methods.