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. BlundoA. De SantisK. Kurosawa and W. Ogata, On a fallacious bound for authentication codes, J. Cryptol., 12 (1999), 155-159.  doi: 10.1007/s001459900049.  Google Scholar

[2]

F. C. Bowditch and P. J. Dukes., Local balance in graph decompositions, preprint, arXiv: 2002.08895. Google Scholar

[3]

A. BrouwerA. 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.  Google Scholar

[4]

C. J. Colbourn and J. H. Dinitz, Handbook of Combinatorial Designs, Second Edition (Discrete Mathematics and Its Applications), Chapman and Hall/CRC, 2007.  Google Scholar

[5]

C. J. ColbournD. 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[8]

G. GeY. Miao and L. Wang, Combinatorial constructions for optimal splitting authentication codes, SIAM J. Discrete Math., 18 (2005), 663-678.  doi: 10.1137/S0895480103435469.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[14]

M. D. Soete, New bounds and constructions for authentication/secrecy codes with splitting, J. Cryptol., 3 (1991), 173-186.  doi: 10.1007/BF00196910.  Google Scholar

[15]

D. R. Stinson, The combinatorics of authentication and secrecy codes, J. Cryptol., 2 (1990), 23-49.  doi: 10.1007/BF02252868.  Google Scholar

[16]

D. R. Stinson, Some constructions and bounds for authentication codes, J. Cryptol., 1 (1988), 37-51.  doi: 10.1007/BF00206324.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

show all references

References:
[1]

C. BlundoA. De SantisK. Kurosawa and W. Ogata, On a fallacious bound for authentication codes, J. Cryptol., 12 (1999), 155-159.  doi: 10.1007/s001459900049.  Google Scholar

[2]

F. C. Bowditch and P. J. Dukes., Local balance in graph decompositions, preprint, arXiv: 2002.08895. Google Scholar

[3]

A. BrouwerA. 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.  Google Scholar

[4]

C. J. Colbourn and J. H. Dinitz, Handbook of Combinatorial Designs, Second Edition (Discrete Mathematics and Its Applications), Chapman and Hall/CRC, 2007.  Google Scholar

[5]

C. J. ColbournD. 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[8]

G. GeY. Miao and L. Wang, Combinatorial constructions for optimal splitting authentication codes, SIAM J. Discrete Math., 18 (2005), 663-678.  doi: 10.1137/S0895480103435469.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[14]

M. D. Soete, New bounds and constructions for authentication/secrecy codes with splitting, J. Cryptol., 3 (1991), 173-186.  doi: 10.1007/BF00196910.  Google Scholar

[15]

D. R. Stinson, The combinatorics of authentication and secrecy codes, J. Cryptol., 2 (1990), 23-49.  doi: 10.1007/BF02252868.  Google Scholar

[16]

D. R. Stinson, Some constructions and bounds for authentication codes, J. Cryptol., 1 (1988), 37-51.  doi: 10.1007/BF00206324.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

Figure 1.  $ 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 & 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]

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

[19]

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

[20]

Ettore Fornasini, Telma Pinho, Raquel Pinto, Paula Rocha. Composition codes. Advances in Mathematics of Communications, 2016, 10 (1) : 163-177. doi: 10.3934/amc.2016.10.163

2020 Impact Factor: 0.935

Metrics

  • PDF downloads (28)
  • HTML views (24)
  • Cited by (0)

Other articles
by authors

[Back to Top]