Contents

  1. 1. Introduction
  2. 2. Preliminaries
  3. 3. The Constructions
  4. 4. Resiliency
  5. 5. Concluding Remarks
  6. Declaration of Competing Interest

Utilitas Mathematica

  • Research article

Key Pre-distribution Schemes via Certain Resolvable Block Designs

Shyam Saurabh1
1Department of Mathematics, Tata College, Kolhan University, Chaibasa, India
  • Received: 09/05/2024
  • Accepted: 23/09/2024
  • Published: 30/09/2024

Abstract

Earlier optimal key pre−distribution schemes (KPSs) for distributed sensor networks (DSNs) were proposed using combinatorial designs via transversal designs, affine, and partially affine resolvable designs. Here, nearly optimal KPSs are introduced and a class of such KPSs is obtained from resolvable group divisible designs. These KPSs are nearly optimal in the sense of local connectivity. A metric for the efficiency of KPSs is given. Further, an optimal KPS has also been proposed using affine resolvable L2-type design.

Keywords: Resolvable and affine resolvable designs, Optimal configuration, Group divisible design, L2−type design, Hadamard product

1. Introduction

Distributed Sensor Networks (DSNs) are ad–hoc mobile networks that include sensor nodes with limited computation and communication capabilities. Lee and Stinson [1,2] and Saurabh and Sinha [3] obtained optimal key pre−distribution schemes (KPSs) for DSNs from transversal designs, affine and partially affine resolvable designs which are classes of optimal (v, b, r, k)−configurations. Those KPSs are optimal in the sense of local connectivity. Here nearly optimal KPSs are obtained from resolvable group divisible designs which are not affine. A metric for efficiency of KPSs is given and an optimal KPS has also been proposed using affine resolvable L2−type Latin square design. A correspondence between combinatorial designs and KPSs for DSNs may be found in [1-3].

Eschenauer and Gligor [4] proposed a randomized KPS. Their scheme consists of three phases: key pre–distribution, shared–key discovery and path–key establishment. Lee and Stinson [1] used this framework in the constructions of deterministic KPSs from certain combinatorial designs. In the key pre–distribution phase, a large pool of keys and their key identifiers are generated. Every sensor node is loaded with a fixed number of keys chosen from the key pool, along with their key identifiers. After deployment of the DSNs, any two nodes in the same neighborhood of DSNs look for common keys in order to communicate; this is the shared-key discovery phase. If any two sensor nodes have no common keys, then they try to establish a secure two–hop path for communication which is the path–key establishment phase [5].

In this paper, some combinatorial constructions are presented for deterministic optimal and nearly optimal KPSs. The present construction is useful when an optimal (v, b, r, k)−configuration is not available for the given v, b, r, k. A recent survey on the constructions of KPSs for DSNs using some combinatorial designs may be found in [3].

2. Preliminaries

2.1 Resolvable and Affine Resolvable Designs

A block design D(v, b, r, k) or (X, B) is an arrangement of the v elements of a set X into b subsets (blocks) of size k each such that each element of X occurs in exactly r blocks. For 1≤i≤v;1≤j≤b, D can be represented by a v×b incident matrix N defined by N=(nij)v×b, where nij={1 if xi∈Bj0 otherwise , for Bj∈B. Clearly each row and column sum of N are r and k respectively.

A block design D(v, b, r, k) is said to be resolvable if the b blocks, each of size k can be partitioned into r resolution classes of br blocks each such that in each resolution class every point is replicated exactly once. Clearly a necessary condition for a design D(v, b, r, k) to be resolvable is that r divides b. Alternatively, if the incidence matrix N of a block design D(v,b,r,k) may be partitioned in to sub matrices as: N=(N1|N2|⋯|Nt) where each Ni(1≤i≤t) is a v×(vk) matrix such that each row sum of Ni is one, then the design is resolvable.

Further a resolvable design is said to be affine if any two blocks belonging to different resolution classes intersect in constant number of elements. Some examples of resolvable and affine resolvable designs are given in subsections 2.2–2.4.

2.2 Group Divisible Design

Let v=mn elements be arranged in an m×n array. A group divisible (GD) design is an arrangement of the v=mn elements in b blocks each of size k such that:

  1. Every element occurs at most once in a block;

  2. Every element occurs in r blocks;

  3. Every pair of elements, which are in the same row of the m×n array, occur together in λ1 blocks whereas every other pair of elements occur together in λ2 blocks.

The non–negative integers: v=mn,b,r,k, λ1and λ2 are known as parameters of the GD design and they satisfy the relations: bk=vr;(n–1)λ1+n(m–1)λ2=r(k–1). Furthermore, if r–λ1=0 then the GD design is singular; if r–λ1>0 and rk–vλ2=0 then it is semi–regular (SR); and if r–λ1>0 and rk–vλ2>0, the design is regular (R) [6].

Transversal designs are special classes of SRGD designs having λ1=0, k=m. Some recent constructions of GD designs using certain combinatorial matrices may be found in [7,8].

Example 1. Consider the following resolvable solution of an SRGD design SR9 with parameters v=8,b=16,r=4,k=2,λ1=0,λ2=1,m=2,n=4 as given in [6]:

RI: [(1 5) (2 6) (3 7) (4 8)];

RII: [(2 7) (1 8) (4 5) (3 6)];

RIII: [(4 6) (3 5) (2 8) (1 7)];

RIV: [(3 8) (4 7) (1 6) (2 5)].

The arrangement of v=8 elements in 2×4 array is given as: 12345678

2.3 L2−type design

Let v=n2elements be arranged in an n×n array. An L2−type (Latin square) design is an arrangement of the v=n2 elements in b blocks each of size k such that:

  1. Every element occurs at most once in a block;

  2. Every element occurs in r blocks;

  3. Every pair of elements, which are in the same row or in the same column of the n×n array, occur together in λ1 blocks whereas every other pair of elements occur together in λ2 blocks.

The non–negative integers v=n2,b,r,k,λ1and λ2 are known as parameters of the L2 – type design and they satisfy the relations: bk=vr;2(n–1)λ1+(n–1)2λ2=r(k–1). Some recent constructions of these designs may be found in [9].

Example 2. Consider an L2−type design LS26 as given in [6] with parameters v=b=9,r=k=4,n1=n2=4,λ1=1,λ2=2 whose blocks are given as:

(1269);(2468);(1489);(2579);(2347);(3459);(1567);(3678);(1358)

The arrangement of v=9 elements in 3×3 array is given as, 147258369

2.4 Nearly Optimal KPS and Efficiency

A block design D(v,b,r,k) is said to be a (v,b,r,k)−configuration if any two blocks intersect in at most one element. A (v,b,r,k)−configuration is a α−common intersection design (α – CID) if |{Bh∈B: Bi∩ Bh≠ ϕ and Bj∩ Bh≠ϕ} |≥α, whenever Bi∩ Bj= ϕ where Bi,Bj∈B are blocks of the configuration.

This implies that any two disjoint blocks intersect with at least α blocks in common or any two disjoint blocks can be connected through at least α blocks. In general, it is desirable to construct a (v,b,r,k)−configuration with α as large as possible for a given (v,b,r,k). This maximum value of α is denoted by α∗(v, b, r, k)=k(r–1). Such a configuration is called optimal [1,2]. The KPSs obtained from optimal configurations are optimal in the sense of local connectivity.

The efficiency of a KPS obtained from a (v,b,r,k)−configuration is defined here as: E=αk(r–1). Clearly E=1 for an optimal configuration. A KPS will be called nearly optimal if its efficiency E≈1 when number of nodes is very large. If an optimal KPS for a given v,b,r,k is not available, we go for nearly optimal KPS. Some examples of such KPSs are given in Section 3.

A block design D(v,b,r,k) may be used to obtain a KPS having N=b sensor nodes, k is the number of keys per node with efficiency E=αk(r–1)   where α is determined using the corresponding series of designs and α∗=k(r–1) if the KPS is optimal. A nearly optimal KPS will be denoted as (N, k,α, E).

Example 3. Consider an affine resolvable SRGD design SR23 as listed in [6] with parameters v=b=9,r=k=3,λ1=0,λ2=1,m=n=3 which is a (9, 9, 3, 3)− configuration. The resolution classes are given as:

RI: [(1 2 3) (4 5 6) (7 8 9)];

RII: [(1 5 9) (2 6 7) (3 4 8)];

RIII: [(1 6 8) (2 4 9) (3 5 7)].

It is easy to verify that any two disjoint blocks of this design intersect with six blocks in common, i.e., |{Bh∈B: Bi∩ Bh≠ ϕ and Bj∩ Bh≠ ϕ} |=6=k(r–1)=6 for Bi∩ Bj= ϕ where Bi,Bj∈B. Hence SR23 is an optimal (9, 9, 3, 3)− configuration which is a 6 – CID. The arrangement of v=9 elements in 3×3 array is given as, 147258369

3. The Constructions

3.1 Optimal KPS from Affine Resolvable L2−type designs

Let A=(aij) and B=(bij) be two m×n matrices. Then their Hadamard product A⊚B is also an m×n matrix given by A⊚B=(aijbij).

The following Series I of L2−type designs may be found in [9]:

Series I: There exists an L2−type design with parameters: (1)v=n2, b=2n,  r=2,k=n, λ1=1, λ2=0. The incidence matrix of above design is given as: N=(N1|N2)=(E1InE2In⋮⋮EnIn), where Ei(1≤i≤n) is an n×n matrix whose ith column contains only +1’s and 0 elsewhere. Now it is shown below that the design with parameters (1) is affine resolvable.

Since each row sum of N1 and N2 is one, the design is resolvable. Clearly the number of resolution classes is r=2 and each class contains ′n′ blocks. The blocks corresponding to the ′n′ columns of N1 form one resolution class (R1) and the blocks corresponding to the ′n′ columns of N2 form another resolution class (R2). Further let Bi and Bj be two blocks from R1 and R2 respectively and let Ci and Cj be columns of N which represent the blocks Bi and Bj respectively. Since the Hadamard product Ci⊚Cj contains one exactly once and remaining entry zero in the resultant column, any two blocks from different resolution classes intersect in exactly one element. Hence the design is affine resolvable.

The above Series I of L2−type designs can be mapped to an optimal KPS having number of nodes N=b=2n, ′n′ number of keys per node, α∗=k(r–1)=n and efficiency E=1 [vide Lemma 1 and [3], Section 4.1.2].

Example 4. For n=250, we obtain an L2−type design with parameters v=62500, b=500,  r=2,k=250, λ1=1, λ2=0 which can be mapped to an optimal KPS having number of nodes N=b=500, n=250 keys per node, α∗=k(r–1)=250 and efficiency E=1.

3.2 Nearly Optimal KPS from Resolvable GD Design

Example 5. A GD design with parameters: v=mn,b,r,k,λ1=0,λ2=1 is a (v, b, r,k)− configuration and the configuration is optimal if the GD design is affine resolvable and b=kr.

Proof. Consider a GD design with parameters: v=mn,b,r,k,λ1=0,λ2=1. Let Bi and Bj be any two distinct blocks of the GD with above mentioned parameters. Since any pair of distinct elements occur together in either one block or no block, we have |Bi∩Bj|≤1 and hence the above GD design is a (v, b, r, k)−configuration. The proof of second part follows from Lemma 1 of [3].

The following Series of resolvable GD designs using generalized Hadamard matrices may be found in [7]:

Series II: There exists a GD design with parameters: v=pt(pt–1),r=pt,k=pt–1,b=(pt)2, λ1=0, λ2=1,m=pt–1,n=pt where p is a prime and t>1.

First, we show that any two disjoint blocks of Series II intersect with α=(pt–2)(pt–1) blocks in common.

Let Bi=(θ1,θ2,⋯,θk) and Bj=(ρ1,ρ2,⋯,ρk) be any two disjoint blocks and Bi×Bj be their cartesian product if we consider them as sets. It is sufficient to count the blocks in which the elements (or unordered pairs) of Bi×Bj occur. In Bi×Bj there are total k2=(pt–1)2 pairs out of which ′k=pt–1′ pairs of elements belong to the rows of m×n array on which the GD design is based and thus these pairs cannot be part of any block of the GD design as λ1=0. Hence α=(pt–1)2–(pt–1)=(pt–2)(pt–1).

The Series I may be mapped to a nearly optimal KPS (N, k,α, E) having N=b=(pt)2 sensor nodes, ′k=pt–1′ keys per node, α=(pt–2)(pt–1) and efficiency given as: E=αk(r–1)=(pt–2)(pt–1)(pt–1)2=1–1pt–1 which tends to 1 as t→∞. ◻

Example 6. Consider the following resolvable solution of an SRGD design SR26 with parameters: v=12,b=16,r=4,k=3,λ1=0,λ2=1,m=3,n=4 as given in [6],

RI: [(1 2 3) (7 8 12) (5 9 10) (4 6 11)];

RII: [(1 11 12) (3 5 7) (6 8 10) (2 4 9)];

RIII: [(1 5 6) (3 4 8) (7 9 11) (2 10 12)];

RIV: [(1 8 9) (2 6 7) (3 10 11) (4 5 12)].

The arrangement of v=12 elements in 3×4 array is given as, 147102581136912

Consider disjoint blocks B1=(1 2 3) and B2=(7 8 12) of RI and consider the cartesian product B1×B2={(1 7), (1 8), (1 12), (2 7), (2 8), (2 12), (3 7), (3 8), (3 12)}. We count the number of blocks in which these pairs occur. Since the pairs (1 7), (2 8) and (3 12) of elements belong to first, second and third rows respectively of the 3×4 array, these pairs cannot be part of any block of SR26 as λ1=0. Clearly the disjoint blocks intersect with six blocks: (1 11 12), (3 5 7), (3 4 8), (2 10 12), (1 8 9), (2 6 7) in common. It can be also verified that any pair of remaining disjoint blocks also intersects with six blocks in common. Hence α=6 and SR26 is a 6−CID.

The following Table 1 lists nearly optimal KPSs using Series II having number of sensor nodes ≤1000 for different values of p and n with λ1=0,λ2=1. The design numbers 1−6 listed below may be found in [6].

Table 1 Nearly Optimal KPSs from SRGD Designs
No. SRGD Parameters (v,r,k,b,m,n) KPSs (N,k,α,E)
1 (6,3,2,9,2,3) (9,2,2,0.50)
2 (12,4,3,16,3,4) (16,3,6,0.66)
3 (20,5,4,25,4,5) (25,4,12,0.75)
4 (42,7,6,49,6,7) (49,6,30,0.84)
5 (56,8,7,64,7,8) (64,7,42,0.86)
6 (72,9,8,81,8,9) (81,8,56,0.89)
7 (110,11,10,121,10,11) (121,10,90,0.90)
8 (156,13,12,169,12,13) (156,12,132,0.92)
9 (240,16,15,256,15,16) (256,15,210,0.93)
10 (272,17,16,289,16,17) (289,16,240,0.94)
11 (342,19,18,361,18,19) (361,18,306,0.94)
12 (506,23,22,529,22,23) (529,22,462,0.95)
13 (600,25,24,625,24,25) (625,24,552,0.96)
14 (702,27,26,729,26,27) (729,26,650,0.96)
15 (812,29,28,841,28,29) (841,28,756,0.96)
16 (930,31,30,961,30,31) (961,30,870,0.97)

4. Resiliency

In a (v, b, r, k)−configuration, the compromise of ′s′ random nodes affect a given link with probability roughly equal to: fail(s)=1– (1–r–2b–2)s. Clearly for a larger resiliency, fail(s) should have a smaller value [1].

Example 7. For q=pt=31, Series II yields nearly optimal (930, 961, 31, 30)− configuration. This may be mapped to a KPS with 961 sensor nodes. Suppose 10 nodes are compromised, then fail (s)≈0.26. This implies that any given link is affected with a probability of 26% when 10 nodes are compromised.

Furthermore, suppose that Ni and Nj are two neighboring nodes then the probability that Ni and Nj share a common key is: Pr1=k(r–1)b–1. Clearly Pr1=1 for a symmetric balanced incomplete block design having λ=1 and Pr1<1 for another block designs.

Let η denote the number of nodes in the intersection of the neighborhoods of the two nodes Ni and Nj where η depends on the size of the physical area where the nodes are deployed, the distance between nodes and on the total number of sensor nodes in the DSN. The probability that Ni and Nj do not share a common key, but there exists a node Nh such that Nh shares a key with both Ni and Nj, is given as follows: Pr2=(1–Pr1)(1–(1–αb–2)η). Then the probability that Ni is connected to Nj via a path of length one or two is approximately: Pr=Pr1+Pr2 [1,3].

Example 8. The values of Pr1,Pr2 and fail(s) for the optimal KPS obtained from Series I are:

Pr1=n2n–1,Pr2=n–12n–1(1–(n–22(n–1))η), fail(s)=0.

Clearly the value of fail(s) is the minimum which is desirable for a KPS.

5. Concluding Remarks

Earlier Lee and Stinson [1,2] and Saurabh and Sinha [3] obtained optimal KPSs from transversal designs, affine and partially affine resolvable designs. Here nearly optimal KPS has been introduced and a class of such KPS has also been proposed using resolvable group divisible designs. An optimal KPS has also been obtained using affine resolvable L2−type design. A metric for efficiency of KPSs is given. Some other resolvable combinatorial designs (which are not affine) such as rectangular designs, balanced incomplete block designs, L2−type designs and triangular designs may also be used to obtain nearly optimal KPSs under certain conditions. The constructions of these schemes would be taken up as a future work.

Declaration of Competing Interest

The author declares that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.

References:

  1. Lee, J. and Stinson, D., 2005. A combinatorial approach to key pre-distribution for distributed sensor networks. In IEEE Wireless Communications and Networking Conference, New Orleans, LA, IEEE Communication Society (pp. 1200–1205).

  2. Lee, J. and Stinson, D., 2006. Common intersection designs. Journal of Combinatorial Designs, 14(4), pp.251–269.

  3. Saurabh, S. and Sinha, K., 2024. Optimal key pre‐distribution schemes from affine resolvable and partially affine resolvable designs. Security and Privacy, 7(1), p.e334.

  4. Eschenauer, L. and Gligor, V. D., 2002. A key-management scheme for distributed sensor networks. In Proceedings of the 10th ACM Conference on Computer and Communications Security (pp. 41–47).

  5. Bose, M., Dey, A. and Mukerjee, R., 2013. Key predistribution schemes for distributed sensor networks via block designs. Designs, Codes and Cryptography, 67, pp.115–136.

  6. Clatworthy, W.H., 1973. Tables of Two-Associate-Class Partially Balanced Designs (Vol. 63). US Government Printing Office.

  7. Saurabh, S. and Sinha, K., 2023. Matrix approaches to constructions of group divisible designs. Bulletin of the ICA, 97, pp.83-105.

  8. Saurabh, S., 2024. Some matrix constructions of non-symmetric regular group divisible designs. Bulletin of the ICA, 102, to appear.

  9. Saurabh, S. and Sinha, K., 2022. Some matrix constructions of L2−type Latin square designs. Bulletin of the ICA, 95, 93–104.

Information
Guidelines
CP Initiatives
Follow CP
Facebook X-twitter Linkedin

1970-2025 CP (Manitoba, Canada) unless otherwise stated.