Paper 2016/708

From 5-pass MQ-based identification to MQ-based signatures

Ming-Shing Chen, Andreas Hülsing, Joost Rijneveld, Simona Samardjiska, and Peter Schwabe


This paper presents MQDSS, the first signature scheme with a security reduction based on the problem of solving a multivariate system of quadratic equations (MQ problem). In order to construct this scheme we give a new security reduction for the Fiat-Shamir transform from a large class of $5$-pass identification schemes and show that a previous attempt from the literature to obtain such a proof does not achieve the desired goal. We give concrete parameters for MQDSS and provide a detailed security analysis showing that the resulting instantiation MQDSS-31-64 achieves $128$ bits of post-quantum security. Finally, we describe an optimized implementation of MQDSS-31-64 for recent Intel processors with full protection against timing attacks and report benchmarks of this implementation.

Note: *A missed reference.* After finishing this work, we were made aware that the authors of [EDV+12] published an updated journal version of their paper [DGV+16]. In this updated version, the authors give a new definition of $n$-soundness, adapt their forking lemma, and fix the presented signature scheme constructions to respect the requirement of exponentially large challenge spaces. However, it turns out that even the updated proof in [DGV+16] does not cover security of the proposed MQ-based signature scheme (and neither of the code-based signature scheme proposed in the same paper). Nevertheless, the signature schemes proposed in [DGV+16] can be proven secure using our results without any modifications.

Available format(s)
Public-key cryptography
Publication info
A major revision of an IACR publication in ASIACRYPT 2016
post-quantum cryptographyFiat-Shamir$5$-pass identification schemevectorized implementation
Contact author(s)
authors-mqdss @ huelsing net
2016-12-04: last of 2 revisions
2016-07-18: received
See all versions
Short URL
Creative Commons Attribution


      author = {Ming-Shing Chen and Andreas Hülsing and Joost Rijneveld and Simona Samardjiska and Peter Schwabe},
      title = {From 5-pass {MQ}-based identification to {MQ}-based signatures},
      howpublished = {Cryptology ePrint Archive, Paper 2016/708},
      year = {2016},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.