Proposal for Piece in Hand Matrix: General Concept for Enhancing Security of Multivariate Public Key Cryptosystems

Shigeo TSUJII; Kohtaro TADAKI; Ryou FUJITA

doi:10.1093/ietfec/e90-a.5.992

Proposal for Piece in Hand Matrix: General Concept for Enhancing Security of Multivariate Public Key Cryptosystems

Shigeo TSUJII, Kohtaro TADAKI, Ryou FUJITA

Full Text Views

0

Share
Cite this

Summary :

It is widely believed to take exponential time to find a solution of a system of random multivariate polynomials because of the NP-completeness of such a task. On the other hand, in most of multivariate public key cryptosystems proposed so far, the computational complexity of cryptanalysis is polynomial time due to the trapdoor structure. In this paper, we introduce a new concept, piece in hand (soldiers in hand) matrix, which brings the computational complexity of cryptanalysis of multivariate public key cryptosystems close to exponential time by adding random polynomial terms to original cryptosystems. This is a general concept which can be applicable to any type of multivariate public key cryptosystems for the purpose of enhancing their security. As an implementation of the concept, we propose the linear PH matrix method with random variables. In 2003 Faugere and Joux broke the first HFE challenge (80 bits), where HFE is one of the major variants of multivariate public key cryptosystem, by computing a Grobner basis of the public key of the cryptosystem. We show, in an experimental manner, that the linear PH matrix method with random variables can enhance the security of HFE even against the Grobner basis attack. In what follows, we consider the strength of the linear PH matrix method against other possible attacks.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E90-A No.5 pp.992-999

Publication Date: 2007/05/01

Publicized

Online ISSN: 1745-1337

DOI: 10.1093/ietfec/e90-a.5.992

Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)

Category

Cite this

Copy

Shigeo TSUJII, Kohtaro TADAKI, Ryou FUJITA, "Proposal for Piece in Hand Matrix: General Concept for Enhancing Security of Multivariate Public Key Cryptosystems" in IEICE TRANSACTIONS on Fundamentals, vol. E90-A, no. 5, pp. 992-999, May 2007, doi: 10.1093/ietfec/e90-a.5.992.
Abstract: It is widely believed to take exponential time to find a solution of a system of random multivariate polynomials because of the NP-completeness of such a task. On the other hand, in most of multivariate public key cryptosystems proposed so far, the computational complexity of cryptanalysis is polynomial time due to the trapdoor structure. In this paper, we introduce a new concept, piece in hand (soldiers in hand) matrix, which brings the computational complexity of cryptanalysis of multivariate public key cryptosystems close to exponential time by adding random polynomial terms to original cryptosystems. This is a general concept which can be applicable to any type of multivariate public key cryptosystems for the purpose of enhancing their security. As an implementation of the concept, we propose the linear PH matrix method with random variables. In 2003 Faugere and Joux broke the first HFE challenge (80 bits), where HFE is one of the major variants of multivariate public key cryptosystem, by computing a Grobner basis of the public key of the cryptosystem. We show, in an experimental manner, that the linear PH matrix method with random variables can enhance the security of HFE even against the Grobner basis attack. In what follows, we consider the strength of the linear PH matrix method against other possible attacks.
URL: https://globals.ieice.org/en_transactions/fundamentals/10.1093/ietfec/e90-a.5.992/_p

Copy

@ARTICLE{e90-a_5_992,
author={Shigeo TSUJII, Kohtaro TADAKI, Ryou FUJITA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Proposal for Piece in Hand Matrix: General Concept for Enhancing Security of Multivariate Public Key Cryptosystems},
year={2007},
volume={E90-A},
number={5},
pages={992-999},
abstract={It is widely believed to take exponential time to find a solution of a system of random multivariate polynomials because of the NP-completeness of such a task. On the other hand, in most of multivariate public key cryptosystems proposed so far, the computational complexity of cryptanalysis is polynomial time due to the trapdoor structure. In this paper, we introduce a new concept, piece in hand (soldiers in hand) matrix, which brings the computational complexity of cryptanalysis of multivariate public key cryptosystems close to exponential time by adding random polynomial terms to original cryptosystems. This is a general concept which can be applicable to any type of multivariate public key cryptosystems for the purpose of enhancing their security. As an implementation of the concept, we propose the linear PH matrix method with random variables. In 2003 Faugere and Joux broke the first HFE challenge (80 bits), where HFE is one of the major variants of multivariate public key cryptosystem, by computing a Grobner basis of the public key of the cryptosystem. We show, in an experimental manner, that the linear PH matrix method with random variables can enhance the security of HFE even against the Grobner basis attack. In what follows, we consider the strength of the linear PH matrix method against other possible attacks.},
keywords={},
doi={10.1093/ietfec/e90-a.5.992},
ISSN={1745-1337},
month={May},}

Copy

TY - JOUR
TI - Proposal for Piece in Hand Matrix: General Concept for Enhancing Security of Multivariate Public Key Cryptosystems
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 992
EP - 999
AU - Shigeo TSUJII
AU - Kohtaro TADAKI
AU - Ryou FUJITA
PY - 2007
DO - 10.1093/ietfec/e90-a.5.992
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E90-A
IS - 5
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - May 2007
AB - It is widely believed to take exponential time to find a solution of a system of random multivariate polynomials because of the NP-completeness of such a task. On the other hand, in most of multivariate public key cryptosystems proposed so far, the computational complexity of cryptanalysis is polynomial time due to the trapdoor structure. In this paper, we introduce a new concept, piece in hand (soldiers in hand) matrix, which brings the computational complexity of cryptanalysis of multivariate public key cryptosystems close to exponential time by adding random polynomial terms to original cryptosystems. This is a general concept which can be applicable to any type of multivariate public key cryptosystems for the purpose of enhancing their security. As an implementation of the concept, we propose the linear PH matrix method with random variables. In 2003 Faugere and Joux broke the first HFE challenge (80 bits), where HFE is one of the major variants of multivariate public key cryptosystem, by computing a Grobner basis of the public key of the cryptosystem. We show, in an experimental manner, that the linear PH matrix method with random variables can enhance the security of HFE even against the Grobner basis attack. In what follows, we consider the strength of the linear PH matrix method against other possible attacks.
ER -