ProvACAna: Provable Algebraic CryptAnalysis

The Internet can be understood as a large traffic network for digital communication in which, in principle, anyone can communicate with anyone else. Since, however, any participant can also make arbitrary claims, the Internet per se offers no protection against fraud, eavesdropping, or active manipulation of messages. To counteract such attacks and to ensure the authenticity, integrity, and privacy of digital communication, cryptographic algorithms must be deployed at the protocol level. In fact, commercial use of the Internet would be simply inconceivable without cryptography. Classical cryptosystems based on the factorization of large numbers or on elliptic curves have so far provided reliable protection and are also used in numerous other applications, such as blockchains. Although these systems are very efficient, they canat least theoreticallybe broken by quantum computers. Even though it is still unclear when quantum computers will be available on a commercial scale, it is already necessary today to design and standardize algorithms and protocols for a quantum-resistant Internet. Most quantum- resistant cryptosystems are based on one of the following four mathematical theories: lattice theory, coding theory, the theory of multivariate equation systems, and the theory of isogenies of elliptic curves. Lattice-based cryptosystems are well studied and offer strong security guarantees, but they suffer in efficiency because they require large signatures, ciphertexts, and keys. Isogeny-based cryptosystems, by contrast, are extremely compact and efficient, but their security is still the subject of ongoing research, and their range of applications appears to be limited so far. Multivariate and code-based cryptosystems could, by comparison, offer a good compromise between efficiency and security. However, the question arises: how secure are these systems actually? To assess the security of a cryptosystem and to choose suitable parameters, cryptographers rely on the running time of the fastest known attack in each case. For many code-based as well as for all multivariate cryptosystems, algebraic algorithms are considered the most promising attack methods. Although algebraic cryptanalysis has been known for a long time, its theoretical foundations have so far been little explored. In practice, algebraic cryptanalysis relies on heuristics and empirical experience. This significantly limits the impact of its claims and calls into question the long-term security of quantum-resistant cryptosystems. The goal of this research project is therefore to place algebraic cryptanalysis on a solid mathematical foundation. To this end, four core problems have been identified that are to be systematically investigated using a rigorous, formal methodology.