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

Maura B. Paterson; Douglas R. Stinson

doi:10.3934/amc.2021054

Article Contents

2021, Volume 0. Doi: 10.3934/amc.2021054

Previous Article Next Article

Early Access

Early Access 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). Early Access publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Early Access articles via the “Early Access” tab for the selected journal.

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

Maura B. Paterson^1, , and
Douglas R. Stinson^2,

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
^* Corresponding author: Maura B. Paterson

Received: March 31, 2021

Revised: July 31, 2021

Early access: November 2021

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

Abstract Full Text(HTML) Figure(1) Related Papers Cited by

Abstract

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 $.

Keywords:

Mathematics Subject Classification: Primary: 05B05; 05B10; 94A62.

Citation:

FullText(HTML)

Figure 1. $ P\in X_{B^Q, s_j}^\sigma $ when $ Q\in X_{s_j}^{\Delta_P} $

Download: Full-size image PowerPoint slide

Related Papers

Cited by

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.