\((2,w)\)-Threshold Schemes Constructed from Orthogonal Resolutions

1. Introduction

A holey or partial resolution class is a collection of blocks such that every element of \(\mathcal{V\backslash}G\), \(G \in \mathcal{G}\) occurs exactly once and the elements of \(G\) do not occur where \(\mathcal{G}\) is a set of \('m'\) groups each of size \(n\) of the GD design. A uniform \((k,\lambda) -\)frame of type \(n^{m}\) and index \(\lambda\) is a GD design with parameters: \(v = mn,b,r,k\), \(\lambda_{1} = 0,\) \(\lambda_{2} = \lambda\) such that

1. The block set \(\mathcal{B}\) can be partitioned into a family \(\mathcal{R:\ }R_{1},R_{2},\ldots,R_{m}\) of partial resolution classes;

2. Each \(R_{i}\mathcal{\in R}\) can be associated with a group \(G \in \mathcal{G}\) so that \(R_{i}(1 \leq i \leq m)\) contains every element of \(\mathcal{V\backslash}G\) exactly once.

A triangular association scheme is an arrangement of \(v = \frac{n(n – 1)}{2}\) elements in an \(n \times n\) array such that the positions on the principal diagonal are left blank, the \(\frac{n(n – 1)}{2}\) positions above and below the principal diagonal are filled with the \(v\) elements in such a way that the resultant arrangement is symmetric about the principal diagonal. Then any two elements which occur in the same row or same column are first associates; otherwise, they are second associates. A partially balanced incomplete block (PBIB) design based on triangular association scheme is called a triangular design.

The integers \(v = \frac{n(n – 1)}{2},b,r,k,\lambda_{1}\)and \(\lambda_{2}\) are known as parameters of the triangular design and they satisfy the relations: \(bk = vr;2(n – 2)\lambda_{1} + \frac{(n – 2)(n – 3)}{2}\lambda_{2} = r(k – 1).\)

An \((r,\lambda) -\)design is a collection \(\mathcal{B}\) of subsets (blocks) from a finite set \(V\) of elements such that every element of \(V\) is contained in \(r\) blocks of \(\mathcal{B}\) and every pair of distinct elements is contained in exactly \(\lambda\) blocks.

Suppose \(b\) blocks of a block design \(D(v,b,r,k)\) can be divided into \(t\ ( = \frac{r}{\mu})\) classes, each of size \(\beta = \frac{\nu\mu}{k}\) such that in each class of \(\beta\) blocks every element of D is replicated \(\mu\) times. Then these \(t\) classes are known as \(\mu -\)resolution (or parallel) classes and the design is called \(\mu -\)resolvable design [11]. When \(\mu = 1\) the design is said to be resolvable and the classes are called resolution classes.

Any two resolutions \(R = R_{1},R_{2},\ldots,R_{r}\) and \(S = S_{1},S_{2},\ldots,S_{r}\) of a resolvable block design\(\ D(v,b,r,k)\) are orthogonal if \(\left| R_{i}\bigcap_{}^{}S_{j} \right| \leq 1,\ 1 \leq i,j \leq r\). Further \(D(v,b,r,k)\) is doubly resolvable if it has a pair of orthogonal resolutions. It should be noted that the blocks of the design are considered as labeled so that repeated blocks are treated as distinct. We write \(m -\) MORs if \(D(v,b,r,k)\) has a set of \(m\) mutually orthogonal resolutions.

Corresponding to a doubly resolvable design: \(D(v,b,r,k)\), an \(r \times r\) array \(A = {(A_{\text{ij}})}_{1 \leq i,j \leq r} = R_{i}\bigcap_{}^{}S_{j};R_{i} \in R,S_{j} \in S\) can be formed such that the rows are indexed by the elements of \(R\) and columns by the elements of \(S\). Hence any cell of \(A\) will either be empty or contain a block of \(D\). Clearly \(A\) is row–wise as well as column–wise resolvable.

If the \(r \times r\) array \(A\) is based on a \((v,\ 2,\ 1) -\)BIBD, then it is known as a Room square or Kirkman square \(\text{KS}_{2}(v;1,1)\) of side \(v – 1\) otherwise it is called a generalized Room square. Further when a doubly resolvable design is based on \(\mu -\)resolvable BIBD, it is called doubly \(\mu -\) resolvable and the corresponding \(t \times t\ (t = \frac{r}{\mu})\) array based on it is known as a Kirkman square, \(\text{KS}_{k}(v;\mu,\lambda)\) Stinson [12] and Abel et al. [13].

A \((v,\ k,\ \lambda) -\)BIBD is said to be near resolvable if its blocks can be partitioned into \('v'\) near or holey resolvable classes: \(R_{1},R_{2},\ldots,R_{v}\) such that such that for each element \(x\) of the design there is precisely one class which does not contain \(x\) in any of its blocks and each class contains \(v – 1\) distinct elements of the design. If \(D\) has a pair of near orthogonal resolutions then the design is known as doubly near resolvable, \(\text{DNR}(v,\ k,\ \lambda) -\)BIBD [14].

Corresponding to a \(\text{DNR}(v,\ k,\ \lambda) -\)BIBD, a \(v \times v\) array \(A = {(A_{\text{ij}})}_{1 \leq i,j \leq v} = R_{i}\bigcap_{}^{}S_{j};R_{i} \in R,S_{j} \in S\) can be formed such that the rows are indexed by the elements of \(R\) and columns by the elements of \(S\) where \(R = R_{1},R_{2},\ldots,R_{v}\) and \(S = S_{1},S_{2},\ldots,S_{v}\) are near orthogonal resolutions of the design. Hence any cell of \(A\) will either be empty or contain a block of the design. Clearly \(A\) is row–wise as well as column–wise near resolvable. We write \(m -\)MNORs if a \((v,\ k,\ \lambda) -\) BIBD has a set of \(m\) mutually near orthogonal resolutions.

Let \(\mathcal{K}\) be a finite key space and \(P\) be a finite set of participants. In a secret sharing scheme, a special participant \(D \notin P\), called the dealer, secretly chooses a key \(K \in \mathcal{K}\) 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,\ w) -\)threshold scheme is a secret sharing scheme in which if any \(t( \leq w)\) or more participants pool their shares, where \(w = |P|\), then they can reconstruct the secret key \(K \in \mathcal{K}\), but any \(t – 1\) 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 \(w = 3\) and \(t = 2\), op. cit. Stinson and Vanstone [15], Stinson [16].

2. \(\left( {2,w} \right){-}\)threshold Schemes from Orthogonal Resolutions

Mutually orthogonal resolutions (\(m\)-MORs) of certain series of \((v, k, \lambda)\)-BIBDs can be found in the works of Mathon and Vanstone [17], Abel et al. [13], and Topalova and Zhelezova [18-20]. Additionally, MORs of GD designs and \((r, \lambda)\)-designs are discussed by Fuji-Hara and Vanstone [21], Vanstone [22], Lamken and Vanstone [23,24], Chang and Miao [25], and Dong and Wang [26]. Some key existence theorems on orthogonal resolutions are presented below:

Vanstone [29] also constructed a \((31, 3, 2)\)-BIBD with seven MNORs; \((29, 4, 3)\)-, \((19, 3, 2)\)-, and \((37, 3, 2)\)-BIBDs with five MNORs.

A 2-MOR of an \((n + 1, 2, 1)\)-BIBD is equivalent to a Room square of side \(n\), see Topalova and Zhelezova [19]. Chaudhry et al. [30] used the critical set of a Room square of side \(n\) or equivalently orthogonal resolutions of an \((n + 1, 2, 1)\)-BIBD in constructing perfect secret sharing schemes, while Saurabh and Sinha [31] used critical sets of group divisible Room squares for the same purpose. Pieprzyk and Zhang [32] derived ideal \((t, w)\)-threshold schemes from a \(b^{t} \times (n + 1)\) orthogonal array \(OA(b^{t}, n + 1, b, t)\) by considering \(OA(i, j)\) as the shares of participants \(P_{j}\) (where \(1 \leq j \leq n\)) and \(OA(i, 0)\) as a secret key (where \(1 \leq i \leq b^{t}\)), with \(OA(i, j)\) denoting the entry in the \(i\)th row and \(j\)th column of \(OA(b^{t}, n + 1, b, t)\). Stinson and Vanstone [15] obtained perfect threshold schemes from Steiner systems \(S(t, w, v)\). Adachi and Lu [33] constructed \((3, 3)\)-threshold schemes from magic cubes by considering the magic cube as a secret key and the corresponding three cubes as the shadows.

Although various secret sharing schemes exist in the literature, more schemes are desirable from the perspectives of secrecy and security. It is suggested to consider each of the \(w\) resolutions of a block design as shares and a combination of any two orthogonal resolutions or the corresponding Room square as a secret key of a \((2, w)\)-threshold scheme. By considering \(w\)-MORs or \(w\)-MNORs of \((v, k, \lambda)\)-BIBDs, GD designs, \((r, \lambda)\)-designs, triangular designs, or any combinatorial designs and 2-MORs of frames, we may obtain \((2, w)\)-threshold schemes. Tables 3-5 present \((2, w)\)-threshold schemes derived from some combinatorial designs.

Abbreviations

\(p\) is a prime or prime power, FV stands for Fuji-Hara and Vanstone [21], and LV stands for Lamken and Vanstone, [28].

Given below are examples of mutually orthogonal resolutions of GD and triangular designs:

3. Conclusion

Here, a brief survey on mutually orthogonal resolutions of some combinatorial designs is presented and some \((2,w) -\)threshold schemes are obtained from these mutually orthogonal resolutions. Two orthogonal resolutions have been used to coordinatize a two–dimensional square, called Room square however we could use \(t -\)MORs to coordinatize a \(t -\)dimensional hypercube. These \(t -\)MORs can also be used in secret sharing schemes. When \(t = 3,k = 2,\lambda = 1\), a set of 3\(-\)MORs is commonly called a Room cube of side \(v – 1\) based on \(D\) [29, 35]. Further considering each resolution as a share and a secret as Room cube obtained from 3\(-\)MORs of a block design, we can obtain \((3,w) -\)threshold schemes. Some constructions and existence results of some other doubly resolvable combinatorial designs namely \(H -\)designs and Canonical Kirkman packing designs can be found in Meng [36], Wang [10] and Meng et al. [37]. The orthogonal resolutions of these designs can also be used to obtain (2, 2) –threshold schemes. Some examples of doubly near resolvable designs which are not frames can be found in Lamken and Vanstone [28] and Abel et al. [13].

An example of a doubly 3–resolvable BIBD is given below which is duplicate of an unreduced BIBD. It seems that there is a possibility of presenting a construction rule of a doubly \(\mu -\)resolvable BIBD with parameters: \(v,\ b = 2\left( \frac{v}{k} \right),r = 2\left( \frac{v – 1}{k – 1} \right),k,\lambda = 2\left( \frac{v – 2}{k – 2} \right);\mu = k,\) obtained by the duplicate of an unreduced BIBD with parameters: \(v,\ b = \left( \frac{v}{k} \right),r = \left( \frac{v – 1}{k – 1} \right),k,\lambda = \left( \frac{v – 2}{k – 2} \right)\), provided that \(v\) divides \(b\).

Conflict of Interest

The authors declare no conflict of interest.