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.
Has parts
Paper I: Øygarden, M., Felke, P., Raddum, H., and Cid, C. Cryptanalysis of the multivariate encryption scheme EFLASH. In: Cryptographers Track at the RSA Conference, pages 85-105. Springer, 2020. The article is available in the thesis file. The article is also available at: https://doi.org/10.1007/978-3-030-40186-3_5Paper II: Øygarden, M., Felke, P., and Raddum, H. Analysis of Multivariate Encryption Schemes: Application to Dob. In: International Conference on Public-Key Cryptography (PKC), pages 155-183. Springer, 2021. The article is available in the thesis file. The article is also available at: https://doi.org/10.1007/978-3-030-75245-3_7
Paper III: Øygarden, M., Smith–Tone, D., and Verbel, J. On the Effect of Projection on Rank Attacks in Multivariate Cryptography. In: PQCrypto: International Conference on Post-Quantum Cryptography, pages 98-113. Springer, 2021. The article is available in the thesis file. The article is also available at: https://doi.org/10.1007/978-3-030-81293-5_6
Paper IV: Eichlseder, M., Grassi, L., Lüftenegger, R., Øygarden, M., Rechberger, C., Schofnegger, M., and Wang, Q. An Algebraic Attack on Ciphers with Low– Degree Round Functions: Application to Full MiMC. In: International Conference on the Theory and Application of Cryptology and Information Security (Asiacrypt), pages 477-506. Springer, 2020. The article is available in the thesis file. The article is also available at: https://doi.org/10.1007/978-3-030-64837-4_16