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-132Ключові слова:
Stream ciphers, GIS protection, Multivariare Cryptography, Graph Based Cipher, graphs given by equations, regular tree approximationsАнотація
Відкриття опису q-регулярного дерева в термінах нескінченної системи квадратних рівнянь над скінченним полем Fq мало вплив на розвиток Інформатики, зокрема теорії криптографічних алгоритмів, що визначаються за графами. Це стимулювало розвиток конструкцій безпечних потокових алгоритмів шифрування. Виявилося, що такі інструменти шифрування можна ефективно використовувати в системах захисту ГІС, що вживають N-рівневу архітектуру. Ми оглянемо відомі алгоритми шифрування, засновані на aпроксимаціях регулярних дерев, їх модифікації, визначені над арифметичними кільцями, та програмні реалізації цих алгоритмів. Крім того, будуть представлені нові більш безпечні алгоритми потокового шифрування, придатні для захисту ГІС.
Алгоритми будуються з використанням блукань на вершинах дводольних регулярних графів D(n,K), визначених за скінченним комутативним кільцем К з одиницею та нетривіальною мультиплікативною групою К*. Долі таких графів є n-вимірними афінними просторами над кільцем К. Блукання парної довжини визначає перетворення переходу від початкової до останньої вершини з однієї з долей графу. Отже, афінний простір Kn можна розглядати як простір відкритих текстів, а блукання на графі паролем, який визначає перетворення, що шифрує.
При певних обмеженнях на паролі досягається ефект, коли різним паролям з (K*)2s, s <[(n+5)/2]/2 відповідають різні шифрограми обраного відкритого тексту з Kn. У 2005 році такий алгоритм у випадку скінченного поля F127 використовувaвся для захисту ГІС. З цього часу властивості алгоритмів шифрування з використанням графів D(n, K) (швидкодія, властивості зміни, степінь та густина поліноміального перетворення шифрування) були ретельно досліджені. Було оцінено складність атак лінеаризації та знайдено модифікації цих алгоритмів із стійкістю до атак лінеаризації. Виявилося, що разом з графами D(n, K) можна ефективно використовувати й інші алгебраїчні графи з подібними властивостями, такі як графи A(n,K).
У статті розглядаються кілька розв’язань задачі захисту геологічної інформаційної системи від можливих кібератак за допомогою потокових алгоритмів, що спираються на графи. Вони мають істотні переваги в порівнянні з реалізованими раніше алгоритмами.
Посилання
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.
##submission.downloads##
Опубліковано
Як цитувати
Номер
Розділ
Ліцензія
Авторське право (c) 2023 В.О. Устименко, О.С. Пустовіт
Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.
Збірник «Екологічна безпека та природокористування» працює у рамках міжнародної ліцензії Creative Commons Attribution («із зазначенням авторства») 4.0 International (CC BY 4.0).
Ліцензійна політика журналу сумісна з переважною більшістю політик відкритого доступу та архівування матеріалів.
