The Unbalanced Oil and Vinegar (UOV) construction has been a central framework in multivariate cryptography since its appearance in 1999. For efficiency considerations, most of these schemes are defined over a field of characteristic 2. This has as consequence that both the public and secret key can be considered as elements of the exterior algebra.
In this talk, we discuss a key-recovery attack on UOV over fields of characteristic 2 that exploits this. We interpret the polar forms of the UOV public map as elements of the second exterior power. Furthermore, using the Pl\"ucker embedding, we express the dual of the secret oil space as an element of the exterior algebra. Utilizing the structure of the public maps, we can formulate relations on this secret element in this algebra. Finally, we demonstrate that the oil space can be recovered using sparse linear algebra techniques.
This attack has a lower time complexity than previous methods and reduces the security of \verb|uov-Ip|, \verb|uov-III|, \verb|uov-V|, and MAYO$_2$ by 4, 11, 20, and 28 bits respectively.
I am a last-year PhD student in Post-Quantum cryptography at the Radboud Universiteit Nijmegen under supervision of Simona Samardjiska. I am focusing on using algebraic techniques for cryptanalysis of different hardness assumptions mostly related to multivariate and code-based cryptography.