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

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

doi:10.1007/978-3-662-53890-6_5

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 proceeding › Conference contribution › Academic › peer-review

57 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 language	English
Title of host publication	Advances in Cryptology - ASIACRYPT 2016 - 22nd International Conference on the Theory and Application of Cryptology and Information Security, Proceedings
Publisher	Springer
Pages	135-165
Number of pages	31
ISBN (Print)	9783662538890
DOIs	https://doi.org/10.1007/978-3-662-53890-6_5
Publication status	Published - 2016
Event	22nd International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2016 - Hanoi, Viet Nam Duration: 4 Dec 2016 → 8 Dec 2016 Conference number: 22

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Publisher	Springer
Volume	10032
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	22nd International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2016
Abbreviated title	ASIACRYPT 2016
Country/Territory	Viet Nam
City	Hanoi
Period	4/12/16 → 8/12/16

Keywords

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

Access to Document

10.1007/978-3-662-53890-6_5

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

Chen, M.S. ; Hülsing, A. ; Rijneveld, J. et al. / From 5-pass MQ-based identification to MQ-based signatures. Advances in Cryptology - ASIACRYPT 2016 - 22nd International Conference on the Theory and Application of Cryptology and Information Security, Proceedings. Springer, 2016. pp. 135-165 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{d00ce665b84b46b1846cc5622fe90910,

title = "From 5-pass MQ-based identification to MQ-based signatures",

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.",

keywords = "5-pass identification scheme, Fiat-Shamir, Post-quantum cryptography, Vectorized implementation",

author = "M.S. Chen and A. H{\"u}lsing and J. Rijneveld and S. Samardjiska and P. Schwabe",

year = "2016",

doi = "10.1007/978-3-662-53890-6_5",

language = "English",

isbn = "9783662538890",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "135--165",

booktitle = "Advances in Cryptology - ASIACRYPT 2016 - 22nd International Conference on the Theory and Application of Cryptology and Information Security, Proceedings",

address = "Germany",

note = "22nd International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2016, ASIACRYPT 2016 ; Conference date: 04-12-2016 Through 08-12-2016",

}

Chen, MS, 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. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10032 , Springer, pp. 135-165, 22nd International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2016, Hanoi, Viet Nam, 4/12/16. https://doi.org/10.1007/978-3-662-53890-6_5

From 5-pass MQ-based identification to MQ-based signatures. / Chen, M.S.; Hülsing, A.; Rijneveld, J. et al.
Advances in Cryptology - ASIACRYPT 2016 - 22nd International Conference on the Theory and Application of Cryptology and Information Security, Proceedings. Springer, 2016. p. 135-165 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10032 ).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

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

AU - Chen, M.S.

AU - Hülsing, A.

AU - Rijneveld, J.

AU - Samardjiska, S.

AU - Schwabe, P.

N1 - Conference code: 22

PY - 2016

Y1 - 2016

N2 - 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.

AB - 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.

KW - 5-pass identification scheme

KW - Fiat-Shamir

KW - Post-quantum cryptography

KW - Vectorized implementation

UR - http://www.scopus.com/inward/record.url?scp=85008190978&partnerID=8YFLogxK

U2 - 10.1007/978-3-662-53890-6_5

DO - 10.1007/978-3-662-53890-6_5

M3 - Conference contribution

AN - SCOPUS:85008190978

SN - 9783662538890

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 135

EP - 165

BT - Advances in Cryptology - ASIACRYPT 2016 - 22nd International Conference on the Theory and Application of Cryptology and Information Security, Proceedings

PB - Springer

T2 - 22nd International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2016

Y2 - 4 December 2016 through 8 December 2016

ER -

Chen MS, Hülsing A, Rijneveld J, Samardjiska S, Schwabe P. 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. Springer. 2016. p. 135-165. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-662-53890-6_5

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

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this