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

*Shigeo Tsujii and 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\"obner basis attack.

**Category / Keywords: **public-key cryptography / public key cryptosystem, multivariate polynomial, multivariate public key cryptosystem

**Date: **received 19 Feb 2008

**Contact author: **tsujii at iisec ac jp

**Available format(s): **PDF | BibTeX Citation

**Version: **20080227:044222 (All versions of this report)

**Short URL: **ia.cr/2008/077

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]