International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Nonlinear Piece In Hand Matrix Method for Enhancing Security of Multivariate Public Key Cryptosystems

Authors:
Shigeo Tsujii
Kohtaro Tadaki
Ryou Fujita
Download:
URL: http://eprint.iacr.org/2008/077
Search ePrint
Search Google
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 apt to be polynomial time due to the trapdoor structure. In this paper, we develop the concept, piece in hand matrix (PH matrix, for short), which aims to bring 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 reasonable type of multivariate public key cryptosystems for the purpose of enhancing their security. There are two types of the PH matrices: a linear matrix whose elements are constants and a nonlinear matrix whose elements are polynomial functions of the plain text or random numbers. In the present paper, we focus our thought on the nonlinear PH matrix method and develop the framework of it. The nonlinear PH matrix method is obtained by generalizing the linear PH matrix method, and the nonlinearity may bring an additional randomization to the original linear PH matrix method. Thus, the nonlinear PH matrix method may enhance the security of the original multivariate public key cryptosystem more than the linear PH matrix method. We show, in an experimental manner, that this actually holds in the enhancement of the security of the Matsumoto-Imai cryptosystem and RSE(2)PKC against the Gr\"obner basis attack.
BibTeX
@misc{eprint-2008-17754,
  title={Nonlinear Piece In Hand Matrix Method for Enhancing Security of Multivariate Public Key Cryptosystems},
  booktitle={IACR Eprint archive},
  keywords={public-key cryptography / public key cryptosystem, multivariate polynomial, multivariate public key cryptosystem},
  url={http://eprint.iacr.org/2008/077},
  note={ tsujii@iisec.ac.jp 13929 received 19 Feb 2008},
  author={Shigeo Tsujii and Kohtaro Tadaki and Ryou Fujita},
  year=2008
}