Cryptography and coding for greater digital security
Inria's dynamic approach to science is due in part to its policy of regularly renewing its project teams. Indeed, every four to eight years, the teams must present a new research project. This offers an opportunity to come up with a new theme, a new team leader, a new name, new profiles, etc. A few months after the Tanc team evolved to form the Grace research project, we met with Daniel Augot, the new team leader, to discuss the implications of this change.
Can you explain the fields concerned by the Grace team (Geometry, arithmetic, algorithms, codes and encryption)?
We are interested in cryptography as a means of protecting data, communications, and machines against attacks through the use of algorithms and computing protocols, but also coding as a way of preventing random incidents. Our concern is applying the appropriate level of protection for the need , because preventing the random cause of a failure is not the same as warding off a hacker. We could say that it is better to envisage the worst possible scenarios and be capable of dealing with anything, but that would be very heavy in terms of energy and speed for applications that don’t necessarily require them. So, we base our work on an intermediate case, meaning that we predict several problems, but not that everything would go wrong at once. In this intermediate case, coding is sufficient, whereas in a worst case scenario, cryptography is required. For example, it isn't very important if a telephone conversation is interrupted, but it is vital that the commands transmitted inside a nuclear power plant be clearly understood and authenticated.
In this context, what was the interest of transforming the Tanc team into Grace?
François Morain had been in charge of Tanc for several years. There had been a lot of changes in staff: Andreas Enge left for the Bordeaux centre, Benjamin Smith and I joined the team, Alain Couvreur was recruited in 2011...Moreover, François became a professor at École Polytechnique in 2009, which is a lot of work, and so that's why I became team leader.
In terms of research themes, I contributed, with algebraic coding, a new field of application to the existing themes of Tanc.
Redundancy can be found everywhere, like when you spell your name saying “A as in Alpha, B as in Bravo"
Hence the Grace team was created in January 2012. A new researcher, Françoise Lévy-dit-Vehel, is now part of the team. She is going to reinforce the theme of algebraic coding and represents this synergy that exists with ENSTA, whose students will be joining the Saclay platform in September 2012.
All these reasons, the changes in staff and the new research themes, made it legitimate to change the team, name, and leader.
Can you give us more details regarding the team’s research work?
© Inria / Photo Kaksonen
The team is organised around three fields of research. The first one is algorithmic number theory and its application to cryptography . We write programmes to determine the factorisation and primality of numbers, that is to say we break down a large quantity of prime numbers (a number that can only be divided by itself and 1). The fundamental problem is finding the exact level of difficulty in factorisation.
The second theme is curve-based cryptography , with research on the construction of new curves for public-key cryptography. Cryptography is not all there is to data security, but it's at the heart. To encrypt a message, you can use a RSA-type key or elliptical curve. RSA encryption is routinely used, for example, in Internet security, credit card transactions, or generating an electronic certificate for your tax returns. The choice between these two methods is a question of performance, in terms of speed and key size.
Finally, the third theme is coding
, where the same curves are used to produce more effective codes. This field traditionally falls within the purview of telecommunications, but increasingly we can observe coding in computing: distributed computing, database replication, peer-to-peer systems, etc. We are working, for example, on the most effective implementation of an algorithm for decoding algebraic codes in worst case scenarios.
One problem that can be solved by algebraic coding is, for example, distributed storage, that is to say a file broken down into lots of little sections on several servers, and ensuring that if one or more servers fail, you can find the data thanks to the principle of redundancy applied in this case.
Another application of our research is a contract with the DGA (Direction Générale de l'Armement ) for encryption. This could allow a lighter implementation of algorithms, lighter calculations for mobile components, decreased use of cell phone battery power and faster Internet transmissions.
What is redundancy?
The principle of error correction is redundancy, that is to say entering more data than required. If one part of the message is corrupted, it is still possible to recreate it. An individual therefore transmits more than a "pure" message. It is this additional part that we call redundancy, for example when you spell your name saying "A as in Alpha, B as in Bravo…". There is a fundamental compromise between the redundancy introduced, which should be short, and error resistance, which needs to be strong. For redundancy, we also want a level of "dispersion". If you used "Brava" instead of "Bravo", communication would be poor because Alpha and Brava are too similar phonetically. Alpha is easier to distinguish from Bravo, which disperses "A" and "B" more effectively.