A novel application on mutually orthogonal graph squares and graph-orthogonal arrays

A. El-Mesady; Y. S. Hamed; Khadijah M. Abualnaja; A. El-Mesady; Y. S. Hamed; Khadijah M. Abualnaja

doi:10.3934/math.2022410

AIMS Mathematics

2022, Volume 7, Issue 5: 7349-7373. doi: 10.3934/math.2022410

Previous Article Next Article

Research article

A novel application on mutually orthogonal graph squares and graph-orthogonal arrays

1.
Department of Physics and Engineering Mathematics, Faculty of Electronic Engineering, Menoufia University, Menouf 32952, Egypt
2.
Department of Mathematics and Statistics, College of Science, Taif University, P.O. Box 11099, Taif 21944, Saudi Arabia

Received: 01 November 2021 Revised: 21 December 2022 Accepted: 23 December 2021 Published: 10 February 2022
MSC : 05B30, 05C70, 94A60, 94A62

Security of personal information has become a major concern due to the increasing use of the Internet by individuals in the digital world. The main purpose here is to prevent an unauthorized person from gaining access to confidential information. The solution to such a problem is by authentication of users. Authentication has a very important role in achieving security. Mutually orthogonal graph squares (MOGS) are considered the generalization of mutually orthogonal Latin squares (MOLS). Also, MOGS are generated from edge decompositions of complete bipartite graphs by isomorphic graphs. Graph-orthogonal arrays can be constructed by MOGS. In this paper, graph-orthogonal arrays are used for constructing authentication codes. These arrays are the encoding matrices of authentication tags. We introduce the concepts and basic theorems of MOGS, graph-orthogonal arrays, and authentication codes. After constructing graph-orthogonal arrays by MOGS, then there is an established mapping between graph-orthogonal arrays and message set. This manages us to construct perfect non-splitting and splitting Cartesian authentication codes. In both cases, we calculate the probabilities of successful impersonation attacks and substitution attacks. Besides that, the performance of constructed non-splitting and splitting authentication codes is analyzed. In the end, optimal authentication codes and secure authentication codes are constructed.
- Latin squares,
- graph squares,
- graph-orthogonal arrays,
- Cartesian authentication codes,
- non-splitting authentication codes,
- splitting authentication codes,
- optimal authentication codes
Citation: A. El-Mesady, Y. S. Hamed, Khadijah M. Abualnaja. A novel application on mutually orthogonal graph squares and graph-orthogonal arrays[J]. AIMS Mathematics, 2022, 7(5): 7349-7373. doi: 10.3934/math.2022410

Related Papers:

Abstract

Security of personal information has become a major concern due to the increasing use of the Internet by individuals in the digital world. The main purpose here is to prevent an unauthorized person from gaining access to confidential information. The solution to such a problem is by authentication of users. Authentication has a very important role in achieving security. Mutually orthogonal graph squares (MOGS) are considered the generalization of mutually orthogonal Latin squares (MOLS). Also, MOGS are generated from edge decompositions of complete bipartite graphs by isomorphic graphs. Graph-orthogonal arrays can be constructed by MOGS. In this paper, graph-orthogonal arrays are used for constructing authentication codes. These arrays are the encoding matrices of authentication tags. We introduce the concepts and basic theorems of MOGS, graph-orthogonal arrays, and authentication codes. After constructing graph-orthogonal arrays by MOGS, then there is an established mapping between graph-orthogonal arrays and message set. This manages us to construct perfect non-splitting and splitting Cartesian authentication codes. In both cases, we calculate the probabilities of successful impersonation attacks and substitution attacks. Besides that, the performance of constructed non-splitting and splitting authentication codes is analyzed. In the end, optimal authentication codes and secure authentication codes are constructed.

References

[1]	C. Shannon, A mathematical theory of communication, Bell System Technical Journal, 27 (1948), 379–423. https://doi.org/10.1002/j.1538-7305.1948.tb01338.x doi: 10.1002/j.1538-7305.1948.tb01338.x
[2]	E. Gilbert, F. MacWilliams, N. Sloane, Codes which detect deception, Bell System Technical Journal, 53 (1974), 405–424. https://doi.org/10.1002/j.1538-7305.1974.tb02751.x doi: 10.1002/j.1538-7305.1974.tb02751.x
[3]	G. Simmons, A game theory model of digital message authentication, Congressus Neumerantium, 34 (1982), 413–424.
[4]	G. Simmons, Message authentication: a game on hypergraphs, Congressus Neumerantium, 45 (1984), 161–192.
[5]	G. Simmons, Authentication theory / coding theory, In: Lecture Notes in Computer Science, Berlin: Springer, 1985,411–431. https://doi.org/10.1007/3-540-39568-7_32
[6]	G. Simmons, A survey of information authentication. Proceedings of the IEEE, 1992,379–419. https://doi.org/10.1109/5.4445
[7]	T. Sze, S. Chanson, C. Ding, T. Helleseth, M. Parker, Logarithm Cartesian authentication codes, Inform. Comput., 184 (2003), 93–108. https://doi.org/10.1016/S0890-5401(03)00053-1 doi: 10.1016/S0890-5401(03)00053-1
[8]	H. Wang, C. Xing, R. Safavi-Naini, Linear authentication codes: bounds and constructions, IEEE T. Inform. Theory, 49 (2003), 866–872. https://doi.org/10.1109/TIT.2003.809567 doi: 10.1109/TIT.2003.809567
[9]	R. Feng, L. Hu, J. Kwak, Authentication codes and bipartite graph, Eur. J. Combin., 29 (2008), 1473–1482. https://doi.org/10.1016/j.ejc.2007.06.013 doi: 10.1016/j.ejc.2007.06.013
[10]	S. Chen, D. Zhao, Two constructions of optimal Cartesian authentication codes from unitary geometry over finite fields, Acta Math. Appl. Sin. Engl. Ser., 29 (2013), 829–836. https://doi.org/10.1007/s10255-013-0259-6 doi: 10.1007/s10255-013-0259-6
[11]	R. Feng, Another construction of Cartesian authentication codes from geometry of classical groups, Northeast Math. J., 15 (1999), 103–114.
[12]	R. Feng, Z. Wan, A construction of Cartesian authentication codes from geometry of classical groups, J. Comb. Inf. Syst. Sci., 20 (1995), 197–210.
[13]	S. Gao, Two constructions of Cartesian authentication codes from unitary geometry, Appl. Math. J. Chinese Univ. Ser. A., 11 (1996), 343–354.
[14]	Y. Gao, Z. Zou, Two new constructions of Cartesian authentication codes from symplectic geometry, Appl. Math., 10 (1995), 345–356. https://doi.org/10.1007/BF02662876 doi: 10.1007/BF02662876
[15]	H. You, Y. Gao, Some new constructions of Cartesian authentication codes from symplectic geometry, J. Syst. Sci. Complex., 7 (1994), 317–327.
[16]	Z. Li, S. Gao, Z. Wang, B. Thuraisingham, W. Wu, A construction of Cartesian authentication code from orthogonal spaces over a finite field of odd characteristic, Discret. Math. Algorit., 1 (2009), 105–114. https://doi.org/10.1142/S1793830909000075 doi: 10.1142/S1793830909000075
[17]	J. Ma, J. Guo, F. Li, K. Wang, A generalization of the formulas for intersection numbers of dual polar association schemes and their applications, Linear Algebra Appl., 434 (2011), 1272–1284. https://doi.org/10.1016/j.laa.2010.11.007 doi: 10.1016/j.laa.2010.11.007
[18]	L. Casse, K. Martin, P. Wild, Bounds and characterizations of authentication / secrecy schemes, Des. Codes Cryptogr., 13 (1998), 107–129. https://doi.org/10.1023/A:1008270111149 doi: 10.1023/A:1008270111149
[19]	C. Ding, A. Salomaa, P. Solé, X. Tian, Three constructions of authentication/secrecy codes, J. Pure Appl. Algebra, 196 (2005), 149–168. https://doi.org/10.1016/j.jpaa.2004.08.008 doi: 10.1016/j.jpaa.2004.08.008
[20]	G. Ge, L. Zhu, Authentication perpendicular arrays APA1 (2, 5, v), J. Comb. Des., 4 (1996), 365–375. https://doi.org/10.1002/(SICI)1520-6610(1996)4:5%3C365::AID-JCD5%3E3.0.CO;2-D doi: 10.1002/(SICI)1520-6610(1996)4:5%3C365::AID-JCD5%3E3.0.CO;2-D
[21]	G. Ge, L. Zhu, Authentication perpendicular arrays APA1 (2, 7, v), J. Comb. Des., 5 (1997), 111–124. https://doi.org/10.1002/(SICI)1520-6610(1997)5:2%3C111::AID-JCD3%3E3.0.CO;2-I doi: 10.1002/(SICI)1520-6610(1997)5:2%3C111::AID-JCD3%3E3.0.CO;2-I
[22]	D. Stinson, Some constructions and bounds for authentication codes, J. Cryptology, 1 (1988), 37–51. https://doi.org/10.1007/BF00206324 doi: 10.1007/BF00206324
[23]	D. Stinson, A construction for authentication/secrecy codes from certain combinatorial designs, In: Lecture Notes in Computer Science, Berlin: Springer, 1988,119–127. https://doi.org/10.1007/3-540-48184-2_31
[24]	D. Stinson, The combinatorics of authentication and secrecy codes, J. Cryptology, 2 (1990), 23–49. https://doi.org/10.1007/BF02252868 doi: 10.1007/BF02252868
[25]	D. Stinson, L. Teirlink, A construction for authentication/secrecy codes from 3-homogeneous permutation groups, Eur. J. Combin., 11 (1990), 73–79. https://doi.org/10.1016/S0195-6698(13)80058-3 doi: 10.1016/S0195-6698(13)80058-3
[26]	T. Van Tran, On the construction of authentication and secrecy codes, Des. Codes Crypt., 5 (1995), 269–280. https://doi.org/10.1007/BF01388389 doi: 10.1007/BF01388389
[27]	M. De Soete, New bounds and constructions for authentication/secrecy codes with splitting, J. Cryptology, 3 (1991), 173–186. https://doi.org/10.1007/BF00196910 doi: 10.1007/BF00196910
[28]	W. Ogata, K. Kurowawa, D. Stinson, H. Saido, New combinatorial designs and their applications to authentication codes and secret sharing schemes, Discrete Math., 279 (2004), 383–405. https://doi.org/10.1016/S0012-365X(03)00283-8 doi: 10.1016/S0012-365X(03)00283-8
[29]	J. Massey, Cryptography–a selective survey, In: Digital Communications, North-Holland: Elsevier Science Publisher, 1985, 4–11.
[30]	R. Rees, D. Stinson, Combinatorial characterizations of authentication codes II, Des. Codes Crypt., 7 (1996), 239–259. https://doi.org/10.1023/A:1018094824862 doi: 10.1023/A:1018094824862
[31]	T. Bolton, T. Dargahi, S. Belguith, M. Al-Rakhami, A. Sodhro, On the security and privacy challenges of virtual assistants, Sensors, 21 (2021), 2312. https://doi.org/10.3390/s21072312 doi: 10.3390/s21072312
[32]	C. Nykvist, M. Larsson, A. Sodhro, A. Gurtov, A lightweight portable intrusion detection communication system for auditing applications, Int. J. Commun. Syst., 33 (2020), 4327. https://doi.org/10.1002/dac.4327 doi: 10.1002/dac.4327
[33]	S. Bakhtiari, R. Safavi-Naini, J. Pieprzyk, A message authentication code based on latin squares, In: Lecture Notes in Computer Science, Berlin: Springer, 1997. https://doi.org/10.1007/BFb0027926
[34]	D. Stinson, Combinatorial characterizations of authentication codes, Des. Codes Crypt., 2 (1992), 175–187. https://doi.org/10.1007/BF00124896 doi: 10.1007/BF00124896
[35]	S. Pal, D. Bhardwaj, R. Kumar, V. Bhatia, A new cryptographic Hash function based on Latin squares and non-linear transformations, Proceeding of 2009 IEEE International Advance Computing Conference, 2009,862–867. https://doi.org/10.1109/IADCC.2009.4809128 doi: 10.1109/IADCC.2009.4809128
[36]	S. Golomb, E. Posner, Rook domains, Latin squares, affine planes, and error-distributing codes, IEEE T. Inform. Theory, 10 (1964), 196–208. https://doi.org/10.1109/TIT.1964.1053680 doi: 10.1109/TIT.1964.1053680
[37]	R. El-Shanawany, A. El-Mesady, Mutually orthogonal graph squares for disjoint union of stars, Ars Combinatoria, 149 (2020), 83–91.
[38]	R. Sampathkumar, S. Srinivasan, Mutually orthogonal graph squares, J. Comb. Des., 17 (2009), 369–373. https://doi.org/10.1002/jcd.20216 doi: 10.1002/jcd.20216
[39]	R. El-Shanawany, A. El-Mesady, On mutually orthogonal certain graph squares, Online J. Anal. Comb, 14 (2020), 1–20.
[40]	M. Higazy, A. El-Mesady, M. Mohamed, On graph-orthogonal arrays by mutually orthogonal graph squares, Symmetry, 12 (2020), 1895. https://doi.org/10.3390/sym12111895 doi: 10.3390/sym12111895
[41]	A. El-Mesady, S. Shaaban, Generalization of MacNeish's Kronecker product theorem of mutually orthogonal, AKCE Int. J. Graphs Co., 18 (2021), 117–122. https://doi.org/10.1080/09728600.2021.1966349 doi: 10.1080/09728600.2021.1966349
[42]	R. El-Shanawany, On mutually orthogonal graph-path squares, Open Journal of Discrete Mathematics, 6 (2016), 7–12. https://doi.org/10.4236/ojdm.2016.61002 doi: 10.4236/ojdm.2016.61002
[43]	R. El-Shanawany, A. El-Mesady, S. Shaaban, Mutually orthogonal graph squares for disjoint union of paths, Applied Mathematical Sciences, 12 (2018), 303–310. https://doi.org/10.12988/ams.2018.8112 doi: 10.12988/ams.2018.8112
[44]	R. El-Shanawany, On mutually orthogonal disjoint copies of graph squares, Note Mat., 36 (2016), 89–98.
[45]	M. Higazy, λ-Mutually orthogonal covers of complete bipartite graphs, Adv. Appl. Discret. Mat., 17 (2016), 151–167. https://doi.org/10.17654/DM017020151 doi: 10.17654/DM017020151
[46]	Z. Wan, Design theory. Beijing: Higher Education Press, 2009.
[47]	J. Liu, Z. Xu, On the Theory and Construction of CARTESIAN Authentication Codes, J. Electron. Inf. Techn., 30 (2008), 93–95. https://doi.org/10.3724/SP.J.1146.2006.00838 doi: 10.3724/SP.J.1146.2006.00838
[48]	W. Jirakitpuwapat, P. Chaipunya, P. Kumam, S. Dhompongsa, P. Thounthong, New methods of construction of Cartesian authentication codes from geometries over finite commutative rings, J. Math. Cryptol., 12 (2018), 119–136. https://doi.org/10.1515/jmc-2017-0057 doi: 10.1515/jmc-2017-0057

Reader Comments

Your name:*

Email:*
© 2022 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)