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

30.06.2016, 16:30 – 18:00

2016/06/30 16:30-18:00

Speaker: Andreas Hülsing| Location: Mornewegstraße 32 (S4|14), Room 3.1.01, Darmstadt

Organizer: Daniel Demmler


In this talk I will present joint work with Joost Rijneveld, Simona Samardjiska, and Peter Schwabe on MQDSS, the first signature scheme with a security reduction from 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.

Short Bio

Andreas is a postdoctoral researcher at TU Eindhoven working with Tanja Lange in the PQCRYPTO project. His research focuses on post-quantum cryptography – cryptography that resists quantum computer-aided attacks. His main goal is to get post-quantum cryptography into practice. To achieve this, it is necessary to develop schemes for which reliable security estimates can be made and that meet practical performance requirements. A lot of his research is on hash-based signatures and led to an IRTF Internet draft, recently. Before his current position, he was a postdoctoral researcher in the cryptographic implementations group at TU Eindhoven, working with Daniel J. Bernstein. He did his PhD in the cryptography and computer algebra group at TU Darmstadt under the supervision of Johannes Buchmann. Before starting his PhD, he worked as a research fellow at Fraunhofer SIT in Darmstadt, mainly carrying out applied research in PKI and smartcard projects.