Paper 2020/837

An Attack on Some Signature Schemes Constructed From Five-Pass Identification Schemes

Daniel Kales and Greg Zaverucha


We present a generic forgery attack on signature schemes constructed from 5-round identification schemes made non-interactive with the Fiat-Shamir transform. The attack applies to ID schemes that use parallel repetition to decrease the soundness error. The attack can be mitigated by increasing the number of parallel repetitions, and our analysis of the attack facilitates parameter selection. We apply the attack to MQDSS, a post-quantum signature scheme relying on the hardness of the MQ-problem. Concretely, forging a signature for the L1 instance of MQDSS, which should provide 128 bits of security, can be done in $\approx 2^{95}$ operations. We verify the validity of the attack by implementing it for round-reduced versions of MQDSS, and the designers have revised their parameter choices accordingly. We also survey other post-quantum signature algorithms and find the attack succeeds against PKP-DSS (a signature scheme based on the hardness of the permuted kernel problem) and list other schemes that may be affected. Finally, we use our analysis to choose parameters and investigate the performance of a 5-round variant of the Picnic scheme.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. MINOR revision.CANS 2020
public-key signaturessecurity analysispost-quantum cryptographyFiat-Shamir transformMQDSS
Contact author(s)
daniel kales @ iaik tugraz at
gregz @ microsoft com
2020-10-06: revised
2020-07-12: received
See all versions
Short URL
Creative Commons Attribution


      author = {Daniel Kales and Greg Zaverucha},
      title = {An Attack on Some Signature Schemes Constructed From Five-Pass Identification Schemes},
      howpublished = {Cryptology ePrint Archive, Paper 2020/837},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.