Improved cryptanalysis of HFEv- via projection

Jintai Ding; Ray Perlner; Albrecht Petzoldt; Daniel Smith-Tone

doi:10.1007/978-3-319-79063-3_18

Improved cryptanalysis of HFEv- via projection

Jintai Ding, Ray Perlner, Albrecht Petzoldt, Daniel Smith-Tone^*

^*Corresponding author for this work

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

8 Citations (Scopus)

Abstract

The HFEv- signature scheme is one of the most studied multivariate schemes and one of the major candidates for the upcoming standardization of post-quantum digital signature schemes. In this paper, we propose three new attack strategies against HFEv-, each of them using the idea of projection. Especially our third attack is very effective and is, for some parameter sets, the most efficient known attack against HFEv-. Furthermore, our attack requires much less memory than direct and rank attacks. By our work, we therefore give new insights in the security of the HFEv- signature scheme and restrictions for the parameter choice of a possible future standardized HFEv- instance.

Original language	English
Title of host publication	Post-Quantum Cryptography - 9th International Conference, PQCrypto 2018, Proceedings
Editors	Tanja Lange, Rainer Steinwandt
Publisher	Springer Verlag
Pages	375-395
Number of pages	21
ISBN (Print)	9783319790626
DOIs	https://doi.org/10.1007/978-3-319-79063-3_18
Publication status	Published - 2018
Externally published	Yes
Event	9th International Conference on Post-Quantum Cryptography, PQCrypto 2018 - Fort Lauderdale, United States Duration: 9 Apr 2018 → 11 Apr 2018

Publication series

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

Conference

Conference	9th International Conference on Post-Quantum Cryptography, PQCrypto 2018
Country/Territory	United States
City	Fort Lauderdale
Period	9/04/18 → 11/04/18

Keywords

Gröbner basis
HFEv-
MinRank
Multivariate cryptography
Projection

Access to Document

10.1007/978-3-319-79063-3_18

Cite this

Ding, J., Perlner, R., Petzoldt, A., & Smith-Tone, D. (2018). Improved cryptanalysis of HFEv- via projection. In T. Lange, & R. Steinwandt (Eds.), Post-Quantum Cryptography - 9th International Conference, PQCrypto 2018, Proceedings (pp. 375-395). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10786 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-79063-3_18

Ding, Jintai ; Perlner, Ray ; Petzoldt, Albrecht et al. / Improved cryptanalysis of HFEv- via projection. Post-Quantum Cryptography - 9th International Conference, PQCrypto 2018, Proceedings. editor / Tanja Lange ; Rainer Steinwandt. Springer Verlag, 2018. pp. 375-395 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{c38b2cbec7d841b7a5c88257d7499ac8,

title = "Improved cryptanalysis of HFEv- via projection",

abstract = "The HFEv- signature scheme is one of the most studied multivariate schemes and one of the major candidates for the upcoming standardization of post-quantum digital signature schemes. In this paper, we propose three new attack strategies against HFEv-, each of them using the idea of projection. Especially our third attack is very effective and is, for some parameter sets, the most efficient known attack against HFEv-. Furthermore, our attack requires much less memory than direct and rank attacks. By our work, we therefore give new insights in the security of the HFEv- signature scheme and restrictions for the parameter choice of a possible future standardized HFEv- instance.",

keywords = "Gr{\"o}bner basis, HFEv-, MinRank, Multivariate cryptography, Projection",

author = "Jintai Ding and Ray Perlner and Albrecht Petzoldt and Daniel Smith-Tone",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing AG, part of Springer Nature 2018.; 9th International Conference on Post-Quantum Cryptography, PQCrypto 2018 ; Conference date: 09-04-2018 Through 11-04-2018",

year = "2018",

doi = "10.1007/978-3-319-79063-3_18",

language = "English",

isbn = "9783319790626",

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

publisher = "Springer Verlag",

pages = "375--395",

editor = "Tanja Lange and Rainer Steinwandt",

booktitle = "Post-Quantum Cryptography - 9th International Conference, PQCrypto 2018, Proceedings",

}

Ding, J, Perlner, R, Petzoldt, A & Smith-Tone, D 2018, Improved cryptanalysis of HFEv- via projection. in T Lange & R Steinwandt (eds), Post-Quantum Cryptography - 9th International Conference, PQCrypto 2018, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10786 LNCS, Springer Verlag, pp. 375-395, 9th International Conference on Post-Quantum Cryptography, PQCrypto 2018, Fort Lauderdale, United States, 9/04/18. https://doi.org/10.1007/978-3-319-79063-3_18

Improved cryptanalysis of HFEv- via projection. / Ding, Jintai; Perlner, Ray; Petzoldt, Albrecht et al.
Post-Quantum Cryptography - 9th International Conference, PQCrypto 2018, Proceedings. ed. / Tanja Lange; Rainer Steinwandt. Springer Verlag, 2018. p. 375-395 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10786 LNCS).

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

TY - GEN

T1 - Improved cryptanalysis of HFEv- via projection

AU - Ding, Jintai

AU - Perlner, Ray

AU - Petzoldt, Albrecht

AU - Smith-Tone, Daniel

N1 - Publisher Copyright: © Springer International Publishing AG, part of Springer Nature 2018.

PY - 2018

Y1 - 2018

N2 - The HFEv- signature scheme is one of the most studied multivariate schemes and one of the major candidates for the upcoming standardization of post-quantum digital signature schemes. In this paper, we propose three new attack strategies against HFEv-, each of them using the idea of projection. Especially our third attack is very effective and is, for some parameter sets, the most efficient known attack against HFEv-. Furthermore, our attack requires much less memory than direct and rank attacks. By our work, we therefore give new insights in the security of the HFEv- signature scheme and restrictions for the parameter choice of a possible future standardized HFEv- instance.

AB - The HFEv- signature scheme is one of the most studied multivariate schemes and one of the major candidates for the upcoming standardization of post-quantum digital signature schemes. In this paper, we propose three new attack strategies against HFEv-, each of them using the idea of projection. Especially our third attack is very effective and is, for some parameter sets, the most efficient known attack against HFEv-. Furthermore, our attack requires much less memory than direct and rank attacks. By our work, we therefore give new insights in the security of the HFEv- signature scheme and restrictions for the parameter choice of a possible future standardized HFEv- instance.

KW - Gröbner basis

KW - HFEv-

KW - MinRank

KW - Multivariate cryptography

KW - Projection

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

U2 - 10.1007/978-3-319-79063-3_18

DO - 10.1007/978-3-319-79063-3_18

M3 - Conference Proceeding

AN - SCOPUS:85045382143

SN - 9783319790626

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

SP - 375

EP - 395

BT - Post-Quantum Cryptography - 9th International Conference, PQCrypto 2018, Proceedings

A2 - Lange, Tanja

A2 - Steinwandt, Rainer

PB - Springer Verlag

T2 - 9th International Conference on Post-Quantum Cryptography, PQCrypto 2018

Y2 - 9 April 2018 through 11 April 2018

ER -

Ding J, Perlner R, Petzoldt A, Smith-Tone D. Improved cryptanalysis of HFEv- via projection. In Lange T, Steinwandt R, editors, Post-Quantum Cryptography - 9th International Conference, PQCrypto 2018, Proceedings. Springer Verlag. 2018. p. 375-395. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-79063-3_18

Improved cryptanalysis of HFEv- via projection

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this