Computer Algebra and Cryptography – CAC

This project is placed in the general context of Information Security. More specifically, the project will investigate the areas of cryptography and computer algebra, and their influence on the security and integrity of digital data. The modern world is completely reliant on digital technologies. Almost all important data is stored and transmitted in electronic form. This potentially exposes this data to serious threats, which include disclosure of data to unauthorized parties, unauthorized alteration of data, falsification of the origin of data, and false denial of participation in a transaction at a particular moment in time. The science of cryptography, a collection of mathematical techniques used to secure the transmission and storage of information, is one of the main tools to counter these threats. Cryptographic primitives can be divided into two large classes. First, Secret-key cryptography (or symmetric cryptography) uses the same key for both decryption and encryption. This key is a shared secret between two or more parties that can be used to maintain a private information link. In secret-key cryptography. The most studied and widely used class of symmetric cryptographic algorithms are block ciphers. Block ciphers are mathematical functions that take as input a plaintext and a secret key. By performing highly complex scrambling operations, a block cipher outputs an encrypted version of the input text, known as ciphertext. On the other hand, Public-key cryptography (or asymmetric cryptography) ; in that case the key used to encrypt a message differs from the key used to decrypt it. The private key is kept secret, while the public key is widely distributed. For this class of algorithms, RSA (Rivest, Shamir and Adleman) is the most widely known and deployed. RSA uses exponentiation modulo a product of two large primes to encrypt and decrypt, performing both public key encryption and public key digital signature. Its security is related with the difficulty of factoring large integers, a problem for which there is no known efficient general technique. A relaxation of this factorization problem arises when some additional information is provided. The problem is then to factor large integers knowing some bits of the prime factors. A fundamental problem in cryptography is to evaluate the security of cryptosystems against the most powerful techniques. To this end, several general methods have been proposed : linear cryptanalysis, differential cryptanalysis, . . . The aim of this project is to apply another general method ' Algebraic cryptanalysis ' to study the security of the main public-key and secret-key cryptosystems. Algebraic cryptanalysis can be described as a general framework that permits to asses the security of a wide range of cryptographic schemes. In fact the recent proposal and development of algebraic cryptanalysis is now widely considered as an important breakthrough in the analysis of cryptographic primitives. It is a powerful technique that applies potentially to a large range of cryptosystems. The basic principle of such cryptanalysis is to model a cryptographic primitive by a set of algebraic equations. The system of equations is constructed in such a way as to have a correspon- dence between the solutions of this system, and a secret information of the cryptographic primitive (for instance, the secret key of an encryption scheme). On the one hand algebraic techniques have been successfully applied against a number of multivariate schemes and in stream cipher cryptanalysis. On the other hand, the fea- sibility of algebraic cryptanalysis against remains the source of speculation for block ciphers, and an almost unexplored approach for hash functions. The scientific lock is that the size of the corresponding algebraic system is so huge (thousand of variables and equations) that nobody is able to predict correctly the complexity of solving such polynomial systems. Very recently, the interaction between Gröbner basis computation and LLL has been put forward highlighting the importance of Gröbner basis techniques to design rigorous Coppersmith's variants. However, right now, only few things are known about this interaction. The goal of this proposal is ultimately to design and implement a new generation of efficient algebraic cryptanalysis toolkits to be used against block ciphers, hash functions and for the problem of factoring with known bits. To achieve this goal, we will investigate non-conventional approaches for modelling these problems.