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, Eindhoven University of Technology, Eindhoven, The Netherlands
Abstract

In this paper we describe attacks on the UOV-based signature scheme called MQ-Sign. MQ-Sign was submitted by Shim, Kim, and An as a a first-round candidate for standardization in the (South) Korean post-quantum cryptography competition (KpqC). The scheme makes use of sparseness of the secret central polynomials and equivalent key construction to reduce the size of the private key. The authors propose four variants exploiting different levels of sparsity, MQ-Sign-SS, MQ-Sign-RS, MQ-Sign-SR, and MQ-Sign-RR with the last one being the standard UOV signature scheme. We show that apart from the MQ-Sign-RR variant, all the others are insecure. Namely, we present a polynomial-time key-recovery attack on the variants MQ-Sign-SS and MQ-Sign-RS and a forgery attack on the variant MQ-Sign-SR below the claimed security level. Our attack exploits exactly the techniques used for reduction of keys - the sparsity of the central polynomials in combination with the specific structure of the secret linear map $\mathbf{S}$. We provide a verification script for the polynomial-time key-recovery attack, that recovers the secret key in less than seven seconds for security level V. Furthermore, we provide an implementation of the non-guessing part of the forgery attack, confirming our complexity estimates.

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
m trimoska @ tue nl
History
2024-01-27: last of 5 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},
      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.