Front. Math. China DOI 10.1007/s11464-016-0610-3

Constructions for key distribution patterns Shangdi CHEN,

Huihui WEI

College of Science, Civil Aviation University of China, Tianjin 300300, China c Higher Education Press and Springer-Verlag Berlin Heidelberg 2016 ⃝

Abstract Key distribution patterns (KDPs) are finite incidence structures satisfying a certain property which makes them widely used in minimizing the key storage and ensuring the security of communication between users in a large network. We construct a new KDP using t-design and combine two ω-KDPs to give new (ω −1)-KDPs, which provide secure communication in a large network and minimize the amount of key storage. Keywords Key predistribution scheme (KPS), key distribution pattern (KDP), incidence structure, design, wireless sensor network (WSN) MSC 05B05, 94A60, 94A60 1 Introduction Consider that there exists a network of v users, say P1 , P2 , . . . , Pv , they want to communicate with each other in a secure way. Then each pair of users {Pi , Pj } must possess a common secret key which use for encryption and decryption of messages sent between them. Due to this, the key management becomes a very significant problem in a large network.

1.1 Key management The study of key management can be broken down into four phases concerning the life-cycle of a cryptographic key. They are key generation, key establishment, key update, and key destruction. And the fundamental key management challenge is key establishment, which is the method by which the keys are distributed to the relevant users in the network. A key establishment scheme is a set of protocols that guarantee each group of users in a network who wish to communicate securely have the ability to establish a common key. A scheme in which the trusted authority has the ability to communicate securely with the users in the network during the key establishment phase is known as a key distribution scheme. Otherwise, the Received July 6, 2014; accepted October 23, 2016 Corresponding author: Shangdi CHEN, E-mail: [email protected]

2

Shangdi CHEN, Huihui WEI

scheme is known as a key predistribution scheme.

1.2 Key distribution schemes (KDSs) A key distribution scheme (KDS) ([14]) is a method of distributing secret information to users in the network in such a way that any pair of users can compute a secure common key. This information is generated and distributed by a trusted server which is active only on the distribution stage. The obvious (trivial) KDS would be for every user in the network to be provided with a separate key for use with each other user in the network. This would require each node to store (v − 1) keys and usually for the server to generate and store v(v − 1)/2 keys. The disadvantage is that the large amount of key storage is required both at each user and at the server in a large network. So far, there are three main types of KDSs. They are secret key cryptosystem, public-key cryptosystem, and using authentication server to establish a session key. These schemes are derived from a basic principle that the secret key is unique and perfect secrecy is assumed. There are also two types of KDSs, namely, key pre-distribution scheme and symmetric key generation scheme, which use the high cost of algebraic coding. 1.3 Key predistribution schemes (KPSs) Stinson [20,21] gave the model of key predistribution scheme (KPS) which consists of a trusted authority (TA) and a set of users U = {1, 2, . . . , n}. They assumed that the network was insecure, and any information was generated and distributed by the TA would be received by every user. The information given to user i is denoted by ui and must be distributed “off-band” in a secure manner. The secret information will enable various privileged subsets to compute keys. Let 2U be the set of all subset of users, let P ⊆ 2U be the collection of all privileged subsets to which the TA is distributing keys, and let F ⊆ 2U be the collection of all forbidden subsets against which each key remains secure. For 1 6 i 6 n, let Ui denote the set of all possible secret values that might be distributed to user i by TA. For any subset of users X ⊆ U , let UX denote the cartesian product Ui1 × Ui2 × · · · × Uij , where X = {i1 , i2 , . . . , ij } and i1 < i2 < · · · < ij . They assumed that there was a probability distribution on UU and the TA chose uU ∈ UU according to this probability distribution. A scheme is a (P, F )-KPS if it satisfies (1) each user i in any privileged subset P can compute key kP : H(KP | Ui ) = 0,

∀ i ∈ P ∈ P;

(2) no forbidden subset F ∈ F disjoint from any privileged subset P has any information on kP : H(KP ) = H(KP | UF ) for all P ∈ P and F ∈ F such that P ∩ F = ∅.

Constructions for key distribution patterns

3

1.3.1 Application of KPSs Wireless sensor networks (WSNs) which integrate wireless communication technology, sensing technology, and computer technology are considered as one of the most important technologies in the 21th century. A WSN is an ad hoc network consisting of spatially distributed sensor nodes that autonomously gather data and use wireless communications in order to relay that data. Without the ability to support an online TA, key predistribution schemes would seem the natural choice for key establishment in these ad hoc networks. The study of KPS for WSNs began by Eschenauer and Gligor [6]. They proposed a basic random key predistribution scheme with computational security and “good” connectivity of nodes. Many other papers also studied the KPS for WSNs, see q-composite schemes [4] and deterministic schemes [3,8,10]. 1.3.2 Construction for KPSs Blom [1] introduced a construction for (2, ω)-KPSs based upon the use of ω symmetric polynomials with coefficients over the finite field GF(q) and proved that the probability of any group of ω colluders can correctly guess the key for two users disjoint from these ω colluders is 1/q. Blundo [2] generalized Blom’s scheme to a (t, ω)-KPS and proved that the probability is still 1/q. Jansen [7] introduced a KPS with a storage reduction system based on the use of combinatorial keys. However, the common keys used by some pairs of users are also known to other individuals in the network. In this respect, Jansen’s scheme cannot be considered as a (2, 1)-KPS.

1.4 Organization There are few known families of KDPs. In this paper, we propose some new constructions which minimize the total number of key storage. If we have an estimate for the number of the storage of subkeys at each node satisfies rκ (Pi ) 6 2λκ in two ω-KDPs, then we combine them to give new (ω − 1)-KDPs. This paper is organized as follows. Section 2 presents the mathematical structures that are used in this paper. Section 3 covers the definitions of KDPs which form the basis of this thesis. Section 4 presents some new constructions for KDPs. Section 5 compares our constructions with several other existing ones. 2 Incidence structures and t-designs We begin by giving some definitions from design theory which we need [24]. Definition 2.1 A finite incidence structure K = (P, B, I ), where P and B are finite nonempty sets of points and blocks, respectively, and I ⊆ P × B is a binary relation between P and B. If (P, x) ∈ I , where P ∈ P and x ∈ B, then we say that P is incident

4

Shangdi CHEN, Huihui WEI

with x or x is incident with P. The set of blocks incident with a point P is usually denoted by (P ) and the set of points incident with a block x is denoted by (x). Hence, we write (Pi ) ∩ (Pj ) denotes the set of blocks incident with both Pi and Pj . Also we usually use v and b denotes the total number of points and blocks, respectively, and denote |(Pi )| by ri , denote |(xj )| by kj . Finally, we also let λ(i, j) = |(Pi ) ∩ (Pj )|,

s(i, j) = |(xi ) ∩ (xj )|.

If every block is incident with the same number of points (i.e., kj = k for some constant k) and no two blocks are incident with the same set of points, then K is called a design. Definition 2.2 Let v, k, λ, and t be integers such that v > k > 2, λ > 1, and t > 0. Let X be a set of elements, called points, and let A be a collection of nonempty subsets of X, called blocks. The pair (X, A ) is called a t-(v, k, λ) design, or, simply, a t-design, if the following properties are satisfied: (1) |X| = v; (2) each block contains exactly k points; (3) every subset of t distinct points is contained in exactly λ blocks. Theorem 2.1 Suppose that (X, A ) is a t-(v, k, λ) design, and 0 6 s 6 t. Then (X, A ) is also an s-(v, k, λs ) design, where ( ) λ v−s t−s λs = (k−s ). t−s

Corollary 2.1 Suppose that (X, A ) is a t-(v, k, λ) design. Then (1) the total number of blocks in A , denoted by b, satisfies ( ) λ vt b = λ 0 = (k ) ; t

(2) the number of blocks in A which contain any given point is a constant independent of the point, denoted by r, which satisfies vr = bk if t > 1 and r(k − 1) = λ2 (v − 1) if t > 2.

3 Key distribution patterns One method of constructing KPSs uses the elegant idea of a key distribution pattern, due to Mitchell and Piper [11]. Let v > 3, and let ω be an integer with 1 6 ω < v − 2. A ω-KDP on v points is a finite incidence structure K = (P, B, I ) with v points such that for any pair of points Pi , Pj , we have (Pi ) ∩ (Pj ) ̸⊆

ω ∪ i=1

(Qi )

Constructions for key distribution patterns

5

for any points Q1 , Q2 , . . . , Qω ∈ P \ {Pi , Pj }. Novak [12] gave the definition of generalized key distribution pattern as follows. Definition 3.1 Let K = (P, B, I ) be a finite incidence structure, and let G and F be families of non-empty subsets of P. Then K is called a (G , F )-key distribution pattern (or (G , F )-KDP), if for all G ∈ G and F ∈ F such that G ∩ F = ∅, ∩ ∪ (P ) ̸⊆ (Q). P ∈G

Q∈F

In many situations, it is appropriate to define the privileged and forbidden subsets of a (G , F )-KDP according to their cardinality. More specifically, we define (1) the set of privileged subsets to be all sets of users of some maximum specified cardinality, say t; and (2) the set of forbidden subsets to be all sets of users of some maximum specified cardinality, say ω. Then we have the following definition. Definition 3.2 define

Let P be the set of all users in the network. For t, ω > 1,

G = {G ∈ 2P : 1 6 |G| 6 t},

F = {F ∈ 2P : 1 6 |F | 6 ω}.

We refer to (G , F )-KDP defined in this way as cardinality, or more precisely, as (t, ω)-KDP. Mitchell and Piper [11] proposed a certain special kind of finite incidence structure called key distribution patterns (KDPs) for reducing the large storage requirement, which can be used to construct KPSs. There are three approaches when it comes to constructing KDPs. The first approach is to take existing KDPs and construct new KDPs from them. Mitchell and Piper [11] used this approach extensively and present several constructions. The second approach is to construct KDPs directly from other mathematical objects. In particular, finite geometry and combinatorics. O’Keefe [13] used special finite geometric structures such as inversive, Minkowski planes, and Laguerre planes to construct (t, ω)-KDPs with storage requirements lower than the trivial distribution system. Quinn [14,15] constructed KDPs from finite projective planes and affine planes. Rinaldi [16] used tangent circular structure to construct (t, ω)-KDPs. Lee and Stinson used design theory, graph theory, orthogonal and perpendicular arrays in order to construct specific (t, ω)-KDPs with particular properties [9,19,20]. The third approach to (G , F )-KDP constructions uses probabilistic techniques. Dyer et al. [5] gave the non-constructive existence results for (t, ω)KDPs.

6

Shangdi CHEN, Huihui WEI

An important study of key distribution patterns is the bounds for total number of key storage (b) and the key storage required at any one node (r). Ruszink’o [17] used a combinatorial approach to give an upper bound for (t, ω)KDPs. Quinn [14,15] presented several lower bounds for (t, ω)-KDPs using combinatorics and design theory. Stinson and Trung used resilient functions for improving the efficiency of (G , F )-KDPs [20,21]. Later, Stinson et al. used combinatorics and inductive arguments to provide various new bounds for (t, ω)KDPs [22,23]. Shin and Bate [18] gave a generalization of KDP for every n-pair of users (n > 2) which was proposed by Mitchell and Piper [11] and discussed the properties and the bounds for the KDP. Novak [12] made a further promotion for KDP and gave the definition of generalized (G , F )-KDP, and proposed some methods of constructions.

4 Constructions In this section, we provide several new constructions for KDPs that used to construct KPSs.

4.1 Construct new KDP from old one Definition 4.1 Let K = (P, B, I ) be a finite incidence structure. Then for any two distinct points P1 , P2 ∈ P, we define K ∗ , which is called ∗ structure of K at P1 , P2 , and denote it by K ∗ = (P ∗ , B ∗ , I ∗ ), where B ∗ = [(P1 ) ∪ (P2 )] \ [(P1 ) ∩ (P2 )],

P ∗ = (B ∗ ) \ {P1 , P2 },

where (B ∗ ) = ∪x∈B∗ (x) and for any P ∈ P ∗ and x ∈ B ∗ , (P, x) ∈ I ∗ if and only if (P, x) ∈ I . That is, the block set of K ∗ consists of all the blocks which incident with points P1 or P2 except the blocks incident with both P1 and P2 . The point set consists of all the points incident with the blocks we defined except the points P1 , P2 , and the incidence relation follows from the incidence structure K . For convenience, we introduce some new notations representing the blocks incident with a point and the points incident with a block in the ∗ structure. For a finite incidence structure K = (P, B, I ) and two distinct points P1 , P2 ∈ P, we define (Q)∗ = (Q) ∩ B ∗ ,

(x)∗ = (x) ∩ P ∗ ,

∀ Q ∈ P ∗, ∀ x ∈ B∗.

The following result shows that the ∗ structure of a t-(v, k, λ) design is again a design. Theorem 4.1 Let K be a t-(v, k, λ) design with t > 3, and let P1 , P2 be any two distinct points of K . Then K ∗ is a (t − 2)-(v − 2, k − 1, 2(λt−1 − λ)) design, where λt−1 = λ(v − t + 1)/(k − t + 1).

Constructions for key distribution patterns

7

Proof Clearly, |P ∗ | = v − 2. Each block of K ∗ is the block of K which incident with points P1 or P2 removes the point P1 or P2 , so it contains exactly k − 1 points. Then we just need to prove that every set of t − 2 distinct points is contained in exactly λ∗ blocks. Since K is a t-(v, k, λ) design, by Theorem 2.1, K can also be regarded as a (t − 1)-(v, k, λt−1 ) design, where λt−1 = λ(v − t + 1)/(k − t + 1). Let Q = {Q1 , Q2 , . . . , Qt−2 } be a (t−2)-subset of P ∗ . Any (t−2)-subset of P ∗ , together with P1 or P2 , forms a (t − 1)-subset of P. By definition of t-design, we have t−2 t−2 ∩ ∩ (Qi ) ∩ (P1 ) = (Qi ) ∩ (P2 ) = λt−1 . i=1

Any (t − 2)-subset of also have

i=1

P ∗,

together with P1 and P2 , forms a t-subset of P. We

t−2 ∩ (Qi ) ∩ (P1 ) ∩ (P2 ) = λt = λ. i=1

For any x ∈ B ∗ , that is, x ∈ [(P1 ) ∪ (P2 )] \ [(P1 ) ∩ (P2 )], we have t−2 ∩

(Qi )∗ =

i=1

t−2 ∩

(Qi ) ∩ B ∗

i=1

[ t−2 ] [ t−2 ] [ t−2 ] ∩ ∩ ∩ = (Qi ) ∩ (P1 ) ∪ (Qi ) ∩ (P1 ) \ (Qi ) ∩ (P1 ) ∩ (P2 ) , i=1

i=1

i=1

so any (t − 2)-subset Q = {Q1 , Q2 , . . . , Qt−2 } in the ∗ structure is contained in exactly λ∗ blocks of B ∗ , where t−2 t−2 t−2 ∩ ∩ ∩ λ = (Qi ) ∩ (P1 ) + (Qi ) ∩ (P2 ) − 2 (Qi ) ∩ (P1 ) ∩ (P2 ) ∗

i=1

i=1

i=1

= λt−1 + λt−1 − 2λ = 2(λt−1 − λ). Then we have shown that K

∗

is a (t − 2)-(v − 2, k − 1, 2(λt−1 − λ)) design. 

The corresponding result for (G , F )-KDPs is given below. Theorem 4.2 If a finite incidence structure K = (P, B, I ) is a (G , F )KDP, then for any two distinct points P1 , P2 ∈ P, K ∗ = (P ∗ , B ∗ , I ∗ ) is a (G ∗ , F ∗ )-KDP, where G ∗ = {G \ {P1 } : P1 ∈ G ∈ G , P2 ∈ / G, ∅ ̸= G \ {P1 } ⊆ P ∗ }, F ∗ = {F \ {P2 } : P2 ∈ F ∈ F , P1 ∈ / F, ∅ ̸= F \ {P2 } ⊆ P ∗ }. Proof Note that K is a (G , F )-KDP, that is, for all G ∈ G and F ∈ F such that G ∩ F = ∅, we have ∩ ∪ (P ) ̸⊆ (Q). P ∈G

Q∈F

8

Shangdi CHEN, Huihui WEI

For any two distinct points P1 , P2 ∈ P, consider G∗ = G \ {P1 } ∈ G ∗ ,

F ∗ = F \ {P2 } ∈ F ∗ .

We have G = G∗ ∪ {P1 },

F = F ∗ ∪ {P2 },

and if G∗ ∩F ∗ = ∅, then we have G∩F = ∅. Suppose that K ∗ is not a (G ∗ , F ∗ )KDP, which means that there exists some G∗ ∈ G ∗ and some F ∗ ∈ F ∗ such that G∗ ∩ F ∗ = ∅ and ∩ ∪ (P )∗ ⊆ (Q)∗ . P ∈G∗

Q∈F ∗

Then ∩

∩

(P ) =

P ∈G

P ∈G∗ ∪{P

=

∩

(P ) 1}

(P ) ∩ (P1 )

P ∈G∗

⊆

∩

(P ) ∩ [(P1 ) ∪ (P2 )]

P ∈G∗

=

∩

(P ) ∩ {B ∗ ∪ [(P1 ) ∩ (P2 )]}

P ∈G∗

=

[ ∩

(P ) ∩ B

∗

P ∈G∗

⊆

∩

] ∪

[ ∩

] (P ) ∩ (P1 ) ∩ (P2 )

P ∈G∗

(P )∗ ∪ [(P1 ) ∩ (P2 )]

(since (P ) ∩ B ∗ = (P )∗ )

P ∈G∗

⊆

∪

(Q)∗ ∪ [(P1 ) ∩ (P2 )]

Q∈F ∗

⊆

∪

(Q) ∪ [(P1 ) ∩ (P2 )] (since (Q)∗ = (Q) ∩ B ∗ )

Q∈F ∗

⊆

∪

(Q) ∪ (P2 )

Q∈F ∗

=

∪

(Q).

Q∈F

This contradicts the fact that K is a (G , F )-KDP, and hence, K ∗ is a (G ∗ , F ∗ )KDP.  We now demonstrate Theorem 4.2 with the following example. Example 4.1

Let K = (P, B, I ) be a finite incidence structure represented

Constructions for key distribution patterns

9

by the following 5 × 5 binary matrix: P1 P2 P3 P4 P5

 x1 1 1  0  1 1

x2 0 1 1 0 1

x3 1 0 1 1 0

x4 1 1 1 0 0

x5  1 0 . 0  1 1

Then K is a (G , F )-KDP, where G = {{P1 , P2 , P4 , P5 }, {P2 , P3 , P5 }, {P1 , P3 , P4 }, {P1 , P2 , P3 }, {P1 , P4 , P5 }, {P1 , P2 }, {P1 , P3 }, {P1 , P4 }, {P2 , P3 }, {P2 , P5 }, {P1 }, {P2 }, {P3 }, {P5 }}, F = {{P1 }, {P2 }, {P3 }, {P4 }, {P5 }, {P1 , P4 }, {P2 , P3 }, {P2 , P5 }, {P4 , P5 }}. The ∗ structure of K at points P1 , P2 is x2 P3 1 P4  0 P5 1 and K

∗

x3 1 1 0

x5 0 , 1 1

is a (G ∗ , F ∗ )-KDP, where G ∗ = {{P3 }, {P4 }, {P4 , P5 }, {P3 , P4 }},

F ∗ = {{P3 }, {P5 }}.

We have the following corollary for the special case when F consists of all subsets of P of cardinality at most ω. Corollary 4.1 If a finite incidence structure K = (P, B, I ) is a (G , ω)KDP, then for any two distinct points P1 , P2 ∈ P, K ∗ = (P ∗ , B ∗ , I ∗ ) is a (G ∗ , ω − 1)-KDP, where G ∗ = {G \ {P1 } : P1 ∈ G ∈ G , P2 ∈ / G, ∅ ̸= G \ {P1 } ⊆ P ∗ }. Proof It follows from Theorem 4.2. If F = {F ∈ 2P : 0 < |F | 6 ω}, then for any two distinct points P1 , P2 ∈ P, we have F ∗ = {F \ {P2 } : P2 ∈ F ∈ F , P1 ∈ / F, ∅ ̸= F \ {P2 } ⊆ P ∗ } ∗

= {F ∈ 2P : 0 < |F | 6 ω − 1}.



In a similar way, we have the following corollary for the special case when G consists of all subsets of P of cardinality at most t. Corollary 4.2 If a finite incidence structure K = (P, B, I ) is a (t, F )KDP with 2 6 t < |P| − ω, then for any two distinct points P1 , P2 ∈ P, K ∗ = (P ∗ , B ∗ , I ∗ ) is a (t − 1, F ∗ )-KDP.

10

Shangdi CHEN, Huihui WEI

Proof It follows from Theorem 4.2. When G = {G ∈ 2P : 1 < |G| 6 t}, it ∗ follows that G ∗ = {G ∈ 2P : 0 < |G| 6 t − 1}.  Theorem 4.3 G ∈ G , then

If K is a (G , ω)-KDP, where 2 6 |G| < |P| − ω for each (

∗

|B | > log2

) |G ∗ | . ⌈(ω − 1)/2⌉

Proof From Corollary 4.2, we know that K ∗ = (P ∗ , B ∗ , I ∗ ) is a (G ∗ , ω − 1)KDP, where G ∗ = {G \ {P1 } : P1 ∈ G ∈ G , P2 ∈ / G}. Then from [12, Theorem 6.1.8] that if a finite incidence structure K = (P, B, I ) is a (G , ω)-KDP, then ( ) |G | b > log2 , ⌈ω/2⌉ 

which gives the desired result.

Unfortunately, if K ∗ is a (G ∗ , F ∗ )-KDP, the K may not be a (G , F )-KDP, and the following example demonstrates this. Example 4.2 Let K = (P, B, I ) be a finite incidence structure represented by the following 5 × 4 binary matrix: P1 P2 P3 P4 P5

 x1 1 1  0  0 1

x2 0 1 1 1 0

x3 1 1 1 0 0

x4  1 0 . 1  0 1

In this example, K is not a (G , F )-KDP, where G = {{P1 , P2 , P5 }, {P2 , P3 , P4 }, {P1 , P2 , P3 }, {P1 , P3 , P5 }, {P1 , P2 }, {P1 , P3 }, {P1 , P5 }, {P2 , P3 }, {P3 , P5 }, {P1 }, {P2 }, {P3 }, {P4 }}, F = {{P1 }, {P4 }, {P5 }, {P1 , P3 }, {P1 , P5 }, {P2 , P4 }, {P3 , P4 }, {P4 , P5 }}. Since {P3 , P5 } ∈ G , {P1 } ∈ F , and {P3 , P5 } ∩ {P1 } = ∅, but {P3 , P5 } ⊆ {P1 , P3 , P5 }, we have (P3 ) ∩ (P5 ) ⊆ (P1 ). However, the ∗ structure of K at points P1 , P2 is a (G ∗ , F ∗ )-KDP, where G ∗ = {{P3 }, {P5 }, {P3 , P5 }},

F ∗ = {{P4 }}.

By generalizing the ∗ structure, we have the structure as follows. Definition 4.2 Let K = (P, B, I ) be a finite incidence structure. Then for any non-empty set X ⊆ P, we define K X , the structure of K at X and denoted by K X = (P X , B X , I X ), where ∪ ∩ BX = (P ) \ (P ), P X = (B X ) \ X, P ∈X

P ∈X

Constructions for key distribution patterns

11

and for any P ∈ P X and x ∈ B X , (P, x) ∈ I X if and only if (P, x) ∈ I . For a finite incidence structure K = (P, B, I ) and a non-empty set X ⊆ P, we define (Q)X = (Q) ∩ B X ,

(x)X = (x) ∩ P X ,

∀ Q ∈ P X , ∀ x ∈ BX .

Corollary 4.3 If a finite incidence structure K = (P, B, I ) is a (G , F )KDP, then for any non-empty set X ⊆ P, K X = (P X , B X , I X ) is a (G X , F X )-KDP, where X = X1 ∪ X2 , X1 ∩ X2 = ∅, and G X = {G \ X1 : X1 ⊆ G, X2 ̸⊆ G, ∅ ̸= G \ X1 ⊆ P X }, F X = {F \ X2 : X2 ⊆ F, X1 ̸⊆ F, ∅ ̸= F \ X2 ⊆ P X }. Proof Note that K is a (G , F )-KDP, that is, for all G ∈ G and F ∈ F such that G ∩ F = ∅, we have ∩ ∪ (P ) ̸⊆ (Q). P ∈G

Q∈F

For any non-empty set X ⊆ P and X = X1 ∪ X2 , consider GX = G \ X1 ∈ G X ,

F X = F \ X2 ∈ F X .

Since G = GX ∪ X1 , F = F X ∪ X2 , when GX ∩ F X = ∅, we have G ∩ F = ∅. Suppose that K X is not a (G X , F X )-KDP, which means that there exist some GX ∈ G X and some F X ∈ F X such that GX ∩ F X = ∅ and ∩ ∪ (P )X ⊆ (Q)X . P ∈GX

Q∈F X

Then ∩

(P ) =

P ∈G

∩

(P )

P ∈GX ∪X1

=

∩

(P ) ∩

∩

(P ) ∩

=

∪

(P )

P ∈X

P ∈GX

∩

(P )

P ∈X1

P ∈GX

⊆

∩

[

(P ) ∩ B

X

P ∈GX

=

[ ∩

⊆

∩

P ∈GX

∪ ]

(P ) ∩ B

P ∈GX

(P )X ∪

∩

X

∩ P ∈X

] (P )

P ∈X

∪

[ ∩ P ∈GX

(P )

(P ) ∩

∩

] (P )

P ∈X

(since (P ) ∩ B X = (P )X )

12

Shangdi CHEN, Huihui WEI

⊆

∪

(Q)X ∪

∪

(Q) ∪

=

∪

(P )

(since (Q)X = (Q) ∩ B X )

P ∈X2

Q∈F X

∪

(P )

P ∈X2

Q∈F X

⊆

∩

(Q).

Q∈F

This contradicts the fact that K is a (G , F )-KDP, and hence, K (G X , F X )-KDP.

X

is a 

4.2 Construct new KDPs from multiple KDPs Construction 4.2.1 Let K = (Pκ , Bκ , Iκ ) and φ = (Pφ , Bφ , Iφ ) be two finite incidence structures with vκ , bκ and vφ , bφ points and blocks, respectively. Then combines these two structures to give a new finite incidence structure with vκ + vφ points and bκ · bφ blocks, which is denoted by V = (Pν , Bν , Iν ). Let Pν = Pκ ∪ Pφ , Bν = {(x, y) | x ∈ Bκ , y ∈ Bφ }, and define Iν as follows. For each P ∈ Pν , • if P ∈ Pκ , then (P, (x, y)) ∈ Iν if and only if (P, x) ∈ Iκ ; • if P ∈ Pφ , then (P, (x, y)) ∈ Iν if and only if (P, y) ∈ Iφ . Mitchell and Piper [11] proved that if K = (Pκ , Bκ , Iκ ) and φ = (Pφ , Bφ , Iφ ) are ω-KDPs, then V = (Pν , Bν , Iν ) also is a ω-KDP. Construction 4.2.2 Let K = (Pκ , Bκ , Iκ ) and φ = (Pφ , Bφ , Iφ ) be two finite incidence structures with vκ , bκ and vφ , bφ points and blocks, respectively. Then combines these two structures to give a new finite incidence structure with vκ + vφ − 1 points and bκ + (rκ (P1 ) + rκ (P2 ) − 2λκ )(bφ − 1) blocks, where rκ (P1 ), rκ (P2 ) are the number of blocks incident with chosen points P1 , P2 from Pκ , respectively, λκ is the number of blocks incident with both P1 and P2 . It is denoted by V = (Pν , Bν , Iν ). Let Pν = (Pκ \ {P1 }) ∪ Pφ , Bν = {x | x ∈ Bκ \ Bκ∗ } ∪ {(x, y) | x ∈ Bκ∗ , y ∈ Bφ }, where Bκ∗ = {x ∈ Bκ | P1 ∈ (x), P2 ∈ / (x)} ∪ {x | P1 ∈ / (x), P2 ∈ (x)} = {x ∈ Bκ | x ∈ (P1 ), x ∈ / (P2 )} ∪ {x | x ∈ / (P1 ), x ∈ (P2 )}, and define Iν as follows. For each P ∈ Pν , • if P ∈ Pκ , then (P, x) ∈ Iν if and only if (P, x) ∈ Iκ , and (P, (x, y)) ∈ Iν if and only if (P, x) ∈ Iκ ; • if P ∈ Pφ , then (P, (x, y)) ∈ Iν if and only if (P, y) ∈ Iφ . For convenience, let us introduce some new notations. For each P ∈ Pν , let (P )′ be the set of all blocks in Bν incident with P with respect to Iν . For

Constructions for key distribution patterns

13

x ∈ Bν , let (x)′ be the set of all points in Pν incident with x with respect to Iν . We have the following lemmas. Lemma 4.1 In Construction 4.2.2, let P be an element of Pν . (1) If P ∈ Pκ \ {P1 }, then (P )′ = [(P ) ∩ (Bκ \ Bκ∗ )] ∪ [((P ) ∩ Bκ∗ ) × Bφ ]. (2) If P ∈ Pφ , then Lemma 4.2 (x).

(P )′ = Bκ∗ × (P ).

In Construction 4.2.2, if x ∈ Bκ \ Bκ∗ , then x ∈ Bν and (x)′ =

Proof For any P ∈ (x), (P, x) ∈ Iκ . Since x ∈ Bκ \ Bκ∗ , P ∈ (x)′ . That is, (x) ⊆ (x)′ . Conversely, for any P ∈ (x)′ , (P, x) ∈ Iν . Since x ∈ Bκ \ Bκ∗ , we have P ∈ Pκ and (P, x) ∈ Iκ , and then P ∈ (x). That is, (x)′ ⊆ (x). Hence, (x)′ = (x).  Lemma 4.3 In Construction 4.2.2, if x ∈ Bκ∗ , y ∈ Bφ , then (x, y) ∈ Bν and (x, y)′ = (x) ∪ (y). Proof For any P ∈ (x, y)′ , if P ∈ Pκ , then (P, x) ∈ Iκ and P ∈ (x); if P ∈ Pφ , then (P, y) ∈ Iφ and P ∈ (y). Therefore, P ∈ (x) ∪ (y), that is, (x, y)′ ⊆ (x) ∪ (y). Conversely, for any P ∈ (x) ∪ (y) and x ∈ Bκ∗ , if P ∈ (x), then P ∈ Pκ and (P, (x, y)) ∈ Iν , so P ∈ (x, y)′ ; if P ∈ (y), then P ∈ Pφ and (P, (x, y)) ∈ Iν , so P ∈ (x, y)′ . Therefore, (x) ∪ (y) ⊆ (x, y)′ . Hence, (x, y)′ = (x) ∪ (y).  Theorem 4.4 If two finite incidence structures K = (Pκ , Bκ , Iκ ) and φ = (Pφ , Bφ , Iφ ) are ω-KDPs (ω > 1), where Pκ ∩ Pφ = ∅, then V = (Pν , Bν , Iν ) is an (ω − 1)-KDP, where V is defined as Construction 4.2.2. Proof For any two distinct points A, B ∈ Pν , we need to consider the following three cases: (1) A, B ∈ Pκ ; (2) A, B ∈ Pφ ; (3) A ∈ Pκ , B ∈ Pφ . Choosing any (ω − 1)-subset C from Pν with A, B ∈ / C , let C1 = C ∩ Pκ ,

C2 = C ∩ Pφ .

|C1 | 6 ω − 1,

|C2 | 6 ω − 1.

It follows that Since Pκ ∩ Pφ = ∅, we have C1 ∩ C2 = ∅,

C = C1 ∪ C2 .

14

Shangdi CHEN, Huihui WEI

∪

Then ∪

(Q)′ =

(Q)′ ∪

∪

=

(Q)′ ,

{[(Q) ∩ (Bκ \ Bκ∗ )] ∪ [((Q) ∩ Bκ∗ ) × Bφ ]}

Q∈C1

Q∈C1

∪ Q∈C2

Q∈C1

Q∈C

∪

∪

(Q)′ =

[(Q) ∩ (Bκ \ Bκ∗ )] ∪

Q∈C1

∪

[((Q) ∩ Bκ∗ ) × Bφ ],

Q∈C1

∪

(Q)′ =

∪

[Bκ∗ × (Q)].

Q∈C2

Q∈C2

Case 1 A, B ∈ Pκ . We have (A)′ = [(A) ∩ (Bκ \ Bκ∗ )] ∪ [((A) ∩ Bκ∗ ) × Bφ ], (B)′ = [(B) ∩ (Bκ \ Bκ∗ )] ∪ [((B) ∩ Bκ∗ ) × Bφ ]. Since K is an ω-KDP, we have ∪

(A) ∩ (B) ̸⊆

(Q),

Q∈C1

which means that there exists a block xκ ∈ Bκ such that xκ ∈ (A) ∩ (B) but xκ ∈ / ∪Q∈C1 (Q). We discuss the following two subcases. Subcase 1.1 xκ ∈ Bκ \ Bκ∗ . We have xκ ∈ (A) ∩ (Bκ \ Bκ∗ ),

xκ ∈ (B) ∩ (Bκ \ Bκ∗ ).

Clearly, xκ ∈ (A)′ ∩ (B)′ ,

∪

xκ ∈ /

(Q)′ ,

Q∈C2

xκ ∈ /

∪

{[(Q) ∩ Bκ∗ ] × Bφ }.

Q∈C1

From xκ ∈ / ∪Q∈C1 (Q), we can deduce that ∪ [(Q) ∩ (Bκ \ Bκ∗ )]. xκ ∈ / Q∈C1

Therefore, xκ ∈ / ∪Q∈C1 (Q)′ . Hence, ∪ ∪ ∪ (Q)′ . (Q)′ = (Q)′ ∪ xκ ∈ / Q∈C1

Subcase 1.2

xκ ∈ Bκ∗ .

Q∈C2

Q∈C

Constructions for key distribution patterns

We have

15

xκ ∈ (A) ∩ Bκ∗ ,

xκ ∈ (B) ∩ Bκ∗ .

For any y ∈ Bφ , clearly, we have (xκ , y) ∈ (A)′ ∩ (B)′ ,

∪

(xκ , y) ∈ /

[(Q) ∩ (Bκ \ Bκ∗ )].

Q∈C1

From xκ ∈ / ∪Q∈C1 (Q), we have xκ ∈ /

∪

[(Q) ∩ Bκ∗ ].

Q∈C1

Therefore,

∪

(xκ , y) ∈ /

{[(Q) ∩ Bκ∗ ] × Bφ }.

Q∈C1

Hence,

∪

(xκ , y) ∈ /

(Q)′ .

Q∈C1

On the other hand, since φ is an ω-KDP, we know that ∪ (Q) ̸= Bφ , Q∈C2

which implies that there exists a block yφ ∈ Bφ but yφ ∈ / ∪Q∈C2 (Q), and it follows that ∪ ∪ (xκ , yφ ) ∈ / [Bκ∗ × (Q)] = (Q)′ . Q∈C2

Q∈C2

Thus, (xκ , yφ ) ∈ (A)′ ∩ (B)′ , and (xκ , yφ ) ∈ /

∪

∪

(Q)′ ∪

Q∈C1

Case 2 A, B ∈ Pφ . We have (A)′ = Bκ∗ × (A),

(Q)′ =

Q∈C2

∪

(Q)′ .

Q∈C

(B)′ = Bκ∗ × (B).

Since φ is an ω-KDP, we have (A) ∩ (B) ̸⊆

∪

(Q),

Q∈C2

which means that there exists a block yφ ∈ Bφ such that yφ ∈ (A) ∩ (B) but yφ ∈ / ∪Q∈C2 (Q).

16

Shangdi CHEN, Huihui WEI

For any x ∈ Bκ∗ , clearly, we have ∪ (x, yφ ) ∈ (A)′ ∩ (B)′ , (x, yφ ) ∈ / (Q)′ ,

∪

(x, yφ ) ∈ /

Q∈C2

[(Q) ∩ (Bκ \ Bκ∗ )].

Q∈C1

Also, since K is an ω-KDP, and |C1 | 6 ω − 1, we know that ∪ (P1 ) ̸⊆ (Q), Q∈C1 ∪{P2 }

which means that there exists a block xκ ∈ (P1 ) but xκ ∈ / ∪Q∈C1 ∪{P2 } (Q), and it implies ∪ xκ ∈ / (Q), xκ ∈ / (P2 ), Q∈C1

that is, xκ ∈

Bκ∗ .

Therefore, ∪

(xκ , yφ ) ∈ /

{[(Q) ∩ Bκ∗ ] × Bφ }.

Q∈C1

Hence, (xκ , yφ ) ∈ /

∪

(Q)′ .

Q∈C1

Thus, (xκ , yφ ) ∈

(A)′

∩

(B)′ ,

(xκ , yφ ) ∈ /

and ∪

(Q)′ ∪

Q∈C1

∪

(Q)′ =

Q∈C2

∪

(Q)′ .

Q∈C

Case 3 A ∈ Pκ and B ∈ Pφ . We have (A)′ = [(A) ∩ (Bκ \ Bκ∗ )] ∪ [((A) ∩ Bκ∗ ) × Bφ ],

(B)′ = Bκ∗ × (B).

Since K is an ω-KDP, and |C1 | 6 ω − 1, we have ∪ (A) ∩ (P1 ) ̸⊆ (Q). Q∈C1 ∪{P2 }

That is, there exists a block xκ ∈ (A) ∩ (P1 ) but xκ ∈ / ∪Q∈C1 ∪{P2 } (Q), which implies ∪ (Q), xκ ∈ / (P2 ), xκ ∈ / Q∈C1

Bκ∗ .

and so xκ ∈ (A) ∩ Also, since φ is an ω-KDP, and |C2 | 6 ω − 1, similarly, we know that there exists a block yφ ∈ (B) but yφ ∈ / ∪Q∈C2 (Q). Then we have ∪ {[(Q) ∩ Bκ∗ ] × Bφ }, (xκ , yφ ) ∈ (A)′ ∩ (B)′ , (xκ , yφ ) ∈ / Q∈C1

Constructions for key distribution patterns

and (xκ , yφ ) ∈ /

∪

17

[Bκ∗ × (Q)] =

Q∈C2

Thus, (xκ , yφ ) ∈ /

∪ Q∈C1

(Q)′ ∪

∪

(Q)′ .

Q∈C2

∪

(Q)′ =

Q∈C2

∪

(Q)′ .

Q∈C

That is, for any two distinct points A, B ∈ Pν , we have ∪ (A)′ ∩ (B)′ ̸⊆ (Q)′ . Q∈C

Hence, V = (Pν , Bν , Iν ) is an (ω − 1)-KDP.



Construction 4.2.3 Let K = (Pκ , Bκ , Iκ ) and φ = (Pφ , Bφ , Iφ ) be two finite incidence structures with vκ , bκ and vφ , bφ points and blocks, respectively. Then combines these two structures to give a new finite incidence structure with vκ + vφ − 2 points and bκ + bφ + (rκ (P1 ) + rκ (P2 ) − 2λκ − 1)(rφ (Q1 ) + rφ (Q2 ) − 2λφ − 1) − 1 blocks, where rκ (P1 ), rκ (P2 ) are the number of blocks incident with the chosen points P1 , P2 from Pκ , respectively, λκ is the number of blocks incident with both P1 and P2 . And rφ (Q1 ), rφ (Q2 ) are the number of blocks incident with the chosen points Q1 , Q2 from Pφ , respectively, λφ is the number of blocks incident with both Q1 and Q2 , and denote it by V = (Pν , Bν , Iν ), where Pν = (Pκ \ {P1 }) ∪ (Pφ \ {Q1 }), Bν = {x | x ∈ Bκ \ Bκ∗ } ∪ {y | y ∈ Bφ \ Bφ∗ } ∪ {(x, y) | x ∈ Bκ∗ , y ∈ Bφ∗ }, where Bκ∗ = {x ∈ Bκ | P1 ∈ (x), P2 ∈ / (x)} ∪ {x | P1 ∈ / (x), P2 ∈ (x)} = {x ∈ Bκ | x ∈ (P1 ), x ∈ / (P2 )} ∪ {x | x ∈ / (P1 ), x ∈ (P2 )}, Bφ∗ = {y ∈ Bν | Q1 ∈ (y), Q2 ∈ / (y)} ∪ {y | Q1 ∈ / (y), Q2 ∈ (y)} = {y ∈ Bν | y ∈ (Q1 ), y ∈ / (Q2 )} ∪ {y | y ∈ / (Q1 ), y ∈ (Q2 )}, and define Iν as follows. For any P ∈ Pν , • if P ∈ Pκ , then (P, x) ∈ Iν if and only if (P, x) ∈ Iκ , and (P, (x, y)) ∈ Iν if and only if (P, x) ∈ Iκ ; • if P ∈ Pφ , then (P, y) ∈ Iν if and only if (P, y) ∈ Iφ , and (P, (x, y)) ∈ Iν if and only if (P, y) ∈ Iφ . Lemma 4.4 In Construction 4.2.3, let P be an element of Pν . (1) If P ∈ Pκ \ {P1 }, then (P )′ = [(P ) ∩ (Bκ \ Bκ∗ )] ∪ [((P ) ∩ Bκ∗ ) × Bφ∗ ].

18

Shangdi CHEN, Huihui WEI

(2) If P ∈ Pφ \ {Q1 }, then (P )′ = [(P ) ∩ (Bφ \ Bφ∗ )] ∪ [Bκ∗ × ((P ) ∩ Bφ∗ )]. Lemma 4.5 In Construction 4.2.3, (1) if x ∈ Bκ \ Bκ∗ , then x ∈ Bν and (x)′ = (x); (2) if y ∈ Bφ \ Bφ∗ , then y ∈ Bν and (y)′ = (y); (3) if x ∈ Bκ∗ , y ∈ Bφ∗ , then (x, y) ∈ Bν and (x, y)′ = (x) ∪ (y). Theorem 4.5 If two finite incidence structures K = (Pκ , Bκ , Iκ ) and φ = (Pφ , Bφ , Iφ ) are ω-KDPs (ω > 1), where Pκ ∩ Pφ = ∅, Bκ ∩ Bφ = ∅, then V = (Pν , Bν , Iν ) is an (ω − 1)-KDP, where V is defined as in Construction 4.2.3. Proof For any two distinct points A, B ∈ Pν , we need to consider the following three cases: (1) A, B ∈ Pκ ; (2) A, B ∈ Pφ ; (3) A ∈ Pκ , B ∈ Pφ . We use the same notations C , C1 , and C2 as in the proof of Theorem 4.4. Then we can get ∪ ∪ ∪ (Q)′ = [(Q) ∩ (Bκ \ Bκ∗ )] ∪ [((Q) ∩ Bκ∗ ) × Bφ∗ ], Q∈C1

∪

Q∈C2

Q∈C1

∪

(Q)′ =

Q∈C1

[(Q) ∩ (Bφ \ Bφ∗ )] ∪

Q∈C2

∪

[Bκ∗ × ((Q) ∩ Bφ∗ )].

Q∈C2

Case 1 A, B ∈ Pκ . We have (A)′ = [(A) ∩ (Bκ \ Bκ∗ )] ∪ [((A) ∩ Bκ∗ ) × Bφ∗ ], (B)′ = [(B) ∩ (Bκ \ Bκ∗ )] ∪ [((B) ∩ Bκ∗ ) × Bφ∗ ]. Since K is an ω-KDP, we have (A) ∩ (B) ̸⊆

∪

(Q),

Q∈C1

which means that there exists a block xκ ∈ Bκ such that xκ ∈ (A) ∩ (B) but xκ ∈ / ∪Q∈C1 (Q). We discuss the following two subcases. Subcase 1.1 xκ ∈ Bκ \ Bκ∗ . We have xκ ∈ (A) ∩ (Bκ \ Bκ∗ ),

xκ ∈ (B) ∩ (Bκ \ Bκ∗ ).

Constructions for key distribution patterns

19

Clearly, xκ ∈ (A)′ ∩ (B)′ ,

∪

xκ ∈ /

(Q)′ ,

∪

xκ ∈ /

Q∈C2

{[(Q) ∩ Bκ∗ ] × Bφ∗ }.

Q∈C1

From xκ ∈ / ∪Q∈C1 (Q), we can deduce that ∪

xκ ∈ /

(Q) ∩ (Bκ \ Bκ∗ ).

Q∈C1

Therefore, xκ ∈ / ∪Q∈C1 (Q)′ , and hence, xκ ∈ /

∪ Q∈C1

Subcase 1.2 We have

∪

(Q)′ ∪

∪

(Q)′ =

Q∈C2

(Q)′ .

Q∈C

xκ ∈ Bκ∗ . xκ ∈ (A) ∩ Bκ∗ ,

xκ ∈ (B) ∩ Bκ∗ .

For any y ∈ Bφ∗ , clearly, we have

(xκ , y) ∈ /

∪

(xκ , y) ∈ (A)′ ∩ (B)′ , (Q) ∩ (Bκ \ Bκ∗ ),

∪

(xκ , y) ∈ /

Q∈C1

(Q) ∩ (Bφ \ Bφ∗ ).

Q∈C2

/ ∪Q∈C1 (Q), we have Furthermore, from xκ ∈ Bκ∗ and xκ ∈ xκ ∈ /

∪

[(Q) ∩ Bκ∗ ].

Q∈C1

Therefore, (xκ , y) ∈ /

∪

{[(Q) ∩ Bκ∗ ] × Bφ∗ }.

Q∈C1

Hence, (xκ , y) ∈ /

∪

(Q)′ .

Q∈C1

On the other hand, since φ is an ω-KDP, and |C2 | 6 ω − 1, we have ∪ (Q1 ) ̸⊆ (Q), Q∈C2 ∪{Q2 }

which means that there exists a block yφ ∈ (Q1 ) but yφ ∈ / ∪Q∈C2 ∪{Q2 } (Q), and it implies that ∪ (Q), yφ ∈ / (Q2 ), yφ ∈ / Q∈C2

20

Shangdi CHEN, Huihui WEI

that is, yφ ∈ Bφ∗ . Therefore, ∪

(xκ , yφ ) ∈ /

[Bκ∗ × ((Q) ∩ Bφ∗ )].

Q∈C2

Thus, (xκ , yφ ) ∈ (A)′ ∩ (B)′ , and ∪ ∪ ∪ (xκ , yφ ) ∈ / (Q)′ ∪ (Q)′ = (Q)′ . Q∈C1

Q∈C2

Q∈C

Case 2 A, B ∈ Pφ . The proof is similar to that of Case 1. Case 3 A ∈ Pκ and B ∈ Pφ . We have (A)′ = [(A) ∩ (Bκ \ Bκ∗ )] ∪ [((A) ∩ Bκ∗ ) × Bφ∗ ], (B)′ = [(B) ∩ (Bφ \ Bφ∗ )] ∪ [Bκ∗ × ((B) ∩ Bφ∗ )]. Since K and φ are both ω-KDPs, |C1 | 6 ω − 1, and |C2 | 6 ω − 1, we have ∪ ∪ (Q) and (B) ∩ (Q1 ) ̸⊆ (Q), (A) ∩ (P1 ) ̸⊆ Q∈C1 ∪{P2 }

Q∈C2 ∪{Q2 }

which means that there exists a block xκ ∈ Bκ such that xκ ∈ (A) ∩ (P1 ) but xκ ∈ / ∪Q∈C1 ∪{P2 } (Q), and it implies that ∪

xκ ∈ /

(Q),

xκ ∈ / (P2 ),

Q∈C1

that is, xκ ∈ Bκ∗ . Similarly, there exists a block yφ ∈ (B) and yφ ∈ Bφ∗ . Then we have (xκ , yφ ) ∈ (A)′ ∩ (B)′ , ∪ ∪ (xκ , yφ ) ∈ / {[(Q) ∩ Bκ∗ ] × Bφ∗ }, (xκ , yφ ) ∈ / {Bκ∗ × [(Q) ∩ Bφ∗ ]}. Q∈C1

Hence, (xκ , yφ ) ∈ /

Q∈C2

∪ Q∈C1

(Q)′ ∪

∪

(Q)′ =

Q∈C2

∪

(Q)′ .

Q∈C

That is, for any two distinct points A, B ∈ Pν , we have ∪ (Q)′ . (A)′ ∩ (B)′ ̸⊆ Q∈C

It has shown that V = (Pν , Bν , Iν ) is an (ω − 1)-KDP.



Constructions for key distribution patterns

21

5 Analysis of our constructions Theorem 5.1 [11] Suppose that (X, B) is a (G , F )-KDP. Then there exists a (G , F )-KPS. Moreover, any (t + 1)-(v, k, λ) design (X, B) is a (t, 6 ω)-KDP, where v−t ω< . k−t According to Theorem 5.1, we have the following corollary. Corollary 5.1 For t > 1, if K is a (t + 3)-(v, k, λ) design, then K is a (t + 2, 6 ω)-KDP, and K ∗ is a (t, 6 ω)-KDP, where ω<

v−t−2 . k−t−2

Proof Suppose that K is a (t+3)-(v, k, λ) design. Then, according to Theorem 4.1, K ∗ is a (t + 1)-(v − 2, k − 1, 2(λt+2 − λ)) design, where λt+2 =

λ(v − t − 2) . (k − t − 2)



We give an example to illustrate Constructions 4.2.2 and 4.2.3. Example 5.1

K is a 2-(7, 6, 5) design defined by Pκ = {P1 , P2 , . . . , P7 },

Bκ = {x1 , x2 , . . . , x7 },

and (Pi , xj ) ∈ Iκ if and only if i is not equal to j. φ is a 2-(7, 4, 2) design defined by Pφ = {Q1 , Q2 , . . . , Q7 },

Bφ = {y1 , y2 , . . . , y7 },

and y1 = {Q3 , Q5 , Q6 , Q7 },

y2 = {Q2 , Q4 , Q5 , Q6 },

y3 = {Q1 , Q4 , Q6 , Q7 },

y4 = {Q2 , Q3 , Q4 , Q7 },

y5 = {Q1 , Q2 , Q5 , Q7 },

y6 = {Q1 , Q2 , Q3 , Q6 },

y7 = {Q1 , Q3 , Q4 , Q5 }. Clearly, K , φ are both 2-KDPs, and we combine K and φ to obtain new KDPs and analyse the storage requirements. Observing the three constructions described in Table 1, it is clear that Constructions 4.2.2 and 4.2.3 are better than the constructions in [11], since the KDPs constructed in this way have smaller b for given v, which improves the network security. Table 1 scheme [11, Construction 1.5] [11, Construction 1.6] Construction 4.2.2 [11, Construction 1.7] Construction 4.2.3

Compare key storage

points v number of blocks incident with a point ri total blocks b 14 13 13 12 12

28 6 ri 24 6 ri 8 6 ri 14 6 ri 6 6 ri

6 43 6 36 6 18 6 21 6 12

49 43 19 28 16

22

Shangdi CHEN, Huihui WEI

We analyse Construction 4.2.3. If we choose points P1 , P2 and Q1 , Q2 , then the incidence structure V = (Pυ , Bυ , Iυ ) obtained using Construction 4.2.3 has point set Pυ = {P2 , P3 , . . . , P7 , Q2 , Q3 , . . . , Q7 } and block set Bυ = {x3 , x4 , x5 , x6 , x7 , y1 , y5 , y6 } ∪ {(xi , yj ) | i = 1, 2, j = 2, 3, 4, 7}. Each point is incident with different numbers of blocks, e.g., Q4 is incident with 8 blocks {(xi , yj ) | i = 1, 2; j = 2, 3, 4, 7}, Qi (i ̸= 4) is incident with 6 blocks; and P2 is incident with 9 blocks x3 , x4 , x5 , x6 , x7 , (x1 , y2 ), (x1 , y3 ), (x1 , y4 ), (x1 , y7 ), Pi (i = 3, 4, 5, 6, 7) is incident with 12 blocks.

Acknowledgements This work was supported in part by the National Natural Science Foundation of China (Grant No. 61179026) and the Fundamental Research Funds for the Central Universities (No. 3122016L005).

References 1. Blom R. An optimal class of symmetric key generation systems. In: Advances in Cryptology: Proceedings of Eurocrypt 84. Lecture Notes in Comput Sci Vol 209. 1985, 335–338 2. Blundo C, DeSantis A, Vaccaro U, Herzberg A, Kutten S, Yung M. Perfectly secure key distribution for dynamic conferences. In: Advances in Cryptology. Lecture Notes in Comput Sci, Vol 740. Berlin: Springer, 1993, 471–486 3. Camtepe S A, Yener B. Combinatorial design of key distribution mechanisms for wireless sensor networks. In: Proc of the 9th European Symp on Research in Computer Security. Berlin: Springer, 2004, 293–308 4. Chan H, Perrig A, Song D X. Random key pre-distribution schemes for sensor networks. In: Proc of 2003 IEEE Symp on Research in Security and Privacy. New York: ACM Press, 2003, 197–213 5. Dyer M, Fenner, Freize A, Thomason A. On key storage in secure networks. J Cryptology, 1995, 8: 189–200 6. Eschenauer L, Gligor V. A key management scheme for distributed sensor networks. In: Proceedings of 9th ACM Conference on Computer and Communication Security, 2002: 41–47 7. Jansen C J A. On the key storage requirements for secure terminals. Computer & Security, 1986, 5: 145–149 8. Lee J, Stinson D R. Deterministic key pre-distribution schemes for distributed sensor networks. In: Proc of the 11th Int Workshop on Selected Areas in Cryptography. Berlin: Springer, 2004, 294–307 9. Lee J, Stinson D R. On the construction of practical key predistribution schemes for distributed sensor networks using combinatorial designs. ACM T Inform Syst Se, 2008, 11: 1–35 10. Liu D, Ning P. Establishing pair-wise keys in distributed sensor networks. In: Proc of the 10th ACM Conf on Computer and Communications Security. New York: ACM Press, 2003, 41–77 11. Mitchell C J, Piper F C. Key storage in secure networks. Discrete Appl Math, 1988, 21: 215–228

Constructions for key distribution patterns

23

12. Novak J C. Generalized key distribution patterns. Doctoral Thesis. Univ of London, 2012 13. O’Keefe C M. Key distribution patterns using Minkowski planes. Des Codes Cryptogr, 1995, 5: 261–267 14. Quinn K A S. Some constructions for key distribution patterns. Des Codes Cryptogr, 1994, 4: 177–191 15. Quinn K A S. Bounds for key distribution patterns. J Cryptology, 1999, 12: 227–240 16. Rinaldi G. Key distribution patterns using tangent circle structures. Des Codes Cryptogr, 2004, 31: 289–300 17. Ruszink’o M. On the upper bound of the size of the r-cover-free families. J Combin Theory Ser A, 1994, 66: 302–310 18. Shin S H, Bate J C. Generalization of key distribution patterns for every n-pair of users. J Appl Math Informatics, 2008, 26: 563–572 19. Stinson D R. Combinatorial designs and cryptography. In: Survey in Combinatorics. Cambridge: Cambridge Univ Press, 1993, 257–287 20. Stinson D R. On some methods for unconditionally secure key distribution patterns and broadcast encryption. Des Codes Cryptogr, 1997, 12: 215–243 21. Stinson D R, Tran van Trung. Some new results on key distribution patterns and broadcast encryption. Des Codes Cryptogr, 1998, 14: 261–279 22. Stinson D R, Wei R. Generalised cover free families. Discrete Math, 2004, 279: 463–477 23. Stinson D R, Wei R, Zhu L. Some new bounds for cover free families. J Combin Theory Ser A, 2000, 90: 224–234 24. Wan Z X. Designs Theory. Beijing: Higher Education Press, 2009