Search

In this paper, we observe simple yet subtle interconnections among design theory, coding theory and cryptography. Maximum distance separable (MDS) matrices have applications not only in coding theory but are also of great importance in the design of block ciphers and hash functions. It is nontrivial to find MDS matrices which could be used in lightweight cryptography. In the SAC 2004 paper [12], Junod and Vaudenay considered bi-regular matrices which are useful objects to build MDS matrices. Bi-regular matrices are those matrices all of whose entries are nonzero and all of whose 2 × 2 {2\times 2} submatrices are nonsingular. Therefore MDS matrices are bi-regular matrices, but the converse is not true. They proposed the constructions of efficient MDS matrices by studying the two major aspects of a d × d {d\times d} bi-regular matrix M, namely v 1 ⁢ ( M ) {v_{1}(M)} , i.e. the number of occurrences of 1 in M, and c 1 ⁢ ( M ) {c_{1}(M)} , i.e. the number of distinct elements in M other than 1. They calculated the maximum number of ones that can occur in a d × d {d\times d} bi-regular matrices, i.e. v 1 d , d {v_{1}^{d,d}} for d up to 8, but with their approach, finding v 1 d , d {v_{1}^{d,d}} for d ≥ 9 {d\geq 9} seems difficult. In this paper, we explore the connection between the maximum number of ones in bi-regular matrices and the incidence matrices of Balanced Incomplete Block Design (BIBD). In this paper, tools are developed to compute v 1 d , d {v_{1}^{d,d}} for arbitrary d. Using these results, we construct a restrictive version of d × d {d\times d} bi-regular matrices, introducing by calling almost-bi-regular matrices, having v 1 d , d {v_{1}^{d,d}} ones for d ≤ 21 {d\leq 21} . Since, the number of ones in any d × d {d\times d} MDS matrix cannot exceed the maximum number of ones in a d × d {d\times d} bi-regular matrix, our results provide an upper bound on the number of ones in any d × d {d\times d} MDS matrix. We observe an interesting connection between Latin squares and bi-regular matrices and study the conditions under which a Latin square becomes a bi-regular matrix and finally construct MDS matrices from Latin squares. Also a lower bound of c 1 ⁢ ( M ) {c_{1}(M)} is computed for d × d {d\times d} bi-regular matrices M such that v 1 ⁢ ( M ) = v 1 d , d {v_{1}(M)=v_{1}^{d,d}} , where d = q 2 + q + 1 {d=q^{2}+q+1} and q is any prime power. Finally, d × d {d\times d} efficient MDS matrices are constructed for d up to 8 from bi-regular matrices having maximum number of ones and minimum number of other distinct elements for lightweight applications.

In this paper we study (4,[email protected])-GDDs of type g^n possessing both the pan-decomposable property introduced by Granville, Moisiadis, Rees, On complementary decompositions of the complete graph, Graphs and Combinatorics 5 (1989) 57-61 and the pan-orientable property introduced by Gruttmuller, Hartmann, Pan-orientable block designs, Australas. J. Combin. 40 (2008) 57-68. We show that the necessary condition for a (4,[email protected])-GDD satisfying both of these properties, namely (1) n>=4, @mg(n-1)=0 (mod 3), and (2) g-1,n are not both even if @m is odd are sufficient. When @l=2, our designs are super-simple. We also determine the spectrum of (4,2)-GDDs which are super-simple and possess some of the decomposable/orientable conditions, but are not pan-decomposable or pan-orientable. In particular, we show that the necessary conditions for a super-simple directable (4,2)-GDD of type g^n are sufficient.

We give some constructions of new infinite families of group divisible designs, GDD(n,2,4;λ1,λ2), including one which uses the existence of Bhaskar Rao designs. We show the necessary conditions are sufficient for 3⩽n⩽8. For n=10 there is one missing critical design. If λ1>λ2, then the necessary conditions are sufficient for n≡4,5,8(mod12). For each of n=10,15,16,17,18,19, and 20 we indicate a small minimal set of critical designs which, if they exist, would allow construction of all possible designs for that n. The indices of each of these designs are also among those critical indices for every n in the same congruence class mod12.

Under the right conditions it is possible for the ordered blocks of a path design PATH(v,k,μ) to be considered as unordered blocks and thereby create a BIBD(v,k,λ). We call this a tight embedding. We show here that, for any triple system TS(v,3), there is always such an embedding and that the problem is equivalent to the existence of a (-1)-BRD(v,3,3), i.e., a c-Bhaskar Rao Design. That is, we also prove the incidence matrix of any triple system TS(v,3) can always be signed to create a (-1)-BRD(v,3,3) and, moreover, the signing determines a natural partition of the blocks of the triple system making it a nested design.

A Steiner pentagon system of order v (SPS(v)) is said to be super-simple if its underlying (v,5,2)-BIBD is super-simple; that is, any two blocks of the BIBD intersect in at most two points. In this paper, it is shown that the necessary condition for the existence of a super-simple SPS(v); namely, v⩾5 and v≡1 or 5(mod10) is sufficient, except for v=5, 15 and possibly for v=25. In the process, we also improve an earlier result for the spectrum of super-simple (v,5,2)-BIBDs, removing all the possible exceptions. We also give some new examples of Steiner pentagon packing and covering designs (SPPDs and SPCDs).

We show the necessary conditions are sufficient for the existence of GDD(n,2,4; λ1, λ2) with two groups and block size four in which every block intersects each group exactly twice (even GDD's) or in which every block intersects each group in one or three points (odd GDD's). We give a construction for near 3-resolvable triple systems TS(n,3,6) for every n⩾4, and these are used to provide constructions for several families of GDDs.

We solve the existence problem for generalized Bhaskar Rao designs of block size 3 for an infinite family of non-abelian groups, the dihedral groups Dn, of order 2n. In our main result we show that for n ≥ 1 and v ≥ 3 the following set of conditions is necessary and sufficient for the existence of a GBRD(v, 3, λ Dn): 1. λ ≡ 0 (mod 2n): 2. λ v(v - 1) ≡ 0 (mod 24).

This paper introduces three new types of combinatorial designs, which we call external difference families (EDF), external BIBDs (EBIBD) and splitting BIBDs. An EDF is a special type of EBIBD, so existence of an EDF implies existence of an EBIBD. We construct optimal splitting A-codes by using EDF. Then we give a new bound on the number of shares required in robust secret sharing schemes (i.e., schemes secure against cheaters). EDF can be used to construct robust secret sharing schemes that are optimal with respect to the new bound. We also prove a weak converse, showing that if there exists an optimal secret sharing scheme, then there exists an EBIBD. Finally, we derive a Fisher-type inequality for splitting BIBDs. We also prove a weak equivalence between splitting BIBDs and splitting A-codes. Further, it is shown that an EDF implies a splitting BIBD.

The necessary conditions for the existence of a balanced incomplete block design on v points, with index λ and block size k, are that λ(v−1)≡0 mod (k−1), λv(v−1)≡0 mod k(k−1) . In this paper we study k=9 with λ=3, 6 and 12. We show that these conditions on v are sufficient, with the possible exceptions of v=177, 345, 385 when λ=3, and v=213 when λ=6. We give constructions of TD3(10,n)s with 13 possible exceptions, namely n∈{5,6,14,20,35,45,55,56,60,78,84,85,102}; we also reduce the number of unknown TDs with block sizes 8 and 9.

New constructions of Bhaskar Rao designs (BRDs) and new families of c-BRDs are given using the relationship of BRDs to other combinatorial structures. For example, we use different families and their properties in various ways to obtain natural signings of BIBDs in order to construct c-BRDs. We investigate the extreme possibilities for c relative to λ, and k relative to v, and prove the non-existence of an infinite series of designs. We also give a symmetricized version of Ehlich's Hadamard construction.

A Bhaskar Rao design, i.e., a BRD(v,k,λ), is formed by signing the v by b incidence matrix of a BIBD(v,k,λ) so that the inner product of any two distinct rows is 0. It is proved in the literature that such designs exist for k=4 with 28 possible exceptions. In this paper, we show that a BRD is equivalent to a special kind of group divisible design (GDD). By using the knowledge of GDDs, we resolve the open cases of BRD(v,4,λ) and complete the spectrum problem on their existence.

An enclosing of BIBD(v,3,λ) into BIBD(v+s,3,λ+1) is point-wise minimal if s is the smallest positive integer for which an enclosing is possible. We show that the necessary conditions are sufficient for a minimal point-enclosing of any BIBD(v,3,λ) into BIBD(v+s,3,λ+1) for 1⩽λ⩽6. Some other general results on enclosings are presented.

In this article we resolve some of the open problems left in two other articles. A c-Bhaskar Rao design, i.e., a c-BRD(v,k,λ), is formed by signing the υ by b incidence matrix of a BIBD(v, k, λ) so that the inner product of any two distinct rows is c. We complete Greig, Hurd, McCranie and Sarvate's work on the spectrum of c-BRD(v, 4, λ) when c ≠ 0. In the classic (i.e., c = 0) case, we establish the existence of 0-BRD(3t + 1, 4, 2) for all 3t + 1 ≥ 433, with at most 30 smaller exceptions, all with t odd. Morgan, Preece and Rees have given a list of nested BIBDs with v ≤ 16 and r ≤ 30; they have one open case. By reformulating this problem, and constructing a (-1)-BRD(16,10, 9), we provide a solution for this open case.

Three methods of constructions of efficient block designs for symmetric parallel line assays have been proposed. These methods are based on balanced incomplete block design (BIBD). Through these designs, all contrasts of interest can be estimated free from block effect and with high efficiency. Any BIB design for which v, the number treatments is strictly greater than twice of block size can be converted into a design that can be used for conducting a symmetric parallel line assay. All methods of construction are demonstrated with some examples.

This paper presents a way of using the natural evolution process as a model for combinatorial design constructions. In spite of the fact that metaheuristic proved its efficiency on a variety of problems, there are only a few known cases of implementing it on combinatorial designs. The genetic algorithm developed here was able to construct BIBDs by searching through the natural solution space without any additional constraints. Among all the obtained positive results, new simple designs with parameters 2-(14, 4, 6) and 2-(18, 4, 6) should be pointed out.

An examination of three well-known composition techniques allows to get some new information about the number of non-isomorphic BIBDs with suitable parameters.

In statistical planning of experiments, super-simple designs are the ones providing samples with maximum intersection as small as possible. Super-simple designs are also useful in other constructions, such as superimposed codes and perfect hash families etc. The existence of super-simple (v,4,λ)-BIBDs have been determined for λ=2,3,4 and 6. When λ=5, the necessary conditions of such a design are that v≡1,4(mod12) and v≥13. In this paper, we show that there exists a super-simple (v,4,5)-BIBD for each v≡1,4(mod12) and v≥13.

We show the necessary conditions are sufficient for the existence of group divisible designs (or PBIBDs) with block size k=3 with three groups of size (n,2,1) for any n≥2 and any two indices with λ1>λ2.

A new method of construction of affine resolvable balanced incomplete block design from a given affine resolvable balanced incomplete block design is given.