American Institute of Mathematical Sciences

doi: 10.3934/amc.2021054
Online First

Online First articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Online First articles via the “Online First” tab for the selected journal.

Splitting authentication codes with perfect secrecy: New results, constructions and connections with algebraic manipulation detection codes

 1 Department of Economics, Mathematics and Statistics, Birkbeck, University of London, Malet St, London WC1E 7HX, UK 2 David R. Cheriton School of Computer Science, University of Waterloo, Waterloo, Ontario, N2L 3G1, Canada

* Corresponding author: Maura B. Paterson

Received  April 2021 Revised  August 2021 Early access November 2021

Fund Project: The second author is supported by NSERC discovery grant RGPIN-03882

A splitting BIBD is a type of combinatorial design that can be used to construct splitting authentication codes with good properties. In this paper we show that a design-theoretic approach is useful in the analysis of more general splitting authentication codes. Motivated by the study of algebraic manipulation detection (AMD) codes, we define the concept of a group generated splitting authentication code. We show that all group-generated authentication codes have perfect secrecy, which allows us to demonstrate that algebraic manipulation detection codes can be considered to be a special case of an authentication code with perfect secrecy.

We also investigate splitting BIBDs that can be "equitably ordered". These splitting BIBDs yield authentication codes with splitting that also have perfect secrecy. We show that, while group generated BIBDs are inherently equitably ordered, the concept is applicable to more general splitting BIBDs. For various pairs $(k, c)$, we determine necessary and sufficient (or almost sufficient) conditions for the existence of $(v, k \times c, 1)$-splitting BIBDs that can be equitably ordered. The pairs for which we can solve this problem are $(k, c) = (3, 2), (4, 2), (3, 3)$ and $(3, 4)$, as well as all cases with $k = 2$.

Citation: Maura B. Paterson, Douglas R. Stinson. Splitting authentication codes with perfect secrecy: New results, constructions and connections with algebraic manipulation detection codes. Advances in Mathematics of Communications, doi: 10.3934/amc.2021054
References:
 [1] C. Blundo, A. De Santis, K. Kurosawa and W. Ogata, On a fallacious bound for authentication codes, J. Cryptol., 12 (1999), 155-159.  doi: 10.1007/s001459900049. [2] F. C. Bowditch and P. J. Dukes., Local balance in graph decompositions, preprint, arXiv: 2002.08895. [3] A. Brouwer, A. Schrijver and H. Hanani, Group divisible designs with block-size four, Discrete Math., 20 (1977), 1-10.  doi: 10.1016/0012-365X(77)90037-1. [4] C. J. Colbourn and J. H. Dinitz, Handbook of Combinatorial Designs, Second Edition (Discrete Mathematics and Its Applications), Chapman and Hall/CRC, 2007. [5] C. J. Colbourn, D. G. Hoffman and R. Rees, A new class of group divisible designs with block size three, J. Combin. Theory, Series A, 59 (1992), 73-89.  doi: 10.1016/0097-3165(92)90099-G. [6] R. Cramer, Y. Dodis, S. Fehr, C. Padró and D. Wichs, Detection of algebraic manipulation with applications to robust secret sharing and fuzzy extractors, in EUROCRYPT '08 (ed. N. P. Smart), vol. 4965 of LNCS, Springer, 2008,471-488. doi: 10.1007/978-3-540-78967-3_27. [7] G. Ge and A. C. Ling, Group divisible designs with block size four and group type $g^um^1$ for small $g$, Discrete Math., 285 (2004), 97-120.  doi: 10.1016/j.disc.2004.04.003. [8] G. Ge, Y. Miao and L. Wang, Combinatorial constructions for optimal splitting authentication codes, SIAM J. Discrete Math., 18 (2005), 663-678.  doi: 10.1137/S0895480103435469. [9] M. Huber, Information Theoretic Authentication and Secrecy Codes in the Splitting Model, in 22nd International Zurich Seminar on Communications (IZS), Eidgenössische Technische Hochschule Zürich, 2012. [10] W. Ogata, K. Kurosawa, D. R. Stinson and H. Saido, New combinatorial designs and their applications to authentication codes and secret sharing schemes, Discrete Math., 279 (2004), 383-405, In Honour of Zhu Lie. doi: 10.1016/S0012-365X(03)00283-8. [11] M. B. Paterson and D. R. Stinson, Combinatorial characterizations of algebraic manipulation detection codes involving generalized difference families, Discrete Math., 339 (2016), 2891-2906.  doi: 10.1016/j.disc.2016.06.004. [12] M. B. Paterson and D. R. Stinson, On the equivalence of authentication codes and robust (2, 2)-threshold schemes, J. Math. Cryptol., 15 (2021), 179-196.  doi: 10.1515/jmc-2019-0048. [13] G. J. Simmons, Authentication theory/coding theory, in CRYPTO '84 (eds. G. R. Blakley and D. Chaum), vol. 196 of LNCS, Springer, 1984, 411-431. [14] M. D. Soete, New bounds and constructions for authentication/secrecy codes with splitting, J. Cryptol., 3 (1991), 173-186.  doi: 10.1007/BF00196910. [15] D. R. Stinson, The combinatorics of authentication and secrecy codes, J. Cryptol., 2 (1990), 23-49.  doi: 10.1007/BF02252868. [16] D. R. Stinson, Some constructions and bounds for authentication codes, J. Cryptol., 1 (1988), 37-51.  doi: 10.1007/BF00206324. [17] J. Wang, A new class of optimal 3-splitting authentication codes, Des. Codes, Cryptogr., 38 (2006), 373-381.  doi: 10.1007/s10623-005-1501-x. [18] J. Wang and R. Su, Further results on the existence of splitting BIBDs and application to authentication codes, Acta Appl. Math., 109 (2010), 791-803.  doi: 10.1007/s10440-008-9346-8.

show all references

References:
 [1] C. Blundo, A. De Santis, K. Kurosawa and W. Ogata, On a fallacious bound for authentication codes, J. Cryptol., 12 (1999), 155-159.  doi: 10.1007/s001459900049. [2] F. C. Bowditch and P. J. Dukes., Local balance in graph decompositions, preprint, arXiv: 2002.08895. [3] A. Brouwer, A. Schrijver and H. Hanani, Group divisible designs with block-size four, Discrete Math., 20 (1977), 1-10.  doi: 10.1016/0012-365X(77)90037-1. [4] C. J. Colbourn and J. H. Dinitz, Handbook of Combinatorial Designs, Second Edition (Discrete Mathematics and Its Applications), Chapman and Hall/CRC, 2007. [5] C. J. Colbourn, D. G. Hoffman and R. Rees, A new class of group divisible designs with block size three, J. Combin. Theory, Series A, 59 (1992), 73-89.  doi: 10.1016/0097-3165(92)90099-G. [6] R. Cramer, Y. Dodis, S. Fehr, C. Padró and D. Wichs, Detection of algebraic manipulation with applications to robust secret sharing and fuzzy extractors, in EUROCRYPT '08 (ed. N. P. Smart), vol. 4965 of LNCS, Springer, 2008,471-488. doi: 10.1007/978-3-540-78967-3_27. [7] G. Ge and A. C. Ling, Group divisible designs with block size four and group type $g^um^1$ for small $g$, Discrete Math., 285 (2004), 97-120.  doi: 10.1016/j.disc.2004.04.003. [8] G. Ge, Y. Miao and L. Wang, Combinatorial constructions for optimal splitting authentication codes, SIAM J. Discrete Math., 18 (2005), 663-678.  doi: 10.1137/S0895480103435469. [9] M. Huber, Information Theoretic Authentication and Secrecy Codes in the Splitting Model, in 22nd International Zurich Seminar on Communications (IZS), Eidgenössische Technische Hochschule Zürich, 2012. [10] W. Ogata, K. Kurosawa, D. R. Stinson and H. Saido, New combinatorial designs and their applications to authentication codes and secret sharing schemes, Discrete Math., 279 (2004), 383-405, In Honour of Zhu Lie. doi: 10.1016/S0012-365X(03)00283-8. [11] M. B. Paterson and D. R. Stinson, Combinatorial characterizations of algebraic manipulation detection codes involving generalized difference families, Discrete Math., 339 (2016), 2891-2906.  doi: 10.1016/j.disc.2016.06.004. [12] M. B. Paterson and D. R. Stinson, On the equivalence of authentication codes and robust (2, 2)-threshold schemes, J. Math. Cryptol., 15 (2021), 179-196.  doi: 10.1515/jmc-2019-0048. [13] G. J. Simmons, Authentication theory/coding theory, in CRYPTO '84 (eds. G. R. Blakley and D. Chaum), vol. 196 of LNCS, Springer, 1984, 411-431. [14] M. D. Soete, New bounds and constructions for authentication/secrecy codes with splitting, J. Cryptol., 3 (1991), 173-186.  doi: 10.1007/BF00196910. [15] D. R. Stinson, The combinatorics of authentication and secrecy codes, J. Cryptol., 2 (1990), 23-49.  doi: 10.1007/BF02252868. [16] D. R. Stinson, Some constructions and bounds for authentication codes, J. Cryptol., 1 (1988), 37-51.  doi: 10.1007/BF00206324. [17] J. Wang, A new class of optimal 3-splitting authentication codes, Des. Codes, Cryptogr., 38 (2006), 373-381.  doi: 10.1007/s10623-005-1501-x. [18] J. Wang and R. Su, Further results on the existence of splitting BIBDs and application to authentication codes, Acta Appl. Math., 109 (2010), 791-803.  doi: 10.1007/s10440-008-9346-8.
$P\in X_{B^Q, s_j}^\sigma$ when $Q\in X_{s_j}^{\Delta_P}$
 [1] Yeow Meng Chee, Xiande Zhang, Hui Zhang. Infinite families of optimal splitting authentication codes secure against spoofing attacks of higher order. Advances in Mathematics of Communications, 2011, 5 (1) : 59-68. doi: 10.3934/amc.2011.5.59 [2] M. B. Paterson, D. R. Stinson, R. Wei. Combinatorial batch codes. Advances in Mathematics of Communications, 2009, 3 (1) : 13-27. doi: 10.3934/amc.2009.3.13 [3] JiYoon Jung, Carl Mummert, Elizabeth Niese, Michael Schroeder. On erasure combinatorial batch codes. Advances in Mathematics of Communications, 2018, 12 (1) : 49-65. doi: 10.3934/amc.2018003 [4] Olof Heden. A survey of perfect codes. Advances in Mathematics of Communications, 2008, 2 (2) : 223-247. doi: 10.3934/amc.2008.2.223 [5] Luciano Panek, Jerry Anderson Pinheiro, Marcelo Muniz Alves, Marcelo Firer. On perfect poset codes. Advances in Mathematics of Communications, 2020, 14 (3) : 477-489. doi: 10.3934/amc.2020061 [6] Richard A. Brualdi, Kathleen P. Kiernan, Seth A. Meyer, Michael W. Schroeder. Combinatorial batch codes and transversal matroids. Advances in Mathematics of Communications, 2010, 4 (3) : 419-431. doi: 10.3934/amc.2010.4.419 [7] Olof Heden. The partial order of perfect codes associated to a perfect code. Advances in Mathematics of Communications, 2007, 1 (4) : 399-412. doi: 10.3934/amc.2007.1.399 [8] Claude Carlet, Juan Carlos Ku-Cauich, Horacio Tapia-Recillas. Bent functions on a Galois ring and systematic authentication codes. Advances in Mathematics of Communications, 2012, 6 (2) : 249-258. doi: 10.3934/amc.2012.6.249 [9] Yunwen Liu, Longjiang Qu, Chao Li. New constructions of systematic authentication codes from three classes of cyclic codes. Advances in Mathematics of Communications, 2018, 12 (1) : 1-16. doi: 10.3934/amc.2018001 [10] Yuebo Shen, Dongdong Jia, Gengsheng Zhang. The results on optimal values of some combinatorial batch codes. Advances in Mathematics of Communications, 2018, 12 (4) : 681-690. doi: 10.3934/amc.2018040 [11] Cuiling Fan, Koji Momihara. Unified combinatorial constructions of optimal optical orthogonal codes. Advances in Mathematics of Communications, 2014, 8 (1) : 53-66. doi: 10.3934/amc.2014.8.53 [12] Srimanta Bhattacharya, Sushmita Ruj, Bimal Roy. Combinatorial batch codes: A lower bound and optimal constructions. Advances in Mathematics of Communications, 2012, 6 (2) : 165-174. doi: 10.3934/amc.2012.6.165 [13] Markku Lehtinen, Baylie Damtie, Petteri Piiroinen, Mikko Orispää. Perfect and almost perfect pulse compression codes for range spread radar targets. Inverse Problems and Imaging, 2009, 3 (3) : 465-486. doi: 10.3934/ipi.2009.3.465 [14] B. K. Dass, Namita Sharma, Rashmi Verma. Characterization of extended Hamming and Golay codes as perfect codes in poset block spaces. Advances in Mathematics of Communications, 2018, 12 (4) : 629-639. doi: 10.3934/amc.2018037 [15] Olof Heden, Fabio Pasticci, Thomas Westerbäck. On the existence of extended perfect binary codes with trivial symmetry group. Advances in Mathematics of Communications, 2009, 3 (3) : 295-309. doi: 10.3934/amc.2009.3.295 [16] Olof Heden, Denis S. Krotov. On the structure of non-full-rank perfect $q$-ary codes. Advances in Mathematics of Communications, 2011, 5 (2) : 149-156. doi: 10.3934/amc.2011.5.149 [17] Helena Rifà-Pous, Josep Rifà, Lorena Ronquillo. $\mathbb{Z}_2\mathbb{Z}_4$-additive perfect codes in Steganography. Advances in Mathematics of Communications, 2011, 5 (3) : 425-433. doi: 10.3934/amc.2011.5.425 [18] Xiang Wang, Wenjuan Yin. New nonexistence results on perfect permutation codes under the hamming metric. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021058 [19] Stefka Bouyuklieva, Zlatko Varbanov. Some connections between self-dual codes, combinatorial designs and secret sharing schemes. Advances in Mathematics of Communications, 2011, 5 (2) : 191-198. doi: 10.3934/amc.2011.5.191 [20] Olof Heden, Fabio Pasticci, Thomas Westerbäck. On the symmetry group of extended perfect binary codes of length $n+1$ and rank $n-\log(n+1)+2$. Advances in Mathematics of Communications, 2012, 6 (2) : 121-130. doi: 10.3934/amc.2012.6.121

2020 Impact Factor: 0.935