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

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

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

22 Citaten (Scopus)

Samenvatting

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.

Originele taal-2Engels
TitelAdvances in Cryptology - ASIACRYPT 2016 - 22nd International Conference on the Theory and Application of Cryptology and Information Security, Proceedings
UitgeverijSpringer
Pagina's135-165
Aantal pagina's31
ISBN van geprinte versie9783662538890
DOI's
StatusGepubliceerd - 2016
Evenement22nd International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT 2016) - Hanoi, Vietnam
Duur: 4 dec 20168 dec 2016
Congresnummer: 22

Publicatie series

NaamLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
UitgeverijSpringer
Volume10032
ISSN van geprinte versie0302-9743
ISSN van elektronische versie1611-3349

Congres

Congres22nd International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT 2016)
Verkorte titelASIACRYPT 2016
LandVietnam
StadHanoi
Periode4/12/168/12/16

    Vingerafdruk

Citeer dit

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 (blz. 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