Paper 2023/1131
One vector to rule them all: Key recovery from one vector in UOV schemes
Abstract
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.
Metadata
- Available format(s)
-
PDF
- Category
- Attacks and cryptanalysis
- Publication info
- Published elsewhere. PQCrypto 2024
- Keywords
- UOVKey recoveryMultivariate Cryptography
- Contact author(s)
- pierre pebereau @ lip6 fr
- History
- 2024-05-15: last of 2 revisions
- 2023-07-20: received
- See all versions
- Short URL
- https://ia.cr/2023/1131
- License
-
CC0
BibTeX
@misc{cryptoeprint:2023/1131,
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},
url = {https://eprint.iacr.org/2023/1131}
}
