Tactical decomposable regular group divisible designs and their threshold schemes

Shyam Saurabh1
1Department of Mathematics, Tata College, Kolhan University, Chaibasa, India

Abstract

Some methods of decomposing v(=mn)×b incidence matrix of regular group divisible (RGD) designs into square submatrices of order m are described. Such designs are known as tactical decomposable designs. As a by–product, resolvable solutions of some RGD designs are obtained. A relationship between tactical decomposable designs and (2, n)threshold schemes is also given.

Keywords: regular group divisible design, tactical decomposable design, resolvability, partial cyclic solution, (2, n)threshold scheme

1. Introduction

A balanced incomplete block (BIB) design or a 2 − (v, k, λ) design is an arrangement of v elements into b = λ(v² − v)/(k² − k) blocks, each of size k (k < v) such that every element occurs in exactly r blocks and any two distinct elements occur together in λ blocks. Further, a BIB design is symmetric if v = b and is self-complementary if v = 2k.

1.1. Tactical decomposable design

Let a (0, 1) – matrix N have a decomposition N = [Nij]i=1,…,s; j=1,…,t where Nij are submatrices of N of suitable sizes. The decomposition is called row tactical if row sum of Nij is rij and column tactical if the column sum of Nij is kij and tactical if it is row as well as column tactical. If N is the incidence matrix of a block design D(v, b, r, k), D is called row (column) tactical decomposable. D is called uniform row (column) tactical decomposable if rij = α (kij = β) ∀i, j. If each Nij is an m × m matrix, D is called square tactical decomposable design, STD(m).

Several methods of constructions of tactical decomposable rectangular, group divisible and L2–type designs may be found in Bekar et al. [2], Singh and Saurabh [19], Saurabh and Sinha [16], [17] and Saurabh [14], among others.

1.2. Group divisible design

Let v = mn elements be arranged in an m × n array. A regular group divisible (RGD) 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 remaining pairs of elements occur together in λ2 blocks; and
  4. r − λ1 > 0, rk − vλ2 > 0.

Further let N be a v × b incidence matrix of a block design such that JvN = kJv×b and satisfies the following conditions (1) or (2).

(i)(1)NN=(rλ1)(ImIn)+(λ1λ2)(ImJn)+λ2(JmJn).

Let Ri and Rj be any two rows of blocks of N. Then from (1), their inner product is

RiRj={rIn+λ1(JI)n,i=jλ2Jn,ij={(rλ1)In+λ1Jn,i=j,λ2Jn,ij. (ii)(2)NN=(rλ2)(InIm)+λ2(JnJm)+(λ1λ2){(JnIn)Im}.

Then (2)

RiRj={rIm+λ2(JI)m,i=j,λ1Im+λ2(JI)m,ij,={(rλ2)Im+λ2Jm,i=j,(λ1λ2)Im+λ2Jm,ij.

Then N represents a GD design with parameters: v = mn, r, k, b, λ1, λ2, m, n. For GD schemes, we refer to Saurabh [14]. A GD design will be called STD(n) or STD(m) with orthogonal rows if its incidence matrix satisfies the conditions (1) or (2) respectively.

1.3. (μ1, μ2, …, μt)–resolvable design

Let the incidence matrix N of a block design D(v, r, k, b) may be decomposed into submatrices as N = (N1 | N2 | … | Nt) such that each row sum of Ni (1 ≤ i ≤ t) is μi. Then the design is 1, μ2, …, μt)–resolvable [see Kageyama [8], Saurabh [13]]. If μ1 = μ2 = … = μt = μ then the design is μ–resolvable. Such designs are also denoted as A–resolvable designs in combinatorial design theory [see Ge and Miao [7]]. A practical application of 1, μ2, …, μt)–resolvable designs may be found in Kageyama [8]. These designs may also have potential applications in coding theory and cryptography.

1.4. Cyclic and partial cyclic designs

A block design D(v, b, r, k) is cyclic if its solution may be obtained by adding the elements of a cyclic group Zv = {0, 1, 2, …, v} mod v to the initial blocks of the design, whereas a design is partial cyclic if its solution may be obtained by developing the initial blocks under a partial cycle: 1 ↔ q, q + 1 ↔ 2q, …, [q(p − 1) + 1] ↔ v = pq of length q where (1 ↔ q) ⇐⇒ 1 → 2, 2 → 3, …, (q − 1) → q, q → 1 [see Saurabh [12]].

Some constructions of partial cyclic GD designs can be found in Dey and Nigam [6], Mukerjee et al. [10], Dey and Balasubramanian [5], Midha and Dey [9], among others.

Example 1.1. A partial cyclic solution to the GD design R80: v = 14, r = 9, k = 3, b = 42, λ1 = 6, λ2 = 1, m = 7, n = 2 may be obtained by developing the initial blocks: (1, 2, 8); (1, 8, 9); (1, 3, 8); (1, 8, 10); (1, 4, 8); (1, 8, 11) under a partial cycle 1 ↔ 7, 8 ↔ 14 of length 7 [see Clatworthy [4]].

Notation 1.2. In is the identity matrix of order n, Jv×b is the v × b matrix all of whose entries are 1 and Jv×v = Jv, A′ is the transpose of matrix A, A ⊗ B is the Kronecker product of two matrices A and B, 0n is a zero matrix of order n × n and a (0,1)–matrix: α = circ(0 1 0 … 0) is a permutation circulant matrix of order m such that αm = Im. RX numbers are from Clatworthy [4].

2. Tactical decomposable RGD designs

2.1. From partial cyclic RGD designs

Theorem 2.1. There always exists a square tactical decomposition of a partial cyclic RGD design with parameters: v=mn,r,k,b,λ1,λ2,m,n, where m is length of the partial cycle.

Proof. Let N be the incidence matrix of a RGD design D having partial cyclic solution of length m. Then the number of initial blocks is t = b/m. Our aim is to decompose N as N = [Nij]i=1,…,n; j=1,…,t where each Nij is a square matrix of order m. Then corresponding to each initial block Bi (1 ≤ i ≤ t) of D, we obtain the ith–column of blocks of N as follows:

Step I: Break the interval [1, mn] into n subintervals as: [1, m], [m + 1, 2m], …, [m(n − 1) + 1, mn] such that each subinterval contains m elements which is the length of partial cycle.

Step II: Let α = circ(0 1 0 … 0) be a permutation circulant matrix of order m. Then corresponding to initial block whose elements belong to above subintervals, we obtain the following m × m block matrices:

N1i=Im+α+α2++αm1,N2i=Im+αm+1+αm+2++α2m1(modm)=Im+α+α2++αm1,Nni=Im+αm(n1)+1+αm(n1)+2++αmn1(modm)=Im+α+α2++αm1.

Hence we obtain a STD(m) RGD design corresponding to its partial cyclic solution. ∎

2.2. From self–complementary BIB design

Theorem 2.2. The existence of a self–complementary BIB design with parameters: v=2k,r,k,b=2r,λ implies the existence of a 3–resolvable STD (2) RGD design with parameters: v=4k,r=3r,k=3k,b=4r,λ1=λ+2r,λ2=2r,m=2,n=2k.

Proof. Let M be the incidence matrix of a self–complementary BIB design. Then replacing 0I2 and 1J2 in M, we obtain a (0,1)–matrix N such that: NN=r(I2kI2)+2r(J2kJ2)+λ{(JI)2kI2}. Also, each column sum of N is 3k. Hence N represents the incidence matrix of a STD (2) RGD design with above mentioned parameters.

Since the BIB design is self–complementary, we obtain r pairs of columns Ci and Cj such that Ci+Cj=J2k×1. Such columns will be called a pair of self–complementary columns. Further replacement of 0I2 and 1J2 in each pair of self–complementary columns yields r resolution classes such that each element occurs exactly three times in every class. Hence the design is 3–resolvable.

Example 2.3. Consider a selfcomplementary BIB design with parameters: v = 4, r = 3, k = 2, b = 6, λ = 1 whose incidence matrix is:

M=[10100101|10100101100110010110100110011001|10100101100110010110100101101001].

Then replacing in M, we obtain a STD (2) RGD design R164: v=8,r=9,k=6,b=12,λ1=7,λ2=6,m=2,n=4 with incidence matrix N as given below: N=[N1|N1N2N3N2|N1N2N3N3]=[J2I2J2I2I2J2I2J2|J2I2J2I2I2J2I2J2J2I2I2J2J2I2I2J2I2J2J2I2J2I2I2J2J2I2I2J2J2I2I2J2|J2I2J2I2I2J2I2J2J2I2I2J2J2I2I2J2I2J2J2I2J2I2I2J2I2J2J2I2J2I2I2J2].

Further since each row sum of N1,N2 and N3 is 3, the design is 3resolvable.

3. Illustrative examples

Here, some RGD designs of Clatworthy [4] are identified as STD (m) using Theorem 2.1 where α=circ (0 1 00) is a permutation circulant matrix of order m. The arrangement of v=mn elements into m×n array for following RGD designs is as follows: 1m+12m+1(n1)m+12m+22m+2(n1)m+2m2m3mmn

1) R80:v=14,r=9,k=3,b=42,λ1=6,λ2=1,m=7,n=2.

Initial blocks are [(1, 2, 8), (1, 8, 9), (1, 3, 8), (1, 8, 10), (1, 4, 8), (1, 8, 11)] under the partial cycles 17, 814 of length 7. Using Theorem 2.1, we have N=[N1|N1N2N3N2|N1N2N3N3]=[αα+α2α+α2α|αα+α2α+α2ααα+α3α+α3ααα+α4α+α4ααα+α3α+α3α|αα+α2α+α2ααα+α3α+α3ααα+α4α+α4ααα+α4α+α4α].

Then NN=8(I2I7)+(J2J7)+5{(J2I2)I7}. Hence N represents the incidence matrix of R80. Further since each row sum of N1,N2 and N3 is 3, the design is 3resolvable.

The initial blocks of the remaining RGD designs listed below may be found in Clatworthy .

2) R89:v=18,r=9,k=3,b=54,λ1=2,λ2=1,m=9,n=2.

N=[N1|N1N2N2]=[αα+α3α7+α8α3|αα+α3α7+α8α3αααα+α2+α5α2+α4α+α5I7+α607αααα+α2+α5α2+α4α+α5I7+α607].

Since each row sum of N1 and N2 is 3 and 6 respectively, the design is (3, 6)resolvable.

3) R115:v=15,r=8,k=4,b=30,λ1=6,λ2=1,m=5,n=3.

N=[N1|N1N2N2]=[α+α2αααα+α2αααα+α2|α+α2αααα+α2αααα+α2α+α3αααα+α3αααα+α3α+α3αααα+α3αααα+α3].

Since each row sum of N1 and N2 is 4, the design is 4resolvable.

4) R128:v=26,r=8,k=4,b=52,λ1=0,λ2=1,m=13,n=2.

N=[N1|N1N2N2]=[α2+α4+α10ααα2+α4+α10|α2+α4+α10ααα2+α4+α10α3+α6+α7ααα3+α6+α7α3+α6+α7ααα3+α6+α7].

Since each row sum of N1 and N2 is 4, the design is 4resolvable.

5) R132:v=30,r=10,k=4,b=75,λ1=2,λ2=1,m=15,n=2.

N=[N1|N1N2N3N2|N1N2N3N3]=[α+α3+I15α5α5α+α3+I15|α+α3+I15α5α5α+α3+I15α+α5+α11α2α2α+α5+α11α+α9α+α9α+α5+α11α2α2α+α5+α11|α+α3+I15α5α5α+α3+I15α+α5+α11α2α2α+α5+α11α+α9α+α9α+α9α+α9].

Since each row sum of N1,N2 and N3 is 4, 4 and 2 respectively, the design is (2, 4, 4)resolvable.

6) R152:v=20,r=10,k=5,b=40,λ1=8,λ2=1,m=5,n=4.

N=[N1|N1N2N2]=[α+α2ααααα+α2ααααα+α2ααααα+α2|α+α2ααααα+α2ααααα+α2ααααα+α2α+α3ααααα+α3ααααα+α3ααααα+α3α+α3ααααα+α3ααααα+α3ααααα+α3].

Since each row sum of N1 and N2 is 5, the design is 5resolvable.

7) R159:v=35,r=10,k=5,b=70,λ1=2,λ2=1,m=5,n=7.

N=[N1|N1N2N2]=[circ (05,05,05, α,α,α,α2+I5|05,05,05, α,α,α,α2+I5circ (05,05,05, α,α,α,α3+α4circ (05,05,05, α,α,α,α3+α4)].

Since each row sum of N1 and N2 is 5, the design is 5resolvable.

8) R160:v=39,r=10,k=5,b=78,λ1=2,λ2=1,m=13,n=3. N=[N1|N1N2N2]=[α2+α4+α10αααα2+α4+α10αααα2+α4+α10|α2+α4+α10αααα2+α4+α10αααα2+α4+α10α3+α6+α7αααα3+α6+α7αααα3+α6+α7α3+α6+α7αααα3+α6+α7αααα3+α6+α7].

Since each row sum of N1 and N2 is 5, the design is 5resolvable.

9) R189:v=b=24,r=k=8, λ1=4,λ2=2,m=4,n=6.

N=[I6(α2+α3+I4)+(JI)6α].

10) R200:v=b=28,r=k=9, λ1=5,λ2=2,m=4,n=7.

N=[I7(α2+α3+I4)+(JI)7α].

11) R208:v=b=32,r=k=10, λ1=6,λ2=2,m=4,n=8.

N=[I8(α2+α3+I4)+(JI)8α].

4. Application in (2, n)threshold schemes

Let K be a finite key space and P be a finite set of participants. In a secret sharing scheme, a special participant DP, called the dealer, secretly chooses a key KK and distributes one share or shadow from the share set S to each participant in a secure manner, so that no participant knows the shares given to other participants. A (t, n)threshold scheme is a secret sharing scheme in which if any t(n) or more participants pool their shares, where n=|P|, then they can reconstruct the secret key KK, but any n1 or fewer participants can gain no information about it.

According to Time Magazine (May 4, 1992, p. 13), control of nuclear weapons in Russia in early 1990s depended upon “two–out–of–three” access mechanism. The three parties involved were the President, the Defense–minister and the Defense Ministry. This would correspond to a threshold scheme with n=3, t=2, op. cit. Stinson and Vanstone [21], Stinson [20].

Pieprzyk and Zhang [11] obtained ideal (t, w) threshold schemes from bt×(n+1) orthogonal array OA (bt, n+1, b, t) by considering OA (i,j) as the shares of participants Pj (1jn) and OA (i,0) as a secret key (1ibt) where OA (i,j) denotes the entry in the ith row and jth column of OA (bt, n+1, b, t). Stinson and Vanstone [21] obtained perfect threshold schemes from Steiner system S(t, w, v). Adachi and Lu [1] constructed (3, 3)threshold schemes from magic cubes by considering magic cube as a secret key and the corresponding three cubes as the shadows.

Some recent constructions of perfect secret sharing schemes from doubly resolvable GD designs and orthogonal resolutions of certain combinatorial designs can be found in Saurabh and Sinha [15,18]. A recent survey on threshold schemes from combinatorial designs may be found in Bose [3].

Present scheme: Consider a STD (m) RGD design whose each submatrix is of size m. Then there are n rows of blocks in its incidence matrix N. The dealer provides rows Ri(1in) of blocks of N to n participants as their shares. Two participants can reveal the secret if their shares Ri and Rj are orthogonal rows of the STD (m) RGD design, i.e., RiRj={rIm+λ2(JI)m,i=j,λ1Im+λ2(JI)m,ij,={(rλ2)Im+λ2Jm,i=j,(λ1λ2)Im+λ2Jm,ij.

Hence corresponding to a STD (m) RGD design, we obtain a (2, n)threshold scheme.

Further using Theorem 2.1 and 2.2, we obtain:

Scheme: The tactical decomposable RGD designs in Theorem 2.1 correspond to (2, n)threshold schemes whereas the designs of Theorem 2.2 correspond to (2, 2k) threshold schemes.

Example 4.1. The STD (4) RGD design R200 given in Section 3 can be used to obtain a (2, 7) threshold scheme.

References:

  1. T. Adachi and X.-N. Lu. Magic cubes and secret sharing schemes (algebras, logics, languages and related areas). Proceedings of the Research Institute for Mathematical Sciences, 2096:115–118, 2018.
  2. H. Bekar, C. Mitchell, and F. Piper. Tactical decomposition of designs. Aequationes Mathematicae, 25:123–152, 1982.
  3. M. Bose. Some combinatorial structures and their applications in cryptography. Statistics and Applications, 22(3):227–242, 2024.
  4. W. H. Clatworthy. Tables of Two-Associate-Class Partially Balanced Designs, volume 63. US National Bureau of Standards, 1948.
  5. A. Dey and K. Balasubramanian. Construction of some families of group divisible designs. Utilitas Mathematica, 40:283–290, 1991.
  6. A. Dey and A. Nigam. Construction of group divisible designs. Journal of the Indian Society of Agricultural Statistics, 37:163–166, 1985.
  7. G. Ge and Y. Miao. Pbds, frames, and resolvability. In Handbook of Combinatorial Designs, pages 287–291. Chapman and Hall/CRC, 2006.
  8. S. Kageyama. Resolvability of block designs. The Annals of Statistics:655–661, 1976.
  9. C. K. Midha and A. Dey. Cyclic group divisible designs. Calcutta Statistical Association Bulletin, 45(3-4):253–258, 1995. https://doi.org/10.1177/0008068319950311.
  1. R. Mukerjee, M. Jimbo, and S. Kageyama. On cyclic semiregular group divisible designs. Osaka Journal of Mathematics, 24:395–407, 1987.
  2. J. Pieprzyk and X.-M. Zhang. Ideal threshold schemes from orthogonal arrays. In Information and Communications Security: 4th International Conference, ICICS 2002 Singapore, December 9–12, 2002 Proceedings 4, pages 469–479. Springer, 2002. https://doi.org/10.1007/3-540-36159-6_40.
  3. S. Saurabh. A note on cyclic and partial cyclic solutions of block designs. Gujrat Journal of Statistics and Data Science, 40:45–50, 2024.
  4. S. Saurabh. Resolvability of a bib design of takeuchi (1962). Statistics and Applications, 22(2):361–362, 2024.
  5. S. Saurabh. Some matrix constructions of non-symmetric regular group divisible designs. Bulletin of the ICA, 102:129–146, 2024.
  6. S. Saurabh and K. Sinha. Perfect secret sharing schemes from combinatorial squares. Security and Privacy, 5(6):e262, 2022. https://doi.org/10.1002/spy2.262.
  7. S. Saurabh and K. Sinha. Some matrix constructions of l2-type latin square designs. Bulletin of the ICA, 95:93–104, 2022.
  8. S. Saurabh and K. Sinha. Matrix approaches to constructions of group divisible designs. Bulletin of the ICA, 97:83–105, 2023.
  9. S. Saurabh, K. Sinha, et al. (2,w)-threshold schemes constructed from orthogonal resolutions. Journal of Combinatorial Mathematics and Combinatorial Computing, 120:231–239, 2024. https://doi.org/10.61091/jcmcc120-20.
  1. M. K. Singh and S. Saurabh. On certain classes of rectangular designs. Calcutta Statistical Association Bulletin, 75(1):72–96, 2023. https://doi.org/10.1177/00080683231162746.
  2. D. R. Stinson. Cryptography: Theory and Practice. Chapman and Hall/CRC, 2005.
  3. D. R. Stinson and S. A. Vanstone. A combinatorial approach to threshold schemes. SIAM Journal on Discrete Mathematics, 1(2):230–236, 1988. https://doi.org/10.1137/0401024.