On security of GIS systems with N-tier architecture and family of graph based ciphers
DOI:
https://doi.org/10.32347/2411-4049.2023.3.113-132Keywords:
Stream ciphers, GIS protection, Multivariare Cryptography, Graph Based Cipher, graphs given by equations, regular tree approximationsAbstract
Discovery of q-regular tree description in terms of an infinite system of quadratic equations over finite field Fq had an impact on Computer Science, theory of graph based cryptographic algorithms in particular. It stimulates the development of new graph based stream ciphers. It turns out that such encryption instruments can be efficiently used in GIS protection systems which use N-Tier Architecture. We observe known encryption algorithms based on the approximations of regular tree, their modifications defined over arithmetical rings and implementations of these ciphers. Additionally new more secure graph based ciphers suitable for GIS protection will be presented.
Algorithms are constructed using vertices of bipartite regular graphs D(n,K) defined by a finite commutative ring K with a unit and a non-trivial multiplicative group K*. The partition of such graphs are n-dimensional affine spaces over the ring K. A walk of even length determines the transformation of the transition from the initial to the last vertex from one of the partitions of the graph. Therefore, the affine space Kn can be considered as a space of plaintexts, and walking on the graph is a password that defines the encryption transformation.
With certain restrictions on the password the effect when different passwords with K*)2s, s <[(n+5)/2]/2 correspond to different ciphertexts of the selected plaintext with Kn can be achieved.
In 2005, such an algorithm in the case of the finite field F127 was implemented for the GIS protection. Since then, the properties of encryption algorithms using D(n, K) graphs (execution speed, mixing properties, degree and density of the polynomial encryption transform) have been thoroughly investigated.
The complexity of linearization attacks was evaluated and modifications of these algorithms with the resistance to linearization attacks were found. It turned out that together with D(n, K) graphs, other algebraic graphs with similar properties, such as A(n, K) graphs, can be effectively used.
The article considers several solutions to the problem of protecting the geological information system from possible cyberattacks using stream ciphers based on graphs. They have significant advantages compared to the implemented earlier systems.
References
S. Dhanjal, Y. Khmelevsky, M. Govorov, V. A. Ustymenko, P. N. Sharma, Security solutions for spatial data in storage - (Implementation case within oracle 9iAS), 8th World MultiConference on Systemics, Cybernetics and Informatics, Vol Ii, Proceedings, pp. 318–323, 2004.
M. Govorov, Y. Khmelevsky, V. Ustimenko, A. Khorev, Security for GIS N-tier architecture, Developments in Spatial Data Handling, pp. 71–83, 2005.
Y. Khmelevsky, S. Dhanjal, Information Security and Data Protection in Computer Science Education, in 12th Western Canadian Conference Education on Computing Education (WCCCE-2007), Thompson Rivers University, Kamloops, Canada, May, 2007, pp. 3–5.
V. Ustimenko, CRYPTIM: Graphs as tools for symmetric encryption, in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2227, 2001.
F. Lazebnik, V. Ustimenko (1993). Some Algebraic Constractions of Dense Graphs of Large Girth and of Large Size, DIMACS series in Discrete Mathematics and Theoretical Computer Science, 10, p. 75-93. https://doi.org/10.1090/dimacs/010/07
Lazebnik F., Ustimenko V. A. and Woldar A. J. (1995). New Series of Dense Graphs of High Girth // Bull (New Series) of AMS, 32, No. 1, p. 73-79. https://doi.org/10.1090/S0273-0979-1995-00569-0
V. Ustimenko, On graph-based cryptography and symbolic computations, Serdica Journal of Computing, vol. 1, no. 2, pp. 131–156, 2007.
Aneta Wroblewska, On some properties of graph based public keys, Albanian Journal of Mathematics, Albanian J. Math. 2(3), 229-234, (2008).
J. S. Kotorowicz and V. A. Ustimenko, On the implementation of cryptoalgorithms based on algebraic graphs over some commutative rings, in Condensed Matter Physics, vol. 11, no. 2, 2008.
V. Ustimenko (1998), Coordinatisation of Trees and their Quotients, in the Voronoj's Impact on Modern Science, Kiev, Institute of Mathematics, 2, p. 125-152.
V. Ustimenko (2007). Linguistic Dynamical Systems, Graphs of Large Girth and Cryptography, Journal of Mathematical Sciences, Springer, 140, No. 3, p. 412-434. https://doi.org/10.1007/s10958-007-0453-2
V. A. Ustimenko, U. Romanczuk, On Dynamical Systems of Large Girth or Cycle Indicator and their applications to Multivariate Cryptography, in "Artificial Intelligence, Evolutionary Computing and Metaheuristics", In the footsteps of Alan Turing Series: Studies in Computational Intelligence, 427, 2012, p. 231-256, https:/doi.org/10.1007/978-3-642-29694-9_10
V. A. Ustimenko, U. Romanczuk, On Extremal Graph Theory, Explicit Algebraic Constructions of Extremal Graphs and Corresponding Turing Encryption Machines, in "Artificial Intelligence, Evolutionary Computing and Metaheuristics", In the footsteps of Alan Turing Series: Studies in Computational Intelligence, Vol. 427, Springer, January, 2013, 257-285.
F. Lazebnik, V. Ustimenko and A. J. Woldar (1996). A characterisation of the components of the graphs D(k,q), Discrete Mathematics, 157, p. 271-283. https://doi.org/10.1016/S0012-365X(96)83019-6
V. А. Ustimenko. On the extremal graph theory and symbolic computations, Dopovidi National Academy of Sci, Ukraine, 2013, No. 2, p. 42-49.
V. Ustimenko, On new results on extremal graph theory, theory of algebraic graphs, and their applications, Reports of National Acad. of Sci. of Ukraine, 2022, N4, pp. 25-32.
V. Ustimenko, Maximality of affine group, hidden graph cryptosystem and graph's stream ciphers, Journal of Algebra and Discrete Mathematics, 2005, v. 1, pp. 51-65.
G. Margulis (1988). Explicit group-theoretical constructions of combinatorial schemes and their application to design of expanders and concentrators, Probl. Peredachi Informatsii, 24, No. 1, p. 51-60.
A. Lubotsky, R. Philips, P. Sarnak (1989). Ramanujan graphs, J. Comb. Theory, 115, No. 2, p. 62-89. https://doi.org/10.1007/BF02126799
T. Shaska, V. Ustimenko (2009). On the homogeneous algebraic graphs of large girth and their applications, Linear Algebra and its Applications, 430, No. 7, p. 1826-1837. https://doi.org/10.1016/j.laa.2008.08.023
F. Buekenhout (editor), Handbook in Incidence Geometry, Ch. 9, North Holland, Amsterdam, 1995.
V. Ustimenko (1989). Affine system of roots and Tits geometries, Voprosy teorii grupp i gomologicheskoy algebry, Yaroslavl, p. 155-157.
M. Polak, V. A. Ustimenko (2012). On LDPC Codes Corresponding to Infinite Family of Graphs A(k,K). Proceedings of the Federated Conference on Computer Science and Information Systems (FedCSIS), CANA, Wroclaw, p. 11-23.
Ustimenko, V. (2021). On semigroups of multivariate transformations constructed in terms of time dependent linguistic graphs and solutions of Post Quantum Multivariate Cryptography. Cryptology ePrint Archive: Report 2021/1466. Retrieved from https://eprint.iacr.org/2021/1466.pdf
D. MacKay and M. Postol (2003). Weakness of Margulis and Ramanujan - Margulis Low Dencity Parity Check Codes, Electronic Notes in Theoretical Computer Science, 74, p. 97-104. https:/doi.org/10.1016/S1571-0661(04)80768-0
V. Ustimenko (2009). Algebraic groups and small world graphs of high girth, Albanian Journal of Mathematics, 3, No. 1, p. 25-33.
V. Ustimenko, On Extremal Algebraic Graphs and Multivariate Cryptosystems, Cryptology ePrint Archive, reprint 2022/1537.
V. Ustimenko, On the extremal graph theory for directed graphs and its cryptographical applications. In: T. Shaska, W.C. Huffman, D. Joener and V. Ustimenko, Advances in Coding Theory and Cryptography, Series on Coding and Cryptology, vol. 3, 181-200 (2007).
V. Ustimenko, Graphs in terms of Algebraic Geometry, symbolic computations and secure communications in Post-Quantum world, Editorial House of University of Maria Curie – Sklodowska, Lublin, November, 2022, 196 pages.
Geetha N K, Ragavi V, Graph Theory Matrix Approach in Cryptography and Network Security, Proceedings of 2022 Algorithms, Computing and Mathematics Conference (ACM), 29-30 Aug. 2022, https://ieeexplore.ieee.org/document/10202460
Costache, A., Feigon, B., Lauter, K., Massierer, M., Puskás, A. (2019). Ramanujan Graphs in Cryptography. In: Balakrishnan, J., Folsom, A., Lalín, M., Manes, M. (eds) Research Directions in Number Theory. Association for Women in Mathematics Series, vol. 19. Springer, Cham. https://doi.org/10.1007/978-3-030-19478-9_1
P.L. K. Priyadarsini, A Survey on some Applications of Graph Theory in Cryptography, Journal of Discrete Mathematical Sciences and Cryptography, https://www.tandfonline.com/doi/abs/10.1080/09720529.2013.878819
W. M. Al Etaiwi, Encryption Algorithm Using Graph Theory, Journal of Scientific Research & Reports, 3(19): 2519-2527, 2014; Article no. JSRR.2014.19.004.
Samid Gideon, Denial Cryptography based on Graph Theory, US patent 6823068-2004 http://www.patentstorm.us/patents/6823068.html
Lothrop Mittenthal, Sequencings and Directed Graphs with Applications to Cryptography, S.W. Golomb et al. (Eds.): Springer-Varlag LNCS 4893, pp. 70–81, 2007.
Moni Naor and Adi Shamir. Visual cryptography. In Advances in Cryptology - EURO-CRYPT'94, LNCS, vol. 950, pp. 1–12, 1994.
Steve Lu, Daniel Manchala, Rafail Ostrovsky, Visual Cryptography on Graphs, COCOON 2008: pp. 225–234, 2008.
William Stallings, Cryptography and Network Security Principles and Practices, Prentice Hall India, 2006.
Dawn Song, David Zuckermany, J. D. Tygar, Expander Graphs for Digital Stream Authentication and Robust Overlay Networks, Proceedings of the 2002 IEEE Symposium on Security and Privacy (S&P.02), 2002.
M Yamuna, Meenal Gogia, Ashish Sikka and Md. Jazib Hayat Khan, "Encryption using graph theory and linear algebra", International Journal of Computer Application, pp. 2250-1797, 2012.
A Paszkiewicz et al., Proposals of graph based ciphers theory and implementations. Research Gate, 2001.
Cusack, B.; Chapman, E. Using graphic methods to challenge cryptographic performance. In Proceedings of the 14th Australian Information Security Management Conference, Edith Cowan University, Perth, Australia, 5–6 December 2016; pp. 30–36. [Google Scholar].
Chapman, E. Using Graphic Based Systems to Improve Cryptographic Algorithms. Ph.D. Thesis, Auckland University of Technology, Auckland, New Zealand, 2016. [Google Scholar].
Kinani, E.H.E. Fast Mapping Method based on Matrix Approach For Elliptic Curve Cryptography. Int. J. Inf. Netw. Secur. (IJINS) 2012, 1, 54–59.
M. Klisowski. Zwiększenie bezpieczeństwa kryptograficznych algorytmów wielu zmiennych bazujących na algebraicznej teorii grafów. Rozprawa doktorska, Politechnika Częstochowska, Częstochowa, 2014.
Vasyl Ustimenko, Aneta Wroblewska, On the key exchange and multivariate encryption with nonlinear polynomial maps of stable degree, Annales of UMCS, Informatica, Vol 13, No 1 (2013), pp 63-80. http://dx.doi.org/10.2478/v10065-012-0047-6
Pustovit O.S. Application of the theory of extreme graphs to modern problems of information security. - Dissertation for obtaining the scientific degree of candidate of technical sciences in the specialty 05.13.06 - Information technologies. – Institute of Telecommunications and Global Information Space of the National Academy of Sciences of Ukraine, Kyiv, 2021.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2023 Ustimenko V.O., Pustovit O.S.
This work is licensed under a Creative Commons Attribution 4.0 International License.
The journal «Environmental safety and natural resources» works under Creative Commons Attribution 4.0 International (CC BY 4.0).
The licensing policy is compatible with the overwhelming majority of open access and archiving policies.
