Design principles for HFEV-based multivariate signature schemes

Albrecht Petzoldt; Ming Shing Chen; Bo Yin Yang; Chengdong Tao; Jintai Ding

doi:10.1007/978-3-662-48797-6_14

Design principles for HFEV-based multivariate signature schemes

Albrecht Petzoldt, Ming Shing Chen, Bo Yin Yang, Chengdong Tao, Jintai Ding^*

^*Corresponding author for this work

Research output: Chapter in Book or Report/Conference proceeding › Conference Proceeding › peer-review

88 Citations (Scopus)

Abstract

The Hidden Field Equations (HFE) Cryptosystem as proposed by Patarin is one of the best known and most studied multivariate schemes. While the security of the basic scheme a eared to be very weak, the HFEv-variant seems to be a good candidate for digital signature schemes on the basis of multivariate olynomials. However, the currently existing scheme of this type, the QUARTZ signature scheme, is hardly used in ractice because of its oor efficiency. In this a er we analyze recent results from Ding and Yang about the degree of regularity of HFEv-systems and derive from them design principles for signature schemes of the HFEv-type. Based on these results we propose the new HFEv-based signature scheme Gui, which is more than 100 times faster than QUARTZ and therefore highly com arable with classical signature schemes such as RSA and ECDSA.

Original language	English
Title of host publication	Advances in Cryptology - ASIACRYPT 2015 - 21st International Conference on the Theory and Application of Cryptology and Information Security, 2015, Proceedings
Editors	Jung Hee Cheon, Tetsu Iwata
Publisher	Springer Verlag
Pages	311-334
Number of pages	24
ISBN (Print)	9783662487969
DOIs	https://doi.org/10.1007/978-3-662-48797-6_14
Publication status	Published - 2015
Externally published	Yes
Event	21st International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2015 - Auckland, New Zealand Duration: 29 Nov 2015 → 3 Dec 2015

Publication series

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

Conference

Conference	21st International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2015
Country/Territory	New Zealand
City	Auckland
Period	29/11/15 → 3/12/15

Keywords

Design principles
Digital signatures
HFEv-
Multivariate cryptography
Performance
Security

Access to Document

10.1007/978-3-662-48797-6_14

Cite this

Petzoldt, A., Chen, M. S., Yang, B. Y., Tao, C., & Ding, J. (2015). Design principles for HFEV-based multivariate signature schemes. In J. H. Cheon, & T. Iwata (Eds.), Advances in Cryptology - ASIACRYPT 2015 - 21st International Conference on the Theory and Application of Cryptology and Information Security, 2015, Proceedings (pp. 311-334). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9452). Springer Verlag. https://doi.org/10.1007/978-3-662-48797-6_14

Petzoldt, Albrecht ; Chen, Ming Shing ; Yang, Bo Yin et al. / Design principles for HFEV-based multivariate signature schemes. Advances in Cryptology - ASIACRYPT 2015 - 21st International Conference on the Theory and Application of Cryptology and Information Security, 2015, Proceedings. editor / Jung Hee Cheon ; Tetsu Iwata. Springer Verlag, 2015. pp. 311-334 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{a522d01624414cc9b43236c7103d732d,

title = "Design principles for HFEV-based multivariate signature schemes",

abstract = "The Hidden Field Equations (HFE) Cryptosystem as proposed by Patarin is one of the best known and most studied multivariate schemes. While the security of the basic scheme a eared to be very weak, the HFEv-variant seems to be a good candidate for digital signature schemes on the basis of multivariate olynomials. However, the currently existing scheme of this type, the QUARTZ signature scheme, is hardly used in ractice because of its oor efficiency. In this a er we analyze recent results from Ding and Yang about the degree of regularity of HFEv-systems and derive from them design principles for signature schemes of the HFEv-type. Based on these results we propose the new HFEv-based signature scheme Gui, which is more than 100 times faster than QUARTZ and therefore highly com arable with classical signature schemes such as RSA and ECDSA.",

keywords = "Design principles, Digital signatures, HFEv-, Multivariate cryptography, Performance, Security",

author = "Albrecht Petzoldt and Chen, {Ming Shing} and Yang, {Bo Yin} and Chengdong Tao and Jintai Ding",

note = "Publisher Copyright: {\textcopyright}International Association for Cryptologic Research 2015.; 21st International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2015 ; Conference date: 29-11-2015 Through 03-12-2015",

year = "2015",

doi = "10.1007/978-3-662-48797-6_14",

language = "English",

isbn = "9783662487969",

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

publisher = "Springer Verlag",

pages = "311--334",

editor = "Cheon, {Jung Hee} and Tetsu Iwata",

booktitle = "Advances in Cryptology - ASIACRYPT 2015 - 21st International Conference on the Theory and Application of Cryptology and Information Security, 2015, Proceedings",

}

Petzoldt, A, Chen, MS, Yang, BY, Tao, C & Ding, J 2015, Design principles for HFEV-based multivariate signature schemes. in JH Cheon & T Iwata (eds), Advances in Cryptology - ASIACRYPT 2015 - 21st International Conference on the Theory and Application of Cryptology and Information Security, 2015, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9452, Springer Verlag, pp. 311-334, 21st International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2015, Auckland, New Zealand, 29/11/15. https://doi.org/10.1007/978-3-662-48797-6_14

Design principles for HFEV-based multivariate signature schemes. / Petzoldt, Albrecht; Chen, Ming Shing; Yang, Bo Yin et al.
Advances in Cryptology - ASIACRYPT 2015 - 21st International Conference on the Theory and Application of Cryptology and Information Security, 2015, Proceedings. ed. / Jung Hee Cheon; Tetsu Iwata. Springer Verlag, 2015. p. 311-334 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9452).

Research output: Chapter in Book or Report/Conference proceeding › Conference Proceeding › peer-review

TY - GEN

T1 - Design principles for HFEV-based multivariate signature schemes

AU - Petzoldt, Albrecht

AU - Chen, Ming Shing

AU - Yang, Bo Yin

AU - Tao, Chengdong

AU - Ding, Jintai

N1 - Publisher Copyright: ©International Association for Cryptologic Research 2015.

PY - 2015

Y1 - 2015

N2 - The Hidden Field Equations (HFE) Cryptosystem as proposed by Patarin is one of the best known and most studied multivariate schemes. While the security of the basic scheme a eared to be very weak, the HFEv-variant seems to be a good candidate for digital signature schemes on the basis of multivariate olynomials. However, the currently existing scheme of this type, the QUARTZ signature scheme, is hardly used in ractice because of its oor efficiency. In this a er we analyze recent results from Ding and Yang about the degree of regularity of HFEv-systems and derive from them design principles for signature schemes of the HFEv-type. Based on these results we propose the new HFEv-based signature scheme Gui, which is more than 100 times faster than QUARTZ and therefore highly com arable with classical signature schemes such as RSA and ECDSA.

AB - The Hidden Field Equations (HFE) Cryptosystem as proposed by Patarin is one of the best known and most studied multivariate schemes. While the security of the basic scheme a eared to be very weak, the HFEv-variant seems to be a good candidate for digital signature schemes on the basis of multivariate olynomials. However, the currently existing scheme of this type, the QUARTZ signature scheme, is hardly used in ractice because of its oor efficiency. In this a er we analyze recent results from Ding and Yang about the degree of regularity of HFEv-systems and derive from them design principles for signature schemes of the HFEv-type. Based on these results we propose the new HFEv-based signature scheme Gui, which is more than 100 times faster than QUARTZ and therefore highly com arable with classical signature schemes such as RSA and ECDSA.

KW - Design principles

KW - Digital signatures

KW - HFEv-

KW - Multivariate cryptography

KW - Performance

KW - Security

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

U2 - 10.1007/978-3-662-48797-6_14

DO - 10.1007/978-3-662-48797-6_14

M3 - Conference Proceeding

AN - SCOPUS:84961251294

SN - 9783662487969

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

SP - 311

EP - 334

BT - Advances in Cryptology - ASIACRYPT 2015 - 21st International Conference on the Theory and Application of Cryptology and Information Security, 2015, Proceedings

A2 - Cheon, Jung Hee

A2 - Iwata, Tetsu

PB - Springer Verlag

T2 - 21st International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2015

Y2 - 29 November 2015 through 3 December 2015

ER -

Petzoldt A, Chen MS, Yang BY, Tao C, Ding J. Design principles for HFEV-based multivariate signature schemes. In Cheon JH, Iwata T, editors, Advances in Cryptology - ASIACRYPT 2015 - 21st International Conference on the Theory and Application of Cryptology and Information Security, 2015, Proceedings. Springer Verlag. 2015. p. 311-334. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-662-48797-6_14

Design principles for HFEV-based multivariate signature schemes

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this