Algebraic Methods for Cryptography – MAC

This project is to be replaced in the more general context of information protection. Its research areas are
cryptography and symbolic computation. We are here essentially - but not exclusively - concerned with
public key cryptography. Public key cryptography relies on the notion of (trapdoor) one-way function. Intuitively,
such a function is easy (polynomial-time) to compute, but difficult (at best sub-exponential) to
invert (except if one knows a trapdoor, rendering preimage computation easy). One way functions themselves
are constructed from hard problems (roughly speaking, problems for which no polynomial-time
algorithm is known). In the cryptographic context, although quite a few problems have been proposed to
construct primitives, those effectively used are essentially factorization (e.g. in RSA) and discrete logarithm
(e.g. in Diffie-Hellman key-exchange). It is well-known that, although polynomial-time algorithms
for those problems have not yet been found, they are not safe from a theoretic breakthrough, that would
endanger the security of the corresponding schemes.Besides, the schemes based on those two problems
are too slow to be used in strongly constrained environments, like mobile communications (ad-hoc networks,
RFID...).Thus, one of the main issues in public key cryptography is to identify hard problems, and
propose new schemes that are not based on number theory. Having in mind the numerous applications of
cryptography in the real world (access control, authentication, securing Internet transactions, protecting
communications...),the consequences of new results in this area are not only of scientific interest, but are
also important from an economical point of view.
Following this line of research, multivariate schemes have been introduced in the mid eighties by Diffie
and Fell in 1985, Matsumoto and Imai in 1988. We recall that multivariate cryptography comprises any
cryptographic scheme that uses multivariate polynomial systems. It has to be mentioned that schemes
based on the hard problem of solving multivariate equations over a finite field are not concerned with the
quantum computer threat, whereas as it is well known that number theoretic-based schemes like RSA,
DH, or ECDH are. Besides, multivariate schemes enjoy low computational requirements and can yield
short signatures, an everlasting concern in public-key cryptography.
Recently, multivariate cryptography has become a very important research area. This is mainly due to
the fact that a European project (NESSIE) has advised in 2003 to use such a scheme (namely, SFLASH)
in the smart-card context. Moreover, there have been proposals for almost every functionality : signature
(Sflash, Quartz, TTS, STS, enTTS, UOV, Rainbow), encryption (Hfe, MI, PMI, 2R...), stream cipher
(Quad), traitor tracing (Billet-Gilber}). It has to be noted, though, that the situation is quite different in
industry : people are still reluctant to use those schemes, because their security is still not well mastered.
In order to evaluate the security of new proposed schemes, strong and efficient cryptanalytic methods
have to be developped. The main theme we shall address in this project is the evaluation of the security of
cryptographic primitives by means of algebraic methods. The idea is to model a cryptographic primitive
as a system of algebraic equations. The system is constructed in such a way as to have a correspondence
between the solutions of this system, and a secret information of the considered primitive. Once this
modeling is done, the problem is then to solve an algebraic system.
Our approach is motivated by the fact that algebraic analysis has appeared only a few years ago in
the cryptographic setting, and thus constitutes a new way of investigating the security of cryptographic
primitives. Moreover its scope is not well understood, and the results in this area are somewhat fuzzy.What
we aim at is primarily identifying those schemes that resist algebraic cryptanalysis. For those, we shall
then give suitable parameters for secure use, a crucial point that often lacks clarity in the proposed
schemes. But in a broader understanding, our project aims at conceiving the best known attacks on a
random system of equations.
In a first phase of the project, we shall identify the schemes or classes of schemes that are worth studying,
from the point of view of algebraic analysis. Then, we shall start the core of our study, namely the
analysis itself. This work will be organized according to the classes we have identified at first stage.Our
analytic work will also include a prospective part, in which we shall broaden our study by considering
schemes arising from secret key cryptography (block ciphers like AES, stream ciphers like QUAD) or
other cryptographic primitives (e.g. SHA1). In a subsequent phase, we shall use our results to design, or
at least set up elements for the design of secure multivariate schemes.