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

Shigeo Tsujii, Kohtaro Tadaki, and Ryou Fujita

##### 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öbner basis attack.

Available format(s)
Category
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
public key cryptosystemmultivariate polynomialmultivariate public key cryptosystem
Contact author(s)
tsujii @ iisec ac jp
History
Short URL
https://ia.cr/2008/077

CC BY

BibTeX

@misc{cryptoeprint:2008/077,
author = {Shigeo Tsujii and Kohtaro Tadaki and Ryou Fujita},
title = {Nonlinear Piece In Hand Matrix Method for Enhancing Security of Multivariate Public Key Cryptosystems},
howpublished = {Cryptology ePrint Archive, Paper 2008/077},
year = {2008},
note = {\url{https://eprint.iacr.org/2008/077}},
url = {https://eprint.iacr.org/2008/077}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.