Cryptanalysis of the TRMC-4 public key cryptosystem

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

doi:10.1007/978-3-540-72738-5_7

Cryptanalysis of the TRMC-4 public key cryptosystem

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

^*Corresponding author for this work

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

1 Citation (Scopus)

Abstract

In 2006, the inventors of TRMC public key cryptosystem proposed a new variant of TRMC, TRMC-4, which can resist the existing attack, in particular, the Joux et al attack. In this paper, we show that the new version is vulnerable to attack via the linearization equations (LE) method. For any given valid ciphertext and its corresponding TRMC-4 public key, we can derive the corresponding plaintext within 2²⁴ double-struck F sign ₂₈-operations, after performing once for the public key a computation of complexity less than 2³⁴. Our results are confirmed by computer experiments.

Original language	English
Title of host publication	Applied Cryptography and Network Security - 5th International Conference, ACNS 2007, Proceedings
Publisher	Springer Verlag
Pages	104-115
Number of pages	12
ISBN (Print)	9783540727378
DOIs	https://doi.org/10.1007/978-3-540-72738-5_7
Publication status	Published - 2007
Externally published	Yes
Event	5th International Conference on Applied Cryptography and Network Security, ACNS 2007 - Zhuhai, China Duration: 5 Jun 2007 → 8 Jun 2007

Publication series

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

Conference

Conference	5th International Conference on Applied Cryptography and Network Security, ACNS 2007
Country/Territory	China
City	Zhuhai
Period	5/06/07 → 8/06/07

Keywords

Algebraic cryptanalysis
Linearization equation
Multivariate public key cryptosystem
Quadratic polynomial
TRMC

Access to Document

10.1007/978-3-540-72738-5_7

Cite this

Nie, X., Hu, L., Ding, J., Li, J., & Wagner, J. (2007). Cryptanalysis of the TRMC-4 public key cryptosystem. In Applied Cryptography and Network Security - 5th International Conference, ACNS 2007, Proceedings (pp. 104-115). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4521 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-540-72738-5_7

@inproceedings{767bffb700c84ca8adf176870c26b425,

title = "Cryptanalysis of the TRMC-4 public key cryptosystem",

abstract = "In 2006, the inventors of TRMC public key cryptosystem proposed a new variant of TRMC, TRMC-4, which can resist the existing attack, in particular, the Joux et al attack. In this paper, we show that the new version is vulnerable to attack via the linearization equations (LE) method. For any given valid ciphertext and its corresponding TRMC-4 public key, we can derive the corresponding plaintext within 224 double-struck F sign 28-operations, after performing once for the public key a computation of complexity less than 234. Our results are confirmed by computer experiments.",

keywords = "Algebraic cryptanalysis, Linearization equation, Multivariate public key cryptosystem, Quadratic polynomial, TRMC",

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

year = "2007",

doi = "10.1007/978-3-540-72738-5_7",

language = "English",

isbn = "9783540727378",

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

publisher = "Springer Verlag",

pages = "104--115",

booktitle = "Applied Cryptography and Network Security - 5th International Conference, ACNS 2007, Proceedings",

note = "5th International Conference on Applied Cryptography and Network Security, ACNS 2007 ; Conference date: 05-06-2007 Through 08-06-2007",

}

Nie, X, Hu, L, Ding, J, Li, J & Wagner, J 2007, Cryptanalysis of the TRMC-4 public key cryptosystem. in Applied Cryptography and Network Security - 5th International Conference, ACNS 2007, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4521 LNCS, Springer Verlag, pp. 104-115, 5th International Conference on Applied Cryptography and Network Security, ACNS 2007, Zhuhai, China, 5/06/07. https://doi.org/10.1007/978-3-540-72738-5_7

Cryptanalysis of the TRMC-4 public key cryptosystem. / Nie, Xuyun; Hu, Lei; Ding, Jintai et al.
Applied Cryptography and Network Security - 5th International Conference, ACNS 2007, Proceedings. Springer Verlag, 2007. p. 104-115 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4521 LNCS).

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

TY - GEN

T1 - Cryptanalysis of the TRMC-4 public key cryptosystem

AU - Nie, Xuyun

AU - Hu, Lei

AU - Ding, Jintai

AU - Li, Jianyu

AU - Wagner, John

PY - 2007

Y1 - 2007

N2 - In 2006, the inventors of TRMC public key cryptosystem proposed a new variant of TRMC, TRMC-4, which can resist the existing attack, in particular, the Joux et al attack. In this paper, we show that the new version is vulnerable to attack via the linearization equations (LE) method. For any given valid ciphertext and its corresponding TRMC-4 public key, we can derive the corresponding plaintext within 224 double-struck F sign 28-operations, after performing once for the public key a computation of complexity less than 234. Our results are confirmed by computer experiments.

AB - In 2006, the inventors of TRMC public key cryptosystem proposed a new variant of TRMC, TRMC-4, which can resist the existing attack, in particular, the Joux et al attack. In this paper, we show that the new version is vulnerable to attack via the linearization equations (LE) method. For any given valid ciphertext and its corresponding TRMC-4 public key, we can derive the corresponding plaintext within 224 double-struck F sign 28-operations, after performing once for the public key a computation of complexity less than 234. Our results are confirmed by computer experiments.

KW - Algebraic cryptanalysis

KW - Linearization equation

KW - Multivariate public key cryptosystem

KW - Quadratic polynomial

KW - TRMC

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

U2 - 10.1007/978-3-540-72738-5_7

DO - 10.1007/978-3-540-72738-5_7

M3 - Conference Proceeding

AN - SCOPUS:38049044803

SN - 9783540727378

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

SP - 104

EP - 115

BT - Applied Cryptography and Network Security - 5th International Conference, ACNS 2007, Proceedings

PB - Springer Verlag

T2 - 5th International Conference on Applied Cryptography and Network Security, ACNS 2007

Y2 - 5 June 2007 through 8 June 2007

ER -

Nie X, Hu L, Ding J, Li J, Wagner J. Cryptanalysis of the TRMC-4 public key cryptosystem. In Applied Cryptography and Network Security - 5th International Conference, ACNS 2007, Proceedings. Springer Verlag. 2007. p. 104-115. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-72738-5_7

Cryptanalysis of the TRMC-4 public key cryptosystem

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this