Cryptanalysis of rational multivariate public key cryptosystems

Jintai Ding; John Wagner

doi:10.1007/978-3-540-88403-3_9

Cryptanalysis of rational multivariate public key cryptosystems

Jintai Ding^*, John Wagner

^*Corresponding author for this work

University of Cincinnati

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

5 Citations (Scopus)

Abstract

In 1989, Tsujii, Fujioka, and Hirayama proposed a family of multivariate public key cryptosystems, where the public key is given as a set of multivariate rational functions of degree 4. These cryptosystems are constructed via composition of two quadratic rational maps. In this paper, we present the cryptanalysis of this family of cryptosystems. The key point of our attack is to transform a problem of decomposition of two rational maps into a problem of decomposition of two polynomial maps. We develop a new improved 2R decomposition method and other new techniques, which allows us to find an equivalent decomposition of the rational maps to break the system completely. For the example suggested for practical applications, it is very fast to derive an equivalent private key, and it requires only a few seconds on a standard PC.

Original language	English
Title of host publication	Post-Quantum Cryptography - Second International Workshop, PQCrypto 2008, Proceedings
Publisher	Springer Verlag
Pages	124-136
Number of pages	13
ISBN (Print)	3540884025, 9783540884026
DOIs	https://doi.org/10.1007/978-3-540-88403-3_9
Publication status	Published - 2008
Externally published	Yes
Event	2nd International Workshop on Post-Quantum Cryptography, PQCrypto 2008 - Cincinnati, OH, United States Duration: 17 Oct 2008 → 19 Oct 2008

Publication series

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

Conference

Conference	2nd International Workshop on Post-Quantum Cryptography, PQCrypto 2008
Country/Territory	United States
City	Cincinnati, OH
Period	17/10/08 → 19/10/08

Access to Document

10.1007/978-3-540-88403-3_9

Cite this

Ding, J., & Wagner, J. (2008). Cryptanalysis of rational multivariate public key cryptosystems. In Post-Quantum Cryptography - Second International Workshop, PQCrypto 2008, Proceedings (pp. 124-136). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5299 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-540-88403-3_9

@inproceedings{7ca8f8e29eae468aab8667a67a94e5ce,

title = "Cryptanalysis of rational multivariate public key cryptosystems",

abstract = "In 1989, Tsujii, Fujioka, and Hirayama proposed a family of multivariate public key cryptosystems, where the public key is given as a set of multivariate rational functions of degree 4. These cryptosystems are constructed via composition of two quadratic rational maps. In this paper, we present the cryptanalysis of this family of cryptosystems. The key point of our attack is to transform a problem of decomposition of two rational maps into a problem of decomposition of two polynomial maps. We develop a new improved 2R decomposition method and other new techniques, which allows us to find an equivalent decomposition of the rational maps to break the system completely. For the example suggested for practical applications, it is very fast to derive an equivalent private key, and it requires only a few seconds on a standard PC.",

author = "Jintai Ding and John Wagner",

year = "2008",

doi = "10.1007/978-3-540-88403-3_9",

language = "English",

isbn = "3540884025",

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

publisher = "Springer Verlag",

pages = "124--136",

booktitle = "Post-Quantum Cryptography - Second International Workshop, PQCrypto 2008, Proceedings",

note = "2nd International Workshop on Post-Quantum Cryptography, PQCrypto 2008 ; Conference date: 17-10-2008 Through 19-10-2008",

}

Ding, J & Wagner, J 2008, Cryptanalysis of rational multivariate public key cryptosystems. in Post-Quantum Cryptography - Second International Workshop, PQCrypto 2008, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5299 LNCS, Springer Verlag, pp. 124-136, 2nd International Workshop on Post-Quantum Cryptography, PQCrypto 2008, Cincinnati, OH, United States, 17/10/08. https://doi.org/10.1007/978-3-540-88403-3_9

Cryptanalysis of rational multivariate public key cryptosystems. / Ding, Jintai; Wagner, John.
Post-Quantum Cryptography - Second International Workshop, PQCrypto 2008, Proceedings. Springer Verlag, 2008. p. 124-136 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5299 LNCS).

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

TY - GEN

T1 - Cryptanalysis of rational multivariate public key cryptosystems

AU - Ding, Jintai

AU - Wagner, John

PY - 2008

Y1 - 2008

N2 - In 1989, Tsujii, Fujioka, and Hirayama proposed a family of multivariate public key cryptosystems, where the public key is given as a set of multivariate rational functions of degree 4. These cryptosystems are constructed via composition of two quadratic rational maps. In this paper, we present the cryptanalysis of this family of cryptosystems. The key point of our attack is to transform a problem of decomposition of two rational maps into a problem of decomposition of two polynomial maps. We develop a new improved 2R decomposition method and other new techniques, which allows us to find an equivalent decomposition of the rational maps to break the system completely. For the example suggested for practical applications, it is very fast to derive an equivalent private key, and it requires only a few seconds on a standard PC.

AB - In 1989, Tsujii, Fujioka, and Hirayama proposed a family of multivariate public key cryptosystems, where the public key is given as a set of multivariate rational functions of degree 4. These cryptosystems are constructed via composition of two quadratic rational maps. In this paper, we present the cryptanalysis of this family of cryptosystems. The key point of our attack is to transform a problem of decomposition of two rational maps into a problem of decomposition of two polynomial maps. We develop a new improved 2R decomposition method and other new techniques, which allows us to find an equivalent decomposition of the rational maps to break the system completely. For the example suggested for practical applications, it is very fast to derive an equivalent private key, and it requires only a few seconds on a standard PC.

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

U2 - 10.1007/978-3-540-88403-3_9

DO - 10.1007/978-3-540-88403-3_9

M3 - Conference Proceeding

AN - SCOPUS:56749105660

SN - 3540884025

SN - 9783540884026

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

SP - 124

EP - 136

BT - Post-Quantum Cryptography - Second International Workshop, PQCrypto 2008, Proceedings

PB - Springer Verlag

T2 - 2nd International Workshop on Post-Quantum Cryptography, PQCrypto 2008

Y2 - 17 October 2008 through 19 October 2008

ER -

Ding J, Wagner J. Cryptanalysis of rational multivariate public key cryptosystems. In Post-Quantum Cryptography - Second International Workshop, PQCrypto 2008, Proceedings. Springer Verlag. 2008. p. 124-136. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-88403-3_9

Cryptanalysis of rational multivariate public key cryptosystems

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this