The design and cryptanalysis of post-quantum cryptographic signature schemes are major challenges for modern cryptography. This thesis examines some signature schemes based on multivariate cryptography and their cryptanalysis. We focus on the Unbalanced Oil and Vinegar (UOV) digital signature scheme and its variants. UOV is to date the most robust multivariate signature scheme, while also achieving the shortest signatures among post-quantum algorithms. Geometrically, the UOV trapdoor is a linear subspace of large dimension included in the algebraic set defined by the public key equations.
Our approach is geometric by nature. First, we prove that, given a single vector in the secret trapdoor, the key recovery problem can be solved in polynomial time. Next, following previous work by Beullens, Castryck and Luyten, we show that the algebraic varieties defined by UOV polynomials are singular, and provide a lower bound on the dimension of the intersection of the singular locus with the secret subspace. This body of results, combined with extra geometric properties, allows us to identify weaknesses in UOV variants submitted to NIST, such as the ^+ structure and VOX. We also leverage subfield structure to obtain a practical cryptanalysis of VOX parameters submitted to NIST.
All these contributions come with open source implementations, some of them yielding attacks that can be run in a few seconds on some standard commercial laptop.