Cryptanalysis of Multivariate-Based Post-Quantum Digital Signature Schemes

Abstract

In this thesis, we study three proposed multivariate-based post-quantum digital signature schemes: Triangular Unbalanced Oil and Vinegar (TUOV), Biscuit, and Multivariate Polynomial Public Key Digital Signature Scheme (MPPK/DS). Our work aims to first explore the underlying problems in multivariate cryptography that these schemes employ. We then provide detailed descriptions and concrete security analysis of these three proposed schemes. We prove that a security reduction that was claimed to be a unique feature of the TUOV signature scheme also applies to the more classical UOV scheme, we provide careful analysis and more detailed proofs of two attacks on Biscuit from the literature, and we present a novel classically efficient forgery attack on MPPK/DS that renders it insecure.