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

M.S. Chen, A. Hülsing, J. Rijneveld, S. Samardjiska, P. Schwabe

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

22 Citations (Scopus)

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.

Original languageEnglish
Title of host publicationAdvances in Cryptology - ASIACRYPT 2016 - 22nd International Conference on the Theory and Application of Cryptology and Information Security, Proceedings
PublisherSpringer
Pages135-165
Number of pages31
ISBN (Print)9783662538890
DOIs
Publication statusPublished - 2016
Event22nd International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT 2016) - Hanoi, Viet Nam
Duration: 4 Dec 20168 Dec 2016
Conference number: 22

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PublisherSpringer
Volume10032
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference22nd International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT 2016)
Abbreviated titleASIACRYPT 2016
CountryViet Nam
CityHanoi
Period4/12/168/12/16

Keywords

  • 5-pass identification scheme
  • Fiat-Shamir
  • Post-quantum cryptography
  • Vectorized implementation

Fingerprint Dive into the research topics of 'From 5-pass MQ-based identification to MQ-based signatures'. Together they form a unique fingerprint.

  • Cite this

    Chen, M. S., Hülsing, A., Rijneveld, J., Samardjiska, S., & Schwabe, P. (2016). From 5-pass MQ-based identification to MQ-based signatures. In Advances in Cryptology - ASIACRYPT 2016 - 22nd International Conference on the Theory and Application of Cryptology and Information Security, Proceedings (pp. 135-165). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10032 ). Springer. https://doi.org/10.1007/978-3-662-53890-6_5