Key recovery from one vector in UOV schemes

After an introduction on multivariate cryptography and algebraic cryptanalysis, we will present a contribution to the cryptanalysis of UOV.

More precisely, UOV is a trapdoor scheme relying on a secret subspace called the “oil subspace”. We will show how to recover a secret key from the knowledge of one single vector in the oil subspace. In other terms, we show that breaking UOV is as hard as finding one such vector because we recover the whole trapdoor in polynomial-time once a vector is known. This attack is also practical: given a secret vector, our implementation recovers the secret key of UOV in at most 15 seconds for NIST security level V.

We will also consider the question of extending this result to schemes related to UOV, in particular MAYO and VOX.