MULTIVARIATE PUBLIC KEY CRYPTOSYSTEMS PRODUCED BY QUASIGROUPS
Doctoral thesis
Permanent lenke
http://hdl.handle.net/11250/2364637Utgivelsesdato
2015Metadata
Vis full innførselSamlinger
Sammendrag
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 MQQENC
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.