{'fraction_non_alphanumeric': 0.042186660297366695, 'fraction_numerical': 0.00943452558667224, 'mean_word_length': 4.033057851239669, 'pattern_counts': {'":': 0, '<': 6, '<?xml version=': 0, '>': 6, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 9, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Key Pre-Distributions From Graph-Based Block Designs

With the development of wireless communication technologies which considerably contributed to the development of wireless sensor networks (WSN), we have witnessed an ever-increasing WSN based applications which induced a host of research activities in both academia and industry. Since most of the target WSN applications are very sensitive, security issue is one of the major challenges in the deployment of WSN. One of the important building blocks in securing WSN is key management. Traditional key management solutions developed for other networks are not suitable for WSN since WSN networks are resource (e.g. memory, computation, energy) limited. Key pre-distribution algorithms have recently evolved as efficient alternatives of key management in these networks. In the key pre-distribution systems, secure communication is achieved between a pair of nodes either by the existence of a key allowing for direct communication or by a chain of keys forming a key-path between the pair. In this paper, we propose methods which bring prior knowledge of network characteristics and application constraints into the design of key pre-distribution schemes, in order to provide better security and connectivity while requiring less resources. Our methods are based on casting the prior information as a graph. Motivated by this idea, we also propose a class of quasi-symmetric designs referred here to as g-designs. These produce key pre-distribution schemes that significantly improve upon the existing constructions based on unital designs. We give some examples, and point out open problems for future research.

Security is an essential question for many sensor network applications, especially for military applications. Providing security to small sensor nodes is challenging because of the resources limitations of sensor nodes in terms of storage, computations, communications, and energy. One of the important building blocks for the development of security solutions in WSN is key management. The key management scheme design is more complicated due to the characteristics of the WSN such as: (1) The vulnerability of nodes to physical attack, where the deployment in a hostile area makes the attacker capable to simply compromise any node and to reveal its security materials (e.g. keys, functions, ...); (2) The nature of wireless communication, where the radio links are insecure and an attacker can eavesdrop on the radio transmissions, inject bits in the channel, and replay previously overheard packets; (3) The density and the large size of the network which make the control of all nodes very hard.
For security or privacy reasons, it is often critical to build encrypted communications between two sensor nodes using a common secret key. Key pre-distribution scheme (KPS) is a classical way to set up secret keys among sensor nodes before the deployment phase. Compared with online key exchange protocols, key pre-distribution is more attractive for networks consisting of large number of nodes with limited communication/computation resources [3].
Over the last decade, a host of research on key predistribution issue for WSN have been conducted and many solutions have been proposed in literature. Existing KPS fall into two categories: probabilistic and deterministic schemes. In probabilistic schemes, a direct connection between each two nodes is established with certain probability, i.e. probability that these two nodes share a common key. In deterministic schemes, however, each pair of nodes are known to be directly connected or not.
Eschenauer and Gligor [3] proposed a random key predistribution (RKP) scheme. Later on, there have been some improvements on RKP, e.g. improvements on its resilience by increasing the "intersection threshold" (the least number of common keys for two nodes to establish a direct connection) [4], or improvements on its resilience as well as higher probability of sharing keys by using deployment knowledge [5]- [9]. Schemes called "multiple key spaces" are proposed that combine different KPS to achieve better performance [10]- [12].
A simple deterministic scheme assigns a distinct key to each link, and b − 1 pairwise keys to each node, where b is the number of nodes. Choi et al. [13] proposed an improved method where each node only needs to store (b + 1)/2 keys. However, these methods may not be easily scalable. Camtepe et al. [14], [15] proposed a novel method that uses block designs for key pre-distribution. They proposed a deterministic key pre-distribution scheme that maps a symmetric balanced incomplete block design (SBIBD) or generalized quadrangles (GQ) to key pre-distribution.
There are some other works that use design theory to construct effective KPS. Lee et al. [16] introduced the common intersection designs to KPS. Chakrabarti et al. [17] used transversal designs and merging block techniques. Ruj et al. [18] proposed a KPS that is based on partially balanced incomplete block designs (PBIBD). They also used triple system to design a probabilistic KPS [19]. Later on, Bose et al. [20] proposed an improved construction that combines several PBIBDs. Bechkit et al. [21] proposed the unital-based key pre-distribution scheme (UKP), a deterministic scheme that improves the scalability of a network. More detailed surveys could be found in [22]- [24].

A. Motivations for Graph-Based KPS
Usually, the main goal of KPS is to seek a design solution that provides more connectivity coverage while requiring less memory (or using as few keys as possible). Existing designs are often evaluated under criteria such as network connectivity, average path length, network resiliency, storage overhead, and network scalability.
Our contributions are motivated by the following observations: • Observation 1: In many applications, there are several intended deployment locations, and typically a number of sensor nodes are deployed in each of these locations. In hierarchical scenarios, each group of sensors placed in a location must pass their data to sensor nodes of higher ranks. This means that for a hierarchical sensor network, nodes in the same group need more connectivity than those across groups ( Figure 1a). This can be used to reduce the number of required keys. • Observation 2: In some scenarios, a group of sensor nodes are naturally set in a master-slave architecture. For instance, the commander of a military needs more communications with his lower rank staff. This means that one or some nodes are in charge of collecting data/sending command signals to the remaining nodes ( Figure 1b). So there are some important connections that we need to establish with higher efficiency and security. • Observation 3: Two sensor nodes can communicate with each other only in a certain distance referred to as the radio frequency (RF) range ( Figure 1c). If it is known that certain pairs never connect directly due to being outside of each other's radio frequency range, then it would be a waste of resources to assign common keys to them. • Observation 4: If it is known in advance that certain connections are more likely to be eavesdropped, the corresponding nodes should not share common keys ( Figure  1d). These observations motivate the use of prior information in designing improved KPS schemes.

B. Contribution and Organization of This Work
We propose graph-based key pre-distributions (block designs) that incorporate prior knowledge of network characteristics and constraints. This provides better security and connectivity while requiring less resources once properly used. We elaborate on two practical scenarios, and explain why the graph-based design is preferable or even required. Some previous work that used deployment knowledge to optimize KPS may look similar, but is different in concept. For example, the scope of "deployment" was usually in a geographic sense. However, the model that communication should not pass through some links of potential danger was rarely studied, up to our knowledge. A general framework that casts the prior information as graphs is the main motivation of this work.
We first briefly review the basics of block design theory in Section II. Especially, we propose g-designs, a class of quasi-symmetric designs, and initiate the study of the applications of them to KPS. We propose the concept of graph-based KPS in Section III. In Section IV, we demonstrate the improvements provided by graph-based KPS and g-designs in a specific scenario. In Section V we study another scenario. We further provide an algorithmic framework (referred to MAR) for KPS design for the second scenario in Section VI. Finally, we make our conclusions in Section VII.

A. Block Design Theory
Block design theory deals with the properties, existence, and construction of systems of finite sets whose intersections have specified numerical properties. A block design (BD) is a set system (V, B). Each element in V is called a point (or treatment), and each element in B is called a block.

Definition 1. A Balanced Incomplete Block Design (BIBD)
with parameters λ, k, r, v, and b is a block design in which v points are arranged in b blocks, such that each block contains k points, each point appears in r blocks, and each pair of points appear in exactly λ blocks. It is denoted by (λ, k, r, v, b)-BIBD. It may also be denoted by (λ, k, v)-BIBD, as r and b are given by [25] Definition 2. A BIBD is a g-design if any two blocks intersect in either zero or a fixed number of points g > 0.
A quasi-symmetric design is a BIBD with two possible intersection numbers for any pair of blocks. A g-design clearly belongs to the class of quasi-symmetric designs when one intersection number equals to zero. But the term g-design is defined here for convenience. Some properties and constructions of g-designs have been studied in [26]- [30].
Clearly, any (λ, k, r, v, b)-BIBD with λ = 1 (also referred to as a Steiner system) is a g-design with g = 1.
Definition 3. Let G be a graph. Let V (G) and E(G) be respectively the set of nodes and edges of G. G is regular with degree d if every node of G has incidence degree d. A clique in G is a subset of its vertices such that every two vertices in the subset are connected by an edge; in other words, it is a subgraph of G and is complete.

Definition 4.
A strongly regular graph (SRG) with parameter set (b, d, t, u) is defined as a regular graph of size b and degree d, such that every two adjacent nodes have t common neighbors, and every two non-adjacent nodes have u common neighbors. The SRG is denoted by srg(b, d, t, u).

B. Some Properties of g-Designs
The following results are helpful for the future analysis. Theorem 1. If there exists a (λ, k, v)−BIBD which is also a g-design with g = 2, then there exists a regular graph G of size b such that its edge set E(G) is a disjoint union of v(v − 1)/2 subsets, where each subset forms a clique of size λ. Also, b satisfies the equation Proof. The proof is given in Appendix A, as it uses a definition to be introduced in Section III.
Theorem 1 provides a necessary condition for the g = 2 case. The following result shows the equivalence between gdesigns with g = 1 and a class of graphs.
Theorem 2. The existence of a (λ = 1, k, v)-BIBD is equivalent to the existence of a regular graph G of size b such that its edge set E(G) is a disjoint union of v subsets each of which forms a clique of size r, where N is the set of natural numbers.
Proof. The proof is given in Appendix B, as it uses a technique to be introduced in Section VI.

III. GRAPH-BASED KPS AND EVALUATION METRICS
Block designs are intimately related to key pre-distribution schemes. In a KPS system, each sensor node is assigned a set of keys, called "key ring". Let a key correspond to a point, and a key ring correspond to a block. For example, A unital design-based KPS gives m 2 (m 2 − m + 1) key rings from a key pool of m 3 + 1 keys, such that each key ring contains m + 1 keys.
In sensor network applications, if two key rings share at least one common key, the corresponding two nodes can be directly connected to each other. The direct connections form a graph, whose nodes correspond to the sensor nodes, and edges correspond to direct connections. This graph is referred to as the "design graph". In mathematical terms: Definition 5. A design graph for a specific block design is a graph G D whose nodes V (G D ) correspond to the blocks. Two nodes are connected in G D if and only if the corresponding two blocks share at least one point.
The prior structural information of a network (discussed) may also be modeled as a graph: Definition 6. A target graph for a specific WSN is a triplet of graphs G T = (G c T , G u T , G r T ) that satisfies 1) each node of G c T , G u T , or G r T corresponds to a node in the WSN, 2) two nodes are connected in G c T if and only if the corresponding nodes in the WSN must directly communicate, 3) two nodes are connected in G u T if and only if the corresponding nodes in the WSN are required not to directly communicate, and 4) for any pair of nodes not covered by the above two cases, they are not connected in G r T if and only if the corresponding nodes in the WSN may communicate via a path but not necessarily communicate directly.
We note that design graphs and target graphs are undirected and unweighted. Also in the classical case, G c T , G u T are null graphs (denoted by ∅) and G r T is a complete graph, i.e. G T = (∅, ∅, G complete ) where G complete denotes the complete graph.
For a given WSN, assume that we are given a target graph G T that reflects the available prior information. A natural question is how to incorporate G T into the classical evaluation metrics, in order to address practical concerns (e.g. Observations 1-4).
First, we briefly review the classical performance metrics in terms of a design graph G D .
• Direct connectivity coverage is the fraction of direct links to all possible links in the network, i.e. the probability that a given pair of nodes can directly connect. • Average path length is the expectation of the length of the shortest path between two nodes drawn uniformly from the network. It can be calculated as the average length of the shortest paths between pairs of nodes in G D . It is defined to be infinite (∞) if there exist two nodes that cannot establish a connection path. • Network resiliency N R x measures the fraction of uncompromised external links when x sensor nodes are captured. It can be calculated as the fraction of edges that do not contain keys employed in the compromised nodes. • Storage overhead measures the memory required to store the keys in each node, often calculated as the size of each block. • Network scalability is the total number of keys needed, for a given number of nodes. Consider a target graph G T . Some of the above criteria need to be modified accordingly.
• Direct connectivity coverage (DCC) and average path length (APL) If two nodes do not communicate (or are not connected in G c T ∪ G r T ), whether they share keys should not be considered into the evaluation of a KPS (Observation 1 and Observation 3). We therefore restrict the calculations of the two metrics to the edge set E(G D )∩E(G c T ∪G r T ), e.g. only consider the edges in G D that also appear in Direct important connectivity coverage can be calculated as the direct connectivity coverage restricted to G c T , i.e.
representing the cardinality of a set. This metric is meaningful only when G c T is not empty. • Network resiliency (NR) Observation 4 provides a scenario where certain nodes are required not to communicate. This is represented by the edges of G u T . Reflected in the metric of network resiliency, if two compromised nodes are connected in both G D and G u T , the common keys they share are regarded as captured. Thus, N R x can be calculated as the fraction of of edges that do not contain keys that are employed by edges in E(G D ) ∩ E(G u T ) or the x compromised nodes. It reduces to the classical case when G u T is a null graph. Definition 7. A KPS is graph-based, if it is designed based on the target graph. Its performance is evaluated based on the metrics above.
Since it is not easy to provide a universal design that is suitable for any situation, we focus on the following two different cases of graph-based KPS. Scenario 1. Consider the case when G T = (∅, ∅, G r T ), i.e. every two nodes may or may not communicate. Notice that in this scenario, we need the modified definition of "direct connectivity coverage" and "average path length".

Scenario 2. Consider the case when
T is a complete graph, and two nodes either must communicate or are required not to communicate. Notice that in this scenario, we need the modified definition of "network resiliency", and the metric "direct important connectivity coverage".
IV. THE G T = (∅, ∅, G r T ) SCENARIO In this scenario, G r T contains the information about pairs of nodes that do not need direct connections. If G r T is nontrivial, i.e. G r T is not a complete graph, we may improve the performance by employing the extra information provided by G r T . For comparison, we first consider the trivial case in which G r T is a complete graph.
(1) When G r T is a complete graph, Bechkit et al. [21] propose a highly scalable KPS using unital design. This was shown to outperform other KPS in many aspects. Here, we examine a more general case. We use a (λ, k, r, v, b)-BIBD with λ = 1 for KPS design, and evaluate the KPS parameters as follows (in terms of v and k).
• Direct connectivity coverage / Direct important connectivity coverage: .
• Average path length: If two nodes are not connected, there are u > 1 nodes connecting both of them, so the minimum path length between these two nodes is equal to two. The average path length is thus • Network resiliency: For approximate analysis, we assume that the captured nodes are uniformly distributed among all the nodes. Since each key occurs in r blocks among the total number of b blocks, the probability that a key is not compromised when x nodes are captured is . Further, the probability that a given link is compromised is • Storage overhead: It is the size of each block, i.e. SO = k. • Network scalability: It is the total number of keys, i.e. N S = v.
(2) When G r T is not a complete graph, in order to exploit the graph information, let us consider a network in which there are s groups and each of the group contains b 0 sensor nodes. For each group, there are τ 0 (0 ≤ τ 0 ≤ b 0 /s) "central nodes" (or nodes of higher rank) who are responsible for collecting information from all the other nodes in the same group. Besides this, between any two groups only the central nodes could establish connections; in other words, a "noncentral node" can only communicate with the nodes within the same group. In terms of a target graph, G r T is isomorphic to the following matrix [J mn ] sb0×sb0 (two graphs are isomorphic if the vertices are the same up to a relabeling): J mn = 0, otherwise.
Here, x denotes the largest integer that is no more than the real number x. Equations (8) and (9) represent the possible connections among all the central nodes and among the nodes in each group, respectively. Our goal is to design a KPS such that any (central or non-central) node could transfer its information to any other node in the network, while satisfying the required performance metrics. A possible graph-based KPS design is to assign keys, e.g. via BIBD with λ = 1, for each of the g groups, together with the group of all central nodes. We now evaluate the network performance of this graph-based design, and compare it with the classical way.
Let v 0 and (s+1)v 0 be respectively the size of the key pool for each group of the graph-based KPS and for the classical KPS. Let b = sb 0 , v = (s + 1)v 0 . Then we compute: • Direct connectivity coverage / Direct important connectivity coverage: 2 ), 1 and from Equation (5) we further obtain 1 O(·) notation: f = O(g) means there exists a positive constant c such that c −1 g < f < cg.
For approximate analysis, we assume that the edges of unital design are uniformly distributed in E(G r T ) and E (G r T ) (the complement of E(G r T )). This implies that For graph-based KPS, the direct connectivity coverage within one group is O(v 0 b −1 0 ), and within the central 0 ) using the same reasoning. So the overall DCC is at least which is as good as Equation (11). • Average path length: The given target graph requires that any path across two groups consists of two types of connections: normal node with central node, and central node to central node. So we consider them separately. For classical KPS, within a group or among central nodes, the average path length is less or equal to For graph-based KPS, connections within any group form a SRG, so the average path length is • Network resiliency: We assume that the captured nodes are uniformly distributed among all the nodes. For classical KPS, each key occurs in r blocks (from the total number of b blocks), and thus the probability that a key is not compromised when x nodes are captured is where we have applied ). This is also the probability that a given link is not compromised. For graph-based KPS, each key occurs in r 0 = O(b 1 2 0 ) blocks (from the total number of b blocks), and thus the probability that a key is not compromised when x nodes are captured is b−r0 x . Further, the probability that a given link within any group is not compromised is The resiliency for the central nodes ≥ N R Gx , because sτ 0 ≤ b 0 . As a result, the resiliency in Equation (16) is greater than that in (15). • Storage overhead: For classical KPS, storage overhead is given by For graph-based KPS, this is equal to ) for a normal node, and 2k 0 for a central node, so in average: In summary, under the same network scalability, the direct connectivity coverage and average path length of graph-based KPS are no worse than those of the classical ones, while the network resiliency and storage overhead are comparatively improved. Thus, the overall performance is improved.
V. THE G T = (G c T , G u T , ∅) SCENARIO In this scenario, we want to have a KPS whose design graph is exactly G c T . We first consider the case where G c T is (by coincidence) the design graph of certain g-design with g = 2 and parameters (λ, k, r, v, b). We start with such simple and "ideal" case for two main reasons: first, it provides a benchmark for a more general-purposed approach to be introduced in the next section; second, designs for more complex target graphs may be derived based upon the ideal ones.
We immediately obtain a satisfying KPS by the natural mapping between blocks of the g-design and key rings. We refer to it as the "natural" method.
The storage overhead is k. The scalability is v. As for the network resiliency, if one node (block) is captured, there will be λ 2 k 2 connections compromised. To observe this, we first notice that any pair of points in the block appear in λ blocks, and there are k 2 such pairs, so λ 2 k 2 connections are compromised. Moreover, any other connection is secure, since the corresponding two blocks share at least one key that is not captured.
T be the graph shown in Figure 2(a). As we can see, the nodes of G c T could be grouped into seven disconnected pairs with all other edges connected in the graph. For clarity, the complement of G c T is given in Figure 2(b). Assume we would like to construct a KPS whose design graph is G c T .
Generate e different keys K = {k 1 , · · · , ke}. Assign K to E(G 0 ), s.t. each edge is assigned a unique key. Define B = {B 1 , · · · , B b }, where Bn = {kt | kt is assigned to an edge which is incident to node n}. Repeat (Clique reduction procedure) l = l + 1; Find a clique C l in G l−1 whose size is no larger than c 0 ; Denote K G l−1 as the set of keys assigned to E(C l ); Update the blocks: ; Until no clique of size greater than 2 can be found. Output: Next we evaluate the performance of this construction by computing resiliency, storage overhead, and scalability measures.
We consider the simple case when one node is captured, say V 1 = {a 1 a 2 a 3 a 4 }. In this case, there are 18 connections compromised. To observe this, we first notice that any two points of V 1 appear in exactly 3 blocks; thus, there are 3 2 4 2 = 18 compromised connections in total. Besides this, if both points of the intersection of two blocks do not belong to V 1 , the two blocks are able to communicate in a secure way.
The storage overhead is the size of each block, i.e. k = 4. The network scalability is the total number of points, i.e. v = 8. Now the question is: for any given target graph G T = (G c T , G u T , ∅), does there exist a KPS whose design graph G D is exactly G c T ? In fact, we have a positive answer that is guaranteed by the following algorithm.

VI. MATCHING AND REDUCING ALGORITHM (MAR)
A schematic diagram of the Matching and Reducing Algorithm (MAR) is depicted in Table I. In the initialization step, a unique key is assigned to each edge, i.e. two nodes of that edge contain the key. Thus, the key ring of each node has been determined. However, we are motived to reduce the size of the key pool and key rings. Notice that for any clique C in G c T , it will not change the design graph if the distinct keys assigned to E(C) are replaced by only one key; in other words, if all the nodes of C share a common key, they still directly connect with one another, and edges outside C are not affected. Therefore, MAR looks for cliques in the current target graph, and reduces the number of keys within each clique to one, and then updates the target graph by removing the clique. The size of the clique, however, is upper-bounded by a constant integer c 0 to ensure a reasonable network resiliency. Consider, for example, if G c T is a complete graph, one key is enough for full connectivity; however, the the whole network is compromised as long as any one node is captured. Fig. 3: An illustrating example where MAR with c 0 = 3 is applied to a simple graph An illustrating example is given in Figure 3. We elaborate on the other aspects of this algorithm: 1) We did not give the details of how to detect cliques, or the optimality criteria for clique selection. Indeed, MAR encompasses many more algorithms. For example, one may propose a specific algorithm that deviates from MAR, in order to minimize the total number of keys (min |V |), etc. 2) It is interesting that MAR is applied as a technical tool to the proof of Theorem 2 (in Appendix B).
3) The upper bound of the clique size in MAR is designed to ensure network resiliency N R x . But is there any theoretical lower bound of N R x if the clique size is bounded by c 0 ? The following theorem gives a positive answer.

A. Network Resiliency for MAR
Theorem 3. For a given graph G c T , assume that the degree of any node is no larger than d, the network resiliency N R x of the KPS determined by the Matching and Reducing Algorithm satisfies where d c0−1 denotes the smallest integer that is no less than d c0−1 .
Proof. Let us consider an arbitrary node x. Each key that is assigned to x is associated with one clique in G c T , due to the clique reduction procedure of the MAR algorithm (an edge can be regarded as a clique of size 2). Assume that x is associated with M cliques, and that clique m is of size λ m , m = 1, · · · , M . Let y m = λ m − 1. It is clear that M m=1 y m ≤ d, 1 ≤ y m ≤ c 0 −1. (c 0 is given in the algorithm) (22) Moreover, the number of compromised links when node x is captured is: We now evaluate the maximum for F under constraint (22). Let f (y) = y+1 2 . Given positive numbers a, b, s in such a way that s − a > 0, s − b > 0, it is easy to observe that f (a)+f (s−a) < f (b)+f (s−b) if and only if |a− s 2 | < |b− s 2 |. Given two positive variables y 1 and y 2 satisfying y 1 + y 2 ≤ c 0 − 1, we have We conclude that F (y 1 , y 2 , · · · , y m ) < F (y 1 + y 2 , · · · , y m ).
(24) By continuous application of Inequalities (23) and (24), F is maximized when Thus, If x nodes are captured, the worst case is that they do not share keys and xF 0 connections are compromised, which implies the result in (21).

B. Example
In this section, we revisit the special case discussed in Section V, i.e. G c T in G T = (G c T , G u T , ∅) is the design graph of a g-design with g = 2 and parameters (λ, k, r, v, b). Now we apply the Matching and Reducing Algorithm and choose the parameter c 0 to be λ, so that the network resiliency is not worse than the "natural" method. Here are the reasons: • Due to Theorem 1, the edge set of G c T is a disjoint union of v 2 subsets, each of which forms a clique of size λ. Further, when MAR with c 0 = λ is applied, it is clear that the minimal number of keys is achieved when the C l in each step is one of the v 2 cliques.
• Therefore, there are v 2 keys in total, and the number of keys required by each node is where the last equality is due to Equation (2). • If one node is captured, there will be k 2 λ 2 connections compromised, which is the same as the "natural" method. • Finally, if c 0 is chosen to be larger, the network resiliency obviously decreases. Returning to Example 1, the parameter c 0 is chosen to be 3. There are v 2 = 28 keys in total, and each node requires k 2 = 6 keys. The keys/key rings can be realized as: Here, each key is uniquely denoted by a two-digit integer. For example, 12 represents a key, and 13 represents another key. Clearly, if one node is captured, 6 · c0 2 = 18 connections are compromised, which is the same as the "natural" approach.
Moreover, if c 0 is chosen to be 2, the network resiliency is improved. This is because every connection is secured by a unique key, and if one node is captured, only d = 12 < 18 connections are compromised. However, the storage overhead increases and network scalability decreases.
If c 0 is chosen to be 4, the network resiliency decreases. To observe this, consider the following case: Label the the 14 nodes to be n 1 , · · · , n 14 , and let two nodes n i , n j be disconnected if and only if |i − j| = 7 ( Figure 2). If we apply MAR with c 0 = 4, then it can be assumed that the following four cliques of size 4 appear in the "clique reduction procedure" (by possible relabeling): {n 1 , n 2 , n 3 , n 4 }, {n 1 , n 5 , n 6 , n 7 }, {n 1 , n 9 , n 10 , n 11 }, {n 1 , n 12 , n 13 , n 14 }.
This means that if node n 1 is captured, the four keys, along with the 4 · 4 2 = 24 > 18 connections among the above four cliques, are compromised.
In summary, the Matching and Reducing Algorithm provides a general solution for KPS design given an arbitrary target graph. Nevertheless, the previous example reveals that for specific target graphs (G c T ), there is a potential advantage of using g-designs (g > 1) based KPS in terms of storage overhead and scalability. We believe that g-design is a promising design tool for KPS and leave that for future work here.

VII. CONCLUSION
We proposed the concept of graph-based KPS and relevant evaluation metrics, motivated by several practical observations. We introduced the g-designs, studied some of their connections with graph theory, and applied them to KPS constructions. Two specific target graphs are considered. Especially, we introduced an algorithm framework called the Matching and Reducing Algorithm. Examples are provided to demonstrate the performance of the proposed scheme. APPENDIX A PROOF OF THEOREM 1 Consider a g-design (V, B) with g = 2 and design graph G. Equation (1) implies that G has b = λv(v−1) k(k−1) nodes. Because two connected blocks share exactly g = 2 keys, all edges in G are induced by a pair of keys in V . Besides this, any pair of keys induces a clique of size λ in G. Two cliques do not share an edge, otherwise there exists two blocks that share at least three keys. Finally, every block intersect with other k(k−1) 2 (λ − 1) blocks, because each block contains k(k−1) 2 pairs and each pair belongs to λ−1 other blocks. This implies that G is regular.

APPENDIX B PROOF OF THEOREM 2
Sufficiency: Assume that a (λ = 1, k, v)-BIBD exists. Let G be its design graph. Any point in V induces r nodes that are connected to one another, forming a clique of size r. Besides this, any two cliques induced by two different points do not share an edge, because otherwise these two points appear in two different blocks contradicting λ = 1. Finally, every block intersects with other (r − 1)k blocks, because each block contains k points and each point belongs to r − 1 other blocks. This implies that G is regular.
Necessity: Let Applying MAR to the given graph G for v iterations, we obtain (V, B) together with an empty graph G l . Due to MAR, |V | = v, each key appears in r blocks, and each block in B contains keys. Next we prove that any pair of keys appear in exactly one block. To this end, we let b ij be the number of blocks which keys i and j both belong to, and count the value of B = 1≤i,j≤v b ij in two different ways: on one hand, because each block contains k points and there are b blocks, B can be calculated as On the other hand, any pair of keys appear in no more than one block, because G is decomposed into v cliques any two of which share no edges. Moreover, B is no more than the total number of pairs v(v − 1)/2. Therefore, any pair must exactly appear in one block.