Vortrag
Rank analysis of Cubic Multivariate Cryptosystems
Vortrag von Dr. Karan Khathuria
Datum: 09.05.18 Zeit: 16.00 - 17.00 Raum:
Multivariate cryptography is the study of public-key cryptosystems based on multivariate polynomials over a finite field. Since solving a system of multivariate nonlinear polynomials over a finite field of order 2 is proven to be NP-hard, it is considered to be secure against quantum computers. Currently, most of the multivariate schemes are based on system of quadratic polynomials, mainly because of two reasons. First, they are smaller compared to higher degree constructions and hence more efficient. Second, if f is cubic, its (symmetric) differential Df(x) = f(x+a) - f(x) - f(a) is a quadratic map that preserves some of the properties of f. In quadratic constructions, one of the most successful family of attacks is the min-rank attack. It exploits the existence of low-rank linear combination of the matrices representing the quadratic forms of the public polynomials. One natural way to avoid this attack is to use cubic polynomials. This leads to several natural questions: Is there a notion of rank for cubic forms? Can we extend the min-rank attack to cubic constructions? Is the differential attack always a vulnerability for such constructions? What are the implications of low-rank cubic constructions? In this talk, we address all these questions by taking a general perspective of cubic multivariate schemes. This is a joint work with John Baena, Daniel Cabarcas, Daniel Escudero and Javier Verbel.