Algebraic Cryptanalysis and How to Break and Design Cryptographic Algorithms for the Future

The talk will be comprised of two presentations (2x45 minutes), where the first half is intended as a more general overview which should be accessible to last-year bachelor students in Computer Science and Mathematics. The latter half will assume further knowledge, as I dive deeper into my own research and discuss possible research directions for the future. Everyone is very welcome to join one, or both, of the presentations.

Abstract

Algebraic cryptanalysis is mainly concerned with the mathematical problem of solving systems of polynomial equations in many variables. This is a fundamental problem with applications to many aspects of cryptography. As an example, it provides the security foundation for a multitude of Post-Quantum (PQ) algorithms, i.e., cryptographic algorithms that will remain secure in the presence of future quantum computers. Algebraic cryptanalysis is moreover crucial for Arithmetization-Oriented (AO) cryptography, which often forms a vital component in implementations of privacy-preserving technologies such as Homomorphic Encryption, Zero-Knowledge Proofs and Multi-Party Computation.

It follows that the future deployment of many cryptographic algorithms will depend on our understanding of algebraic cryptanalysis. However, despite decades of effort, the problem of polynomial system solving remains extremely hard to get right. Indeed, many proposed PQ-/AO-cryptosystems have already been broken, as will undoubtedly many more be in the years to come.
In this talk I will give an overview of algebraic cryptanalysis for PQ and AO algorithms: why do they break, and how can we secure them in the future?