Simona Samardjiska
Degree: Ph.D.
Graduation year: 2015
Supervisor: Danilo Gligoroski
Title: Multivariate public key cryptosystems produced by quasigroups

Multivariate public key cryptography (MPKC) is the study of public key cryptosystems based on the NP-hard problem of solving multivariate quadratic (MQ) systems of equations over finite fields. In the past two decades the concept has gained the attention of the cryptographic community as one of the possible alternatives for the post quantum world: a world in which, due to known quantum algorithms, the classical, number theoretic public key cryptosystems will no longer be considered secure.
Over the years, the research on MQ cryptosystems has undergone significant development producing many interesting and versatile design ideas. One of the more recent designs is the MQQ cryptosystem and its successor, the signature scheme MQQ-SIG. Both schemes use multivariate quadratic quasigroups (MQQ) in the construction of the trapdoor.
The work in this thesis is focused on several different aspects of the MQQ design: improvement of performance, new design solutions and security analysis of the underlying MQQ trapdoor. The approach taken in order to tackle all of these aspects is based on the state of the art of MQ cryptography and quasigroup theory and backed up by experimental analysis using Gröbner bases system solvers. As a result, the thesis contributes not only to the MQQ design, but also more generally to polynomial algebra and most importantly to the overall understanding of the security of MQ schemes. The most significant contributions can be summarized as follows.
In the first phase of the research, several new constructions of classes of functions are proposed that can be used in the design of MQ schemes. For example, a new way of constructing MQQs is proposed, that significantly improves the efficiency of MQQ-SIG in terms of key size and signing speed. Furthermore, more general types of structures, namely Left MQQs, are proposed for use instead of MQQs, in order to improve the security, while not degrading the efficiency.
The obtained improvements result in a design of a new encryption scheme MQQ-ENC that is the main topic of interest in the second phase of the research. The security of the scheme is analysed both theoretically and experimentally using the current best known cryptanalytic techniques. An appropriate conversion for IND-CCA security of the scheme is also proposed.
The appearance of a new powerful cryptanalytic technique called Good Keys, initiates the results in the third and final phase of the research. An application of the technique of Good Keys reveals that MQQ-SIG and MQQ-ENC contain too much structure and therefore a practical, polynomial key recovery attack is possible on both schemes. The detailed analysis of the good keys that exist for MQQ-SIG and MQQ-ENC shows that good keys attacks and the closely related rank attacks need to be modelled differently over fields of characteristic 2. Besides the theoretical arguments, this result is also confirmed experimentally.
The thorough analysis of MQQ cryptosystems leads to a proposal of a new security framework for MQ cryptography. The adaptation of known linearity measures from symmetric cryptography in the context of MQ cryptography is undoubtedly the thesis contribution of widest application. It can be used as a general measure for the security of MQ trapdoors with respect to any attack that exploits the existence of linear subspaces of the trapdoor.

Presentation: slides
Trial lecture
Topic: What is a quantum computer and what are the relations to cryptology?
Presentation: slides
Evaluation committee