Paper 2024/219
Singular points of UOV and VOX
Abstract
In this work, we study the singular locus of the varieties defined by the public keys of UOV and VOX, two multivariate signature schemes submitted to the additional NIST call for post-quantum signature schemes. We give a new attack for $\hat +$ and VOX targeting singular points of the underlying UOV key. Our attack lowers the security of the schemes, both asymptotically and in number of gates, showing in particular that the parameter sets proposed for these schemes do not meet the NIST security requirements. More precisely, we show that the security of VOX/UOV$\hat +$ was overestimated by factors $2^{2}, 2^{18}, 2^{37}$ for security levels I, III, V respectively. As an essential element of the attack on VOX, we introduce a polynomial time algorithm performing a key recovery from one vector, with an implementation requiring only $15$ seconds at security level V.
Note: Revision 2024-09-02: Corrected technical lemmas, improved key recovery from one vector in VOX (exp -> polytime). Revision 2025-02-17: Added generic smoothness, improved technical lemmas.
Metadata
- Available format(s)
-
PDF
- Category
- Attacks and cryptanalysis
- Publication info
- Published by the IACR in EUROCRYPT 2025
- Keywords
- Multivariate cryptographyCryptanalysisSingular pointsBihomogeneous polynomial system
- Contact author(s)
- pierre pebereau @ lip6 fr
- History
- 2025-02-17: last of 2 revisions
- 2024-02-13: received
- See all versions
- Short URL
- https://ia.cr/2024/219
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/219,
author = {Pierre Pébereau},
title = {Singular points of {UOV} and {VOX}},
howpublished = {Cryptology {ePrint} Archive, Paper 2024/219},
year = {2024},
url = {https://eprint.iacr.org/2024/219}
}