1 Introduction

Symmetric Key Cryptography (SKC) is useful for providing security properties in those devices that are typically resource constrained. However, one of the issues with the SKC is the key management. Typically, in a large network, the number of keys required to be stored in the entire network is also high and may not match with the available storage in the deployed network nodes. Let us consider a scenario where thousands of sensor nodes (smart meters) are used to monitor some environmental parameters in specific surrounding. Specifically, let us consider the grid based sensor networks where the objects being monitored form a square grid. A few of the examples of such networks are the networks deployed:

  1. 1.

    to monitor goods in a warehouse,

  2. 2.

    to monitor and regulate traffic on city streets,

  3. 3.

    to monitor the electricity consumption of houses through smart meters with the houses being laid in a row by row fashion.

In all such applications and the likes, the integrity and the confidentiality of the data communicated to the base station is vital in order to preserve the application semantics. Hence, it is necessary to devise and deploy an effective security protocol that ensures these security properties. However, with the nodes used in deployment being resource constrained—in terms of the available storage, computational power, bandwidth and the energy, the design of the security protocol must ensure minimal resource overhead [1]. In addition, any security protocol deployed needs an effective key management scheme that must not impose large demands on the memory required to store the keys, while offering effective resilience at the same time. As for example, when using simple pairwise key distribution, the network resilience is very high—with the compromise of one node leading to only that part of the network being affected; however such a scheme requires the total number of keys to be stored in the network to be of the order of \(O(N^{2})\), where N is the total number of nodes in the network.

The goal of our work here, is to design a Key Pre-distribution Scheme (KPS) that requires comparatively lesser number of keys and provide the same level of resilience as pairwise KPS scheme. The literature in this field of KPS considered no knowledge of deployment of nodes [2,3,4,5,6,7,8,9,10]. However, the knowledge of the placement of nodes yields an efficient KPS as keys can be shared between those nodes that are not in the communication range. This is so, because the neighbour discovery phase is not needed and this helps in reducing the overhead in key setup phase.

The scheme that takes the advantage of deployment knowledge is discussed in [11, 12]. The KPS for grid based sensor networks is discussed in [13]. Their scheme is based on the concept of costas array [14]. The resilience of the scheme is dependent on the size of costas array. As compared, the scheme that we propose here is independent of any parameter. To illustrate, let us consider a scenario in which there is a colony of houses. All these houses are laid out in a row by row fashion as shown in Fig. 1. All the 50 houses are equipped with the devices to communicate the respective electricity consumption readings. The houses are installed with smart meters that periodically take the readings and communicate the same to the aggregator nodes (in the considered example, AG\(_1\) is aggregator node for that region). The aggregation is used to obviously conserve the communication costs—instead of sending in N different readings, an aggregated value sent saves the bandwidth. There can be many aggregator nodes whose job is to take up the readings from the assigned region of the entire colony. Aggregator nodes finally transfer the reading to the Base Station (BS) or the control center where further processing of the received data takes place. The same scenario can be considered for other applications forming a square grid (monitoring goods in warehouse, monitoring the traffic or pollution level on city streets, etc.).

Fig. 1
figure 1

Considered scenario of colony

Full size image

Our proposed KPS takes the advantage of linearity in the deployment of the grid based sensor networks. A linear sensor networks is defined as the network where each node has either one or two neighbours, with exception of the terminal nodes. The terminal nodes are those with just a single neighbour. The construction proposed in [15] requires 4 keys per node, whereas our proposed KPS requires 3 keys per node to provide same level of resilience. They applied their scheme only to linear sensor networks whereas we extend that idea to grid based networks. There are several applications forming a square grid network but we consider the deployment of smart grid, as it has many advantages (discussed in Sect. 2), and is widely deployed [16,17,18]. Such grids have generated lot of interest in the research community from the point of view of securing the same [19,20,21]. To the best of our knowledge, ours is the first attempt at exploiting the linearity in designing a KPS for grid based sensor networks with the storage requirement of only 3 keys per node while ensuring the same level of resilience as the other existing schemes.

The rest of the paper is organized as follows : we give a brief overview of the smart grid in Sect. 2. In Sect. 3, we discuss a brief background about the ultralight weight KPS and costas array based KPS. These schemes takes linear and grid based deployment of nodes under consideration respectively. In Sect. 4, we discuss the proposed KPS and give the mathematical proof to prove its resilience. The comparison with the existing schemes is done in Sect. 5, whereas we conclude the paper in Sect. 6.

2 Smart Grid Architecture and Significance

The entire thought of the smart grid is to have enough Information Technology (IT) knowledge to control the framework better and make it more self-sufficient and self-healing; as discussed in [22, 23]. Smart grid provides more advantages than traditional power grid as discussed in [16, 24]. The authors of [23], discuss how to tidy the conventional power framework. However, the security aspect is not considered in their work. The energy effective framework for electricity dispersion is proposed in [25]. Smart grid is also used to exploit new innovations, for example, Plug-in Hybrid Electrical Vehicles (PHEVs) [26], different types of dispersed generations, solar energy [27], smart metering [28], lighting administration frameworks, distribution robotization, and some more.

Fig. 2
figure 2

Typical architecture of smart grid

Full size image

The typical architecture of a smart grid is as shown in Fig. 2. As we can see from the figure, smart grid carries four main components:

  1. i.

    Generation

    This component is responsible for generating the required power in a smart manner. The renewable energy generators like wind turbines can be used for the production as discussed in [27, 29].

  2. ii.

    Transmission

    This component is responsible for energy-efficient transmission network that will carry the power from the bulk generation facilities to the power distribution systems as discussed in [30].

  3. iii.

    Distribution

    This component is responsible for distributing power from substation to end users. The impact on distribution systems through smart grid is discussed in [31].

  4. iv.

    Consumers

    The classification of this component is as follows:

    • Industrial customers

    • Commercial customers

    • Residential customers

    The consumers play a major role in smart grid through saving the energy in off-peak hours, demanding the energy in emergency and valley-filling as discussed in [32].

All these four components are related to operations, markets and service providers. The other components are HAN (Home Area Network), electrical vehicles, smart appliances, home monitoring, etc. The communication between the smart meter hanging outside houses, offices, factory etc. (forms a HAN) and the substation is two way. The communication between data centre and substation is also two way. This allows the generation of the power to be in control and consumers to remain in constant touch with their electricity usage.

Although smart grid uses IT knowledge for the mentioned functionalities, it has some differences from IT infrastructure. Therefore, solutions applicable to IT infrastructure cannot fit directly to smart grid as discussed in [21]. The difference between smart grid and IT infrastructure is as shown in Table 1. As we can see from the table, the availability plays a major role in smart grid because if the service fails to remain available, then the entire region will face the blackout which is not accepted. Therefore, availability plays a major role in smart grid whereas it is not the first priority for IT. Privacy must be guaranteed for smart grid whereas it is optional for IT. In terms of architecture, technology and Quality of Service (QoS), smart grid and IT differs as described in the Table 1.

Table 1 Difference between IT and smart grid
Full size table

The data being communicated in smart grid has to be kept secret as compromise of the same can yield adverse results. There are works related with authentication and key management as discussed in [36,37,38,39,40]. However, the literature does not consider the constrains of smart meters like limited storage, memory, bandwidth etc., which motivates the idea of lightweight KPS. The lightweight key distribution scheme based on group ID and elliptic curve based cryptography based mechanisms are described in [41, 42] respectively. However, they do not consider the specific topology that smart grid forms. Therefore, we come up with a novel solution for lightweight KPS for the grid based sensor networks (e.g. smart grid).

3 Related Work

In this section, we discuss a brief background related with ultralight weight KPS and costas array. Moreover, we describe the KPS inspired from costas array and show how it fits to the grid based sensor networks. The ultralight weight scheme takes linear deployment of sensor nodes under consideration. Costas array based KPS takes grid based deployment of nodes under consideration. The proposed KPS is applicable to both.

3.1 Ultralight Weight KPS: Linear Sensor Networks

We first look at the construction proposed in [15] (Construction 1). The construction requires, each node to store 4 keys for getting the same level of resilience as pairwise KPS. The parameter k of the construction decides how many nodes needed to be captured by the adversary before making the network fallible (when no node from the left half of captured nodes can communicate securely with right half of the captured nodes, the network is said to be fallible). The network is said to be k-fallible if capturing \(k-1\) nodes does not divide the network in two halves.

Construction 1

Assign keys to the nodes of a linear network such that each node shares unique pairwise keys with each of the nodes at distance k and 1.

Example 1

If Construction 1 is applied to a linear network with nine nodes and k = 3, then the nodes share keys as illustrated in Fig. 3. Consider each circle in the figure as nodes (meters) and lines coming out of it as keys they share with other nodes. i.e. \(1, 2, 3, \ldots .\) represents nodes and line from 1 to 4 means nodes 1 and 4 are sharing symmetric key.

Fig. 3
figure 3

Construction in which all the nodes requires 4 keys to achieve k-fallibility

Full size image

The Example 1 shows that intermediate (node number 4, 5, 6) nodes require 4 keys to have a 3-fallible network whereas local pairwise setting would require 6 keys per intermediate node as can be seen from Fig. 4. If the adversary captures lesser than 3 nodes, then there remains a secure path from left half of captured nodes to right half as can be seen from Fig. 5 (the dashed lines represent captured path, after capturing node 5 and 6 there is still a secure path from node 4–7). Therefore, in order to make the network fallible adversary has to capture one more node i.e. capture k nodes (3 for the considered example). In order to achieve k-fallibility, the local pairwise setting requires \(2*k\) number of keys whereas Construction 1 requires 4 keys per node. Our proposed KPS requires only 3 keys per node to achieve k-fallibility.

Fig. 4
figure 4

Local pairwise KPS when \(r=3\)

Full size image
Fig. 5
figure 5

After capturing 2 nodes from Fig. 4

Full size image

3.2 Key Pre-distribution Through Costas Array: Grid Based Networks

The KPSs for the grid based networks are discussed in [13, 43, 44]. The KPS proposed in [13] is based on Costas Array and the solution proposed in [43, 44] is based on symmetric bi-variate polynomials. We study the solution for key pre-distribution inspired from the costas array and then device a solution for the considered scenario of the colony. The (4 × 4) costas array is as shown in Fig. 6. The definition of costas array of order n follows:

  1. i.

    Its an \(n\times n\) matrix.

  2. ii.

    Each entry in the matrix is either blank or a dot.

  3. iii.

    Each column and row contains exactly one dot.

  4. iv.

    Any two vectors (lines passing through dots with a direction) are different (difference is either a length or a direction).

Fig. 6
figure 6

Costas array of order 4

Full size image
Fig. 7
figure 7

Initialization of KPS through costas array of order 4

Full size image
Fig. 8
figure 8

KPS through costas array of order 4

Full size image

The property that makes costas array special is, the separation between any pair of dots in the matrix is not rehashed for another pair of dots. The use of costas array for key pre-distribution in grid based sensor network is given in [13]. One can start imposing costas array on a square grid of sensor nodes from any corner. Here, we consider each square shown in Figs. 7 and 8 as a sensor node (smart meter). The costas array of order 4 is used for the distribution of keys. The initialization of the KPS through costas array is as shown in Fig. 7. If we continue to apply costas array on the network of nodes, then the key predistribution is as shown in Fig. 8. We can clearly observe:

  1. i.

    Each node stores exact 4 keys.

  2. ii.

    Each key has been stored with 4 nodes.

The number of keys stored by nodes for the KPS shown in Fig. 8 is dependent on the size of costas array.

In the next section, we take the advantage of having a linearity in smart meters’ deployment and form a KPS based on that. The number of keys stored per node is 3 without depending on any parameter. The resilience of the network is same as the other existing KPSs in the literature.

4 Proposed Key Predistribution Scheme

If we look at just a single row from the considered scenario of the colony shown in Fig. 1, we can clearly see that it forms a linear sensor network. The proposed solution for key pre-distribution provides lesser storage of keys than pairwise KPS, ultralight weight KPS, and the KPS based on costas array. Moreover, the proposed KPS is applicable to both linear as well as grid based networks. The idea is inspired from the KPS we proposed in [45]. Moreover, the proposed KPS is k-resilient. i.e. the network is \(k+1\)-fallible (adversary has to capture k nodes in order to partition the network). The proposed method of key predistribution is as defined in Algorithm 1. The example of proposed KPS on network with 9 nodes and \(k=2\) is as shown in Fig. 9. As we can see from the figure, each smart meter requires at the most 3 keys whereas the ultralight weight KPS requires 4, and the KPS inspired from costas array requires the size of costas array as the number of keys. As we can see from Fig. 10, the single row of houses is considered along with aggregator node and BS and the proposed construction is applied with 11 nodes. The same when applied to the considered scenario of colony of houses forms a network as shown in Fig. 11. We assume that the BS cannot be captured. The aggregator node and the BS are considered to be resource rich as compared to the other nodes (meters) and can store more number of keys. The resilience of the proposed scheme is k (maximum number of consecutive nodes (meters) allowed to be captured) and we prove the same in Theorem 1. We assume no smart meters are compromised initially. Attacks on network of nodes or meters are possible after they are deployed. Attacker can be insider or outsider. The proposed scheme avoids both the kind of adversaries by providing resilience against consecutive node (meter) captures.

Fig. 9
figure 9

Example of proposed KPS on 9 smart meters with \(k=2\)

Full size image
Fig. 10
figure 10

Example of proposed KPS by considering a single row of grid with \(k=2\)

Full size image
Fig. 11
figure 11

Example of proposed KPS on the considered scenario of grid with \(k=2\)

Full size image
figure c

Theorem 1

The KPS of the proposed construction isk-resilient.

Proof

We prove the theorem with the help of proving the following propositions.

Setup:

The smart meters of the network are labeled from 0 to \((N-1)\), where N is the total number of meters in the network. The maximum number of consecutive meters that an adversary can capture is k.

Proposition 1

There is a meter with label\(l \in (0,k)\), so that no meter with the value\(l(mod (k+1))\)is captured.

Proof

After applying the mod operation to the labels of smart meters of the network with respect to modulus \((k+1)\), \(n/(k+1)\) congruent sets are produced with the same values ranging from \({0,1,\ldots ,k}\). The size of each set is \((k+1)\). An adversary captures k meters and they can be captured from any of the different \(n/(k+1)\) sets. As the size of every set is \(k+1\), after capturing k meters there is always a single meter left that is not captured. Because of the congruence all the congruent meters to that uncaptured meter are not captured as well.

Therefore, Proposition 1 holds.

Setup: There are 2 meters with labels \(x_1\) and \(x_2\) at distance at least \((k+2)\) from captured meter and the label of \(x_1\) is greater than the label of \(x_2\).

Proposition 2

There is always a secure path from meter\(x_1\)to\(x_2\).

Proof

The secure path from meter \(x_1\) to \(x_2\) is found using following steps:

  1. 1.

    From meter \(x_1\) within the same set, go towards meter \(x_2\) with hops of length \((k+1)\) till a meter with label equivalent to \(l(mod (k+1))\) is reached. If meter \(x_1\) itself is equivalent to \(l(mod (k+1))\), then no need to take any hop. These hops are secure as no captured meter lies within distance \((k+2)\) of \(x_1\).

  2. 2.

    Continue applying step 1 till we reach a meter that is at distance less than \((k+1)\) from \(x_2\).

  3. 3.

    Complete the path by taking hops of length 1 or \((k+1)\) until meter \(x_2\) is reached. These hops are secure as there are no captured meters lying within the distance \((k+2)\) of \(x_2\). Hence, we can say that no matter which k meters adversary captures, there always remains a secure connected path for the remaining meters.

Therefore, Proposition 2 holds.

Therefore, the resilience of the proposed construction is k. Hence, the Theorem 1 holds. \(\square\)

Let us look at an example to understand the theorem. If we capture meters 2 and 8 from the example shown in Fig. 9, then the network looks like the Fig. 12. As we can see, there is no partition as left half of the captured nodes can communicate with right half through a secure path. E.g. 0–3, 1–4, 0–1–4–7–6–5, etc. Now, in order to take the advantage of the consecutive node capture, if adversary captures meter 3, then the network looks like the Fig. 13. As we can see, there is no partition. i.e. secure paths are still there (0–1–4, 0–1–4–7–6–5, etc.). Therefore, the proposed KPS is k-resilient. i.e. even after capturing k (2 in the considered example), the network is not partitioned in two halves.

Fig. 12
figure 12

Example of proposed KPS with 2 captured nodes

Full size image
Fig. 13
figure 13

Example of proposed KPS with 2 consecutive captured nodes

Full size image

We apply the following standard algorithm for checking the connectivity (between nodes) in an underlying graph of the proposed construction as shown in Algorithm 2.

figure d

The implementation of the proposed construction for verifying the connectivity between nodes is done using python language. The pseudo-code of the same is as shown below in Algorithm 3.

figure e

The proposed construction is implemented with different values of N such as 10, 20, 50, 100, 1000, 2000, 5000 and 100,000. For all the values of N, implementation of proposed construction shows that it remains connected. The total number of keys required for the proposed construction is calculated using the total number of edges in the underlying graph of proposed construction. The comparison of the same with other existing schemes is shown in the next section.

5 Comparison of Different KPSs

The local pairwise KPS requires more number of symmetric keys as compared to the one proposed in [15]. The proposed construction requires even lesser storage in terms of symmetric keys required and can get the same fallibility value as compared to the approach considered in [15] and in local pairwise KPS. The costas array based [13] or group ID based [41] approaches for key pre-distribution in smart grid require number of keys that is dependent on size of costas array or the way groups are formed. The scheme proposed in [43] talks about a hierarchical grid based KPS. This scheme uses symmetric bi-variate polynomials for generating keys of symmetric nature. The number of keys required to be stored per node is again dependent on N for the scheme proposed in [43]. Our proposed construction by considering linearity in smart meters’ deployment requires just 3 keys to be stored in each smart meter. Comparison in terms of number of symmetric keys required is as shown in Table 2. For all the approaches, we considered ’N’ as total number of nodes (smart meters) in the network. The proposed KPS requires only 3 keys per smart meter in order to provide the same level of resilience as compared to other schemes. As shown in Table 2, the total number of keys required for the proposed scheme is lesser as compared to the other existing schemes.

Table 2 Comparison of key pre-distribution schemes
Full size table

The performance analysis on the number of symmetric keys required is shown in Table 3. This table shows the exact number of keys required for the network of N meters. The proposed scheme is scalable as the keys are pre distributed in the manner that handles the increment and decrement in total number of meters. As we can see from the Table 3 and the chart shown in Fig. 14, the proposed KPS requires the least number of keys as compared to the other existing schemes for providing same level of resilience.

Table 3 Total number of symmetric keys required for different ciphers
Full size table
Fig. 14
figure 14

Performance analysis

Full size image

6 Conclusions

Sharing just a single key in an entire network of nodes (smart meters) solves the purpose of security of data with very less storage requirement. However, adversary needs to capture just a single key to disrupt the entire service and compromise the security of the network. Sharing pair-wise keys with every meters gives a maximum resilience as adversary has to capture \(O(N-1)\) keys, where N is the total number of smart meters in the network. However, the storage requirement is \(O(N^N)\) for pair-wise key distribution. We proposed a KPS that requires constant storage i.e. only 3 keys per meter. The mathematical analysis and the associated proof shows that the proposed scheme provides the same level of resilience as pair-wise KPS with very less key storage requirement (3 keys per meter).