Welcome to the resource topic for 2023/1131
Title:
One vector to rule them all: Key recovery from one vector in UOV schemes
Authors: Pierre Pébereau
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.
ePrint: https://eprint.iacr.org/2023/1131
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .