On extremal algebraic graphs, Eulerian transformations and implementations of multivariate cryptosystems

• Date: 2026
• Author Affiliations: Vasyl Ustimenko — Доктор фізико-математичних наук, професор, завідуючий відділу інформаційної безпеки Інституту телекомунікацій і глобального інформаційного простору НАН України, Київ, Visiting Professor of Royal Holloway University of London; Oleksandr Pustovit — Кандидат технічних наук, старший науковий співробітник Інституту телекомунікацій і глобального інформаційного простору НАН України, Київ
• Keywords: keywords
• Main Authors: Ustimenko, Vasyl, Pustovit, Oleksandr
• Format: Article
• Language: English
• Published: Kyiv National University of Construction and Architecture 2026
• Subjects: Multivariate Cryptography; Symbolic Computations; Algebraic Graphs; Extremal Graph Theory
• Online Access: https://es-journal.in.ua/article/view/364963
• Journal Title: Environmental safety and natural resources

Results of implementation of several multivariate public keys of linear degree of size O(n) and polynomial density defined over commutative ring K with the nontrivial multiplicative group K*. are presented. The space of plaintexts of these cryptosystems is (K*)n and space of ciphertexts is Kn. The encryption map is the restriction on (K*)n of polynomial transformation of the space Kn which is the composition of special Eulerian trams-formation with cubical map of Multivariate Cryptography of kind T1QT2, where T1 and T2 are bijective affine trans-formations and Q is a nonlinear map defined via walk on algebraic bipartite graph points and lines of which form the space Kn.This scheme is implemented for the cases K=Fq and K=Zq, q=232. The knowledge of private key allows to decipher of the message from public user in time O(n2). The cryptosystems are generalisations of algorithms suggested 9 years ago cryptanalysis of which are unknown. The problem of breaking the cryptosystem is equivalent to solving of system of nonlinear equations in n variables of degree cn, de c>0. The computer packages for the investigation of such systems are undeveloped.