Paper 2023/1131

One vector to rule them all: Key recovery from one vector in UOV schemes

Pierre Pébereau, Sorbonne University, Laboratoire de Recherche en Informatique de Paris 6, Centre National de la Recherche Scientifique, Thales (France)

Unbalanced Oil and Vinegar is a multivariate signature scheme that was introduced in 1999. Most multivariate candidates for signature schemes at NIST's PQC standardization process are either based on UOV or closely related to it. The UOV trapdoor is a secret subspace, the "oil subspace". We show how to recover an equivalent secret key from the knowledge of a single vector in the oil subspace in any characteristic. The reconciliation attack was sped-up by adding some bilinear equations in the subsequent computations, and able to conclude after two vectors were found. We show here that these bilinear equations contain enough information to dismiss the quadratic equations and retrieve the secret subspace with linear algebra for practical parametrizations of UOV, in at most 15 seconds for modern instanciations of UOV. This proves that the security of the UOV scheme lies in the complexity of finding exactly one vector in the oil space. In addition, we deduce a key recovery attack from any forgery attack by applying a corollary of our main result. We show how to extend this result to schemes related to UOV, such as MAYO and VOX.

Note: Revision: corrected the analysis of VOX.

Available format(s)
Attacks and cryptanalysis
Publication info
UOVKey recoveryMultivariate Cryptography
Contact author(s)
pierre pebereau @ lip6 fr
2023-07-27: revised
2023-07-20: received
See all versions
Short URL
No rights reserved


      author = {Pierre Pébereau},
      title = {One vector to rule them all: Key recovery from one vector in UOV schemes},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1131},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.