Practical key-recovery attack on MQ-Sign

Thomas Aulbach; Simona Samardjiska; Monika Trimoska

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 signatures PQC MQ-Sign multivariate cryptography UOV
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}
}