Chat
Chemistry · MapleScholar Plus

Quantum-Resistant Ciphers: Extremal Algebraic Graphs and Multivariate Cryptography

Shor's quantum algorithm threatens to dismantle RSA and elliptic curve public-key cryptography; multivariate quadratic cryptosystems constructed over extremal algebraic graphs provide robust post-quantum security.

Author
Vasyl Ustimenko et al.
Published
2023
Journal
Annals of Computer Science and Information Systems
Last updated
September 2026
Quantum-Resistant Ciphers: Extremal Algebraic Graphs and Multivariate Cryptography

The impending arrival of large-scale quantum computers poses an existential threat to modern digital finance and secure web communication by solving integer factorization and discrete logarithms in polynomial time.

Multivariate quadratic public-key cryptosystems offer post-quantum resistance, but early designs suffered from massive public key sizes and vulnerability to specialized algebraic Gröbner basis attacks.

This mathematical framework constructs multivariate encryption schemes using incidence geometries of extremal algebraic graphs with large girth. The resulting algebraic structures provide provable non-linear complexity while significantly shrinking public key footprints.

These graph-based multivariate constructions offer a lightweight, quantum-resistant cryptographic shield for embedded IoT devices, smart cards, and long-term secure archival data storage.

Reference

Ustimenko, V., & Wroblewska, A. (2023). Extremal algebraic graphs, quadratic multivariate public keys and temporal rules. Proceedings of the 18th Conference on Computer Science and Intelligence Systems, 35, 1173–1178.

Title

Extremal algebraic graphs, quadratic multivariate public keys and temporal rules

Abstract

We introduce large groups of quadratic transformations of a vector space over the finite fields defined via symbolic computations with the usage of algebraic constructions of Extremal Graph Theory. They can serve as platforms for the protocols of Noncommutative Cryptography with security based on the complexity of word decomposition problem in noncommutative polynomial transformation group. The modifications of these symbolic computations in the case of large fields of characteristic two allow us to define quadratic bijective multivariate public keys such that the inverses of public maps has a large polynomial degree. Another family of public keys is defined over arbitrary commutative ring with unity. We suggest the usage of constructed protocols for the private delivery of quadratic encryption maps instead of the public usage of these transformations, i.e. the idea of temporal multivariate rules with their periodical change.

Cited 5 times · View on doi.org

Continue

Continue Exploring

Ask this paper your own questions, or keep browsing the verified research catalogue.