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

Shigeo TSUJII  Kohtaro TADAKI  Ryou FUJITA  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E90-A   No.5   pp.992-999
Publication Date: 2007/05/01
Online ISSN: 1745-1337
DOI: 10.1093/ietfec/e90-a.5.992
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
public key cryptosystem,  multivariate polynomial,  multivariate public key cryptosystem,  piece in hand concept,  soldiers in hand,  

Full Text: PDF(242.5KB)>>
Buy this Article




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.