Algebraic Cryptanalysis of Cryptographic Schemes with Extension Field Structure

Abstract

Post-Quantum Cryptography studies cryptographic algorithms that quantum computers cannot break. Recent advances in quantum computing have made this kind of cryptography necessary, and research in the field has surged over the last years as a result. One of the main families of post-quantum cryptographic schemes is based on finding solutions of a polynomial system over finite fields. This family, known as multivariate cryptography, includes both public key encryption and signature schemes.

The majority of the research contribution of this thesis is devoted to understanding the security of multivariate cryptography. We mainly focus on big field schemes, i.e., constructions that utilize the structure of a large extension field. One essential contribution is an increased understanding of how Gröbner basis algorithms can exploit this structure. The increased knowledge furthermore allows us to design new attacks in this setting. In particular, the methods are applied to two encryption schemes suggested in the literature: EFLASH and Dob. We show that the recommended parameters for these schemes will not achieve the proposed 80-bit security. Moreover, it seems unlikely that there can be secure and efficient variants based on these ideas. Another contribution is the study of the effectiveness and limitations of a recently proposed rank attack. Finally, we analyze some of the algebraic properties of MiMC, a block cipher designed to minimize its multiplicative complexity.