Research Statement of Ilia Toli

Early in my PhD studies I have concentrated on Public Key Cryptography. The best of my background is Algebra, therefore I have paid particular atention to the polynomial-based cryptosystems. One of the best-known cryptosystems of this class is HFE (Hidden Field Equations).

My results on HFE include finding several keyspace redundancies. I have simplified it in all unessential ways, and this helps its implementation. I think this helps cryptanalysis as well, when the PK contains linearized part. Further research is needed to clarify this topic.

I have also developed HFE further into HIE (Hidden Ideal Equations), in order to defend it from all known attacks. I have written a paper and held several talks in the topic.

I have studied AES (Advanced Encryption System) since its very selection in 2001. In a classical paper, Murphy and Robshaw claim that one can break AES if s/he solves a given overdefined system of 5120 quadratic and 128 linear equations in 3968 variables.

In a joint work with Alberto Zanoni, I prove that their claim is inaccurate. We calculate a lex Gröbner basis for that system, that is, we solve it. The Gröbner basis has 176 equations in 336 variables. Fixing 160 variables and running them by exhaustive search is 256^160.

One can also write this system for 11 or more (plaintext, ciphertext) pairs, and put all systems together. Next, one can eliminate all variables but the 176 key-related variables. Solving such a system by means of general-purpose algorithms should take 176^255 bit time. Still worse, only writing the system down (it is almost topmost dense) requires about 136^255 bit space. It seems the wrong way to break through.

Then we write down another system corresponding to the key-generation algorithm. Solving these two systems put together (336 or more equations in 336 variables) implies breaking AES. We reduce this problem into the problem of solving another system of 16 or more equations in 16 variables. Only to write this system down requires about 16^255 bit space. Therefore, there is no hope to solve it in less than 16^255 bit time.

Fixed the plaintext p, the last system is invariant with varying of keys, except for its constant terms. Probably this helps studying it. This attack is known-plaintext. A similar attack can be set up chosen-ciphertext. By this case, fixed the ciphertext, the system is invariant with varying of keys, except for its constant part.

I have published two papers and held several talks in the topic. I have written a third paper in the topic.

I have matured the idea that Group Theory offers the best means to interpret and probably cryptanalyze AES.

My current research interests span through (more or less from most to least): Complexity Theory, Cryptography, Commutative Algebra, Computer Algebra and Graph Theory.