High Order Linearization Equation (HOLE) attack on multivariate public key cryptosystems

Jintai Ding; Lei Hu; Xuyun Nie; Jianyu Li; John Wagner

doi:10.1007/978-3-540-71677-8_16

High Order Linearization Equation (HOLE) attack on multivariate public key cryptosystems

Jintai Ding^*, Lei Hu, Xuyun Nie, Jianyu Li, John Wagner

^*Corresponding author for this work

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

44 Citations (Scopus)

Abstract

In the CT-track of the 2006 RSA conference, a new multivariate public key cryptosystem, which is called the Medium Field Equation (MFE) multivariate public key cryptosystem, is proposed by Wang, Yang, Hu and Lai. We use the second order linearization equation attack method by Patarin to break MFE. Given a ciphertext, we can derive the plaintext within 2²³ double-struck F sign₂₁₅ -multiplications, after performing once for any given public key a computation of complexity less than 2⁵². We also propose a high order linearization equation (HOLE) attack on multivariate public key cryptosystems, which is a further generalization of the (first and second order) linearization equation (LE). This method can be used to attack extensions of the current MFE.

Original language	English
Title of host publication	Public Key Cryptography - PKC 2007 - 10th International Conference on Practice and Theory in Public-Key Cryptography, Proceedings
Publisher	Springer Verlag
Pages	233-248
Number of pages	16
ISBN (Print)	9783540716761
DOIs	https://doi.org/10.1007/978-3-540-71677-8_16
Publication status	Published - 2007
Externally published	Yes
Event	10th International Conference on Theory and Practice in Public-Key Cryptography, PKC 2007 - Beijing, China Duration: 16 Apr 2007 → 20 Apr 2007

Publication series

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

Conference

Conference	10th International Conference on Theory and Practice in Public-Key Cryptography, PKC 2007
Country/Territory	China
City	Beijing
Period	16/04/07 → 20/04/07

Keywords

Algebraic cryptanalysis
High order linearization equation
Multivariate public key cryptosystem
Quadratic polynomial

Access to Document

10.1007/978-3-540-71677-8_16

Cite this

Ding, J., Hu, L., Nie, X., Li, J., & Wagner, J. (2007). High Order Linearization Equation (HOLE) attack on multivariate public key cryptosystems. In Public Key Cryptography - PKC 2007 - 10th International Conference on Practice and Theory in Public-Key Cryptography, Proceedings (pp. 233-248). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4450 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-540-71677-8_16

Ding, Jintai ; Hu, Lei ; Nie, Xuyun et al. / High Order Linearization Equation (HOLE) attack on multivariate public key cryptosystems. Public Key Cryptography - PKC 2007 - 10th International Conference on Practice and Theory in Public-Key Cryptography, Proceedings. Springer Verlag, 2007. pp. 233-248 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{df25d0b2cc67455595151ac7085d436c,

title = "High Order Linearization Equation (HOLE) attack on multivariate public key cryptosystems",

abstract = "In the CT-track of the 2006 RSA conference, a new multivariate public key cryptosystem, which is called the Medium Field Equation (MFE) multivariate public key cryptosystem, is proposed by Wang, Yang, Hu and Lai. We use the second order linearization equation attack method by Patarin to break MFE. Given a ciphertext, we can derive the plaintext within 223 double-struck F sign215 -multiplications, after performing once for any given public key a computation of complexity less than 252. We also propose a high order linearization equation (HOLE) attack on multivariate public key cryptosystems, which is a further generalization of the (first and second order) linearization equation (LE). This method can be used to attack extensions of the current MFE.",

keywords = "Algebraic cryptanalysis, High order linearization equation, Multivariate public key cryptosystem, Quadratic polynomial",

author = "Jintai Ding and Lei Hu and Xuyun Nie and Jianyu Li and John Wagner",

year = "2007",

doi = "10.1007/978-3-540-71677-8_16",

language = "English",

isbn = "9783540716761",

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

publisher = "Springer Verlag",

pages = "233--248",

booktitle = "Public Key Cryptography - PKC 2007 - 10th International Conference on Practice and Theory in Public-Key Cryptography, Proceedings",

note = "10th International Conference on Theory and Practice in Public-Key Cryptography, PKC 2007 ; Conference date: 16-04-2007 Through 20-04-2007",

}

Ding, J, Hu, L, Nie, X, Li, J & Wagner, J 2007, High Order Linearization Equation (HOLE) attack on multivariate public key cryptosystems. in Public Key Cryptography - PKC 2007 - 10th International Conference on Practice and Theory in Public-Key Cryptography, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4450 LNCS, Springer Verlag, pp. 233-248, 10th International Conference on Theory and Practice in Public-Key Cryptography, PKC 2007, Beijing, China, 16/04/07. https://doi.org/10.1007/978-3-540-71677-8_16

High Order Linearization Equation (HOLE) attack on multivariate public key cryptosystems. / Ding, Jintai; Hu, Lei; Nie, Xuyun et al.
Public Key Cryptography - PKC 2007 - 10th International Conference on Practice and Theory in Public-Key Cryptography, Proceedings. Springer Verlag, 2007. p. 233-248 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4450 LNCS).

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

TY - GEN

T1 - High Order Linearization Equation (HOLE) attack on multivariate public key cryptosystems

AU - Ding, Jintai

AU - Hu, Lei

AU - Nie, Xuyun

AU - Li, Jianyu

AU - Wagner, John

PY - 2007

Y1 - 2007

N2 - In the CT-track of the 2006 RSA conference, a new multivariate public key cryptosystem, which is called the Medium Field Equation (MFE) multivariate public key cryptosystem, is proposed by Wang, Yang, Hu and Lai. We use the second order linearization equation attack method by Patarin to break MFE. Given a ciphertext, we can derive the plaintext within 223 double-struck F sign215 -multiplications, after performing once for any given public key a computation of complexity less than 252. We also propose a high order linearization equation (HOLE) attack on multivariate public key cryptosystems, which is a further generalization of the (first and second order) linearization equation (LE). This method can be used to attack extensions of the current MFE.

AB - In the CT-track of the 2006 RSA conference, a new multivariate public key cryptosystem, which is called the Medium Field Equation (MFE) multivariate public key cryptosystem, is proposed by Wang, Yang, Hu and Lai. We use the second order linearization equation attack method by Patarin to break MFE. Given a ciphertext, we can derive the plaintext within 223 double-struck F sign215 -multiplications, after performing once for any given public key a computation of complexity less than 252. We also propose a high order linearization equation (HOLE) attack on multivariate public key cryptosystems, which is a further generalization of the (first and second order) linearization equation (LE). This method can be used to attack extensions of the current MFE.

KW - Algebraic cryptanalysis

KW - High order linearization equation

KW - Multivariate public key cryptosystem

KW - Quadratic polynomial

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

U2 - 10.1007/978-3-540-71677-8_16

DO - 10.1007/978-3-540-71677-8_16

M3 - Conference Proceeding

AN - SCOPUS:38049027287

SN - 9783540716761

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

SP - 233

EP - 248

BT - Public Key Cryptography - PKC 2007 - 10th International Conference on Practice and Theory in Public-Key Cryptography, Proceedings

PB - Springer Verlag

T2 - 10th International Conference on Theory and Practice in Public-Key Cryptography, PKC 2007

Y2 - 16 April 2007 through 20 April 2007

ER -

Ding J, Hu L, Nie X, Li J, Wagner J. High Order Linearization Equation (HOLE) attack on multivariate public key cryptosystems. In Public Key Cryptography - PKC 2007 - 10th International Conference on Practice and Theory in Public-Key Cryptography, Proceedings. Springer Verlag. 2007. p. 233-248. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-71677-8_16

High Order Linearization Equation (HOLE) attack on multivariate public key cryptosystems

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this