Abstract: 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.

Paper: 2016-12-01 (older versions: , )

Source code: Available on GitHub

Related talks:
MQDSS
2018-04-12 – NIST's First PQC Standardization Conference –
From 5-pass MQ-based identification to MQ-based signatures
2017-03-24 – Crypto Working Group –
2016-12-05 – ASIACRYPT 2016 –
2016-11-18 – DS Lunch colloquium –
2016-06-30 – Crossing Seminar, TU Darmstadt – by Andreas Hülsing –

@inproceedings{CHRSS16,
  author    = {Ming-Shing Chen and Andreas H\"ulsing and Joost Rijneveld and Simona Samardjiska and Peter Schwabe},
  title     = {From 5-pass MQ-based identification to MQ-based signatures},
  booktitle = {Advances in Cryptology -- {Asiacrypt 2016}},
  editor    = {Jung Hee Cheon and Tsuyoshi Takagi},
  publisher = {Springer-Verlag Berlin Heidelberg},
  series    = {Lecture Notes in Computer Science},
  volume    = {10032},
  year      = {2016},
  pages     = {135--165},
  url       = {https://eprint.iacr.org/2016/708},
}