Paper 2023/432
Practical key-recovery attack on MQ-Sign
Abstract
This note describes a polynomial-time key-recovery attack on the UOV-based signature scheme called MQ-Sign. The scheme is a first-round candidate in the Korean Post-Quantum Cryptography Competition. Our attack exploits the sparsity of the secret central polynomials in combination with the specific structure of the secret linear map $S$. We provide a verification script that recovers the secret key in less than seven seconds for security level 5.
Metadata
- Available format(s)
-
PDF
- Category
- Attacks and cryptanalysis
- Publication info
- Preprint.
- Keywords
- digital signaturesPQCMQ-Signmultivariate cryptographyUOV
- Contact author(s)
-
thomas aulbach @ ur de
simonas @ cs ru nl
monika trimoska @ ru nl - History
- 2023-03-27: last of 3 revisions
- 2023-03-24: received
- See all versions
- Short URL
- https://ia.cr/2023/432
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2023/432, author = {Thomas Aulbach and Simona Samardjiska and Monika Trimoska}, title = {Practical key-recovery attack on MQ-Sign}, howpublished = {Cryptology ePrint Archive, Paper 2023/432}, year = {2023}, note = {\url{https://eprint.iacr.org/2023/432}}, url = {https://eprint.iacr.org/2023/432} }