Paper 2023/432

Practical key-recovery attack on MQ-Sign

Thomas Aulbach, University of Regensburg, Regensburg, Germany
Simona Samardjiska, Radboud University, Nijmegen, The Netherlands
Monika Trimoska, Radboud University, Nijmegen, The Netherlands
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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.