Top

Designs, Codes and Cryptography

Published in:

22-06-2023

Covering schemes of strength t

Authors: André Guerino Castoldi, Anderson Novaes Martinhão, Emerson L. Monte Carmelo, Otávio J. N. T. N. dos Santos

Published in: Designs, Codes and Cryptography | Issue 11/2023

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

This work brings together several types of combinatorial designs: difference matrices, difference covering arrays and difference schemes by defining the concept of covering scheme of strength t over an abelian additive group. Connections of covering schemes with orthogonal arrays and covering arrays are also established. We show general results of covering schemes of strength t using a method based on the factorization of a group and some refinements for particular classes. We apply the previous results to investigate covering schemes having three, four and five factors. Finally, a reformulation of covering schemes in terms of graph theory is established.

previous article Sok: vector OLE-based zero-knowledge protocols

next article Improved attacks against reduced-round Whirlwind

Abel R.J.R., Combe D., Palmer W.D.: Generalized Bhaskar Rao designs and dihedral groups. J. Comb. Theory Ser. A 106(1), 145–157 (2004).MathSciNetCrossRefMATH

Bose R.C., Bush K.A.: Orthogonal arrays of strength two and three. Ann. Math. Stat. 23(4), 508–524 (1952).MathSciNetCrossRefMATH

Buratti M.: Recursive constructions for difference matrices and relative difference families. J. Comb. Des. 6(3), 165–182 (1998).MathSciNetCrossRefMATH

Castoldi A.G., Martinhão A.N., Monte Carmelo E.L., dos Santos O.J.N.T.N.: Invariant codes, constructions of difference schemes, and distributive quasigroups. Comput. Appl. Math. 41, 370 (2022).

Chateauneuf M., Kreher D.L.: On the state of strength-three covering arrays. J. Comb. Des. 10(4), 217–238 (2002).MathSciNetCrossRefMATH

Colbourn C.J.: Combinatorial aspects of covering arrays. Matematiche 59(1,2), 125–172 (2004).MathSciNetMATH

Colbourn C.J., Dinitz J.H.: Handbook of Combinatorial Designs. Chapman and Hall, Boca Raton (2006).CrossRefMATH

Colbourn C.J., Lanus E., Sarkar K.: Asymptotic and constructive methods for covering perfect hash families and covering arrays. Des. Codes Cryptogr. 86, 907–937 (2018).MathSciNetCrossRefMATH

Demirkale F., Donovan D., Hall J., Khodkar A., Rao A.: Difference covering arrays and pseudo-orthogonal latin squares. Graphs Comb. 32(4), 1353–1374 (2016).MathSciNetCrossRefMATH

10.

Garey M., Johnson D.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, New York (1979).MATH

11.

Ge G.: On \((g, 4; 1)\)-difference matrices. Discret. Math. 301(2), 164–174 (2005).CrossRefMATH

12.

Hedayat A.S., Pu K., Stufken J.: On the construction of asymmetrical orthogonal arrays. Ann. Stat. 2142–2152 (1992).

13.

Hedayat A.S., Sloane N.J.A., Stufken J.: Orthogonal Arrays: Theory and Applications. Springer, New York (2012).MATH

14.

Hedayat A.S., Stufken J., Su G.: On difference schemes and orthogonal arrays of strength \(t\). J. Stat. Plann. Inference 56(2), 307–324 (1996).MathSciNetCrossRefMATH

15.

Jungnickel D.: On difference matrices and regular latin squares. Abh. Math. Semin. Univ. Hambg. 50(2), 219–231 (1980).MathSciNetCrossRefMATH

16.

Pan R., Abel R.J.R., Bunjamin Y.A., Feng T., Tsang Ung T.J., Wang X.: Difference matrices with five rows over finite abelian groups. Des. Codes Cryptogr. 90, 1–20 (2022).MathSciNetCrossRefMATH

17.

Paige L.J.: A note on finite abelian groups. Bull. Am. Math. Soc. 53(6), 590–593 (1947).MathSciNetCrossRefMATH

18.

Pan R., Chang Y.: \((m, n, 3, 1)\) optical orthogonal signature pattern codes with maximum possible size. IEEE Trans. Inf. Theory 61(2), 1139–1148 (2014).MathSciNetCrossRefMATH

19.

Pan R., Chang Y.: A note on difference matrices over non-cyclic finite abelian groups. Discret. Math. 339(2), 822–830 (2016).MathSciNetCrossRefMATH

20.

Rotman J.J.: Advanced Modern Algebra. Prentice Hall, New York (2002).MATH

21.

Seiden E.: On the problem of construction of orthogonal arrays. Ann. Math. Stat. 25(1), 151–156 (1954).MathSciNetCrossRefMATH

22.

Seiden E., Zemach R.: On orthogonal arrays. Ann. Math. Stat. 1355–1370 (1966).

23.

Torres-Jimenez J., Izquierdo-Marquez I.: Survey of covering arrays. In: 2013 15th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, pp. 20–27 (2013).

24.

Yin J.: Constructions of difference covering arrays. J. Comb. Theory Ser. A 104(2), 327–339 (2003).MathSciNetCrossRefMATH

25.

Yin J.: Cyclic difference packing and covering arrays. Des. Codes Cryptogr. 37(2), 281–292 (2005).MathSciNetCrossRefMATH

26.

Zhang M., Feng T., Wang X.: A note on a pair of orthogonal orthomorphisms of cyclic groups. Discret. Math. 346, 113–122 (2023).MathSciNetCrossRef

Title: Covering schemes of strength t
Authors: André Guerino Castoldi
Anderson Novaes Martinhão
Emerson L. Monte Carmelo
Otávio J. N. T. N. dos Santos
Publication date: 22-06-2023
Publisher: Springer US
Published in: Designs, Codes and Cryptography / Issue 11/2023
Print ISSN: 0925-1022
Electronic ISSN: 1573-7586
DOI: https://doi.org/10.1007/s10623-023-01252-2

Springer Professional

Covering schemes of strength t

Abstract

Premium Partner

Springer Professional

Abstract

Please log in to get access to your license.

Other articles of this Issue 11/2023

Constructions of column-orthogonal strong orthogonal arrays via matchings of bipartite graphs

Ligero: lightweight sublinear arguments without a trusted setup

Sok: vector OLE-based zero-knowledge protocols

Guest editorial: Special issue on Mathematics of Zero-Knowledge

Generalized attack on ECDSA: known bits in arbitrary positions

Plane curves giving rise to blocking sets over finite fields

Premium Partner