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

2023, Volume 17, Issue 6: 1364-1387. Doi: 10.3934/amc.2021054

This issue Previous Article Security analysis of public key encryption with filtered equality test Next Article A proof of the conjectured run time of the Hafner-McCurley class group algorithm

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: April 2021

Revised: August 2021

Early access: November 2021

Published: December 2023

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

Abstract / Introduction 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:

Full Text(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.