Seminario: "Groebner basis' attack to multivariate cryptography" - Giancarlo Rinaldo

Seminario della serie "Seminari CrypTO", in collaborazione con Telsy SpA, centro di competenza in crittografia e cybersecurity del Gruppo TIM che opera nel perimetro di TIM Enterprise

"Groebner basis' attack to multivariate cryptography"
Giancarlo Rinaldo
Università di Messina

Martedì 23 Aprile 2024 - ore 14:30
Aula Buzano - Dipartimento di Scienze Matematiche
Politecnico di Torino

Abstract: In the last decades multivariate cryptography, namely the cryptography based on the difficulty of finding solutions of a generic system of quadratic polynomial equations, has attracted a good amount of interest in the computational algebra and cryptographic research communities (see [3]). As an example, in 2016, the National Institute of Standards and Technology (NIST) started a competition to select the Post-Quantum cryptosystems for standardization, and two multivariate public key cryptosystems has been proposed: Rainbow (see[4]) based on a multi-layer version of the Unbalanced Oil & Vinegar scheme, and GeMSS (Great Multivariate Short Signature, see [1]) based on HFEv−. After providing the necessary introduction on the multivariate schemes, and classical Buchberger algorithm to solve systems of polynomials, we will present signature-based algorithms that have been extremely successful in solving previously intractable problems (see [2]).

References
[1] Antoine Casanova et al. “GeMSS: a great multivariate short signature”. PhD thesis. UPMC-Paris 6 Sorbonne Universités; INRIA Paris Research Centre, 2017.
[2] Jean-Charles Faugere Christian Eder. “A survey on signature-based Gröbner basis computations”. In: ACM Communications in Computer Algebra. ACM. 2015, pp. 1–61.
[3] Donald O’Shea David A. Cox John Little. Ideals, Varieties, and Algorithms - Fourth edition. Springer, 2018.
[4] Jintai Ding and Dieter Schmidt. “Rainbow, a new multivariable polynomial signature scheme”. In: International
conference on applied cryptography and network security. Springer. 2005, pp. 164–175.