Paper 2006/051

Proposal for Piece In Hand Matrix Ver.2: General Concept for Enhancing Security of Multivariate Public Key Cryptosystems

Shigeo Tsujii, Kohtaro Tadaki, and Ryou Fujita

Abstract

We proposed the concept, piece in hand (soldiers in hand) matrix and have developed the framework based on the concept so far. The piece in hand matrix is a general concept which can be applicable to any type of multivariate public key cryptosystems to enhance their security. In this paper, we make improvements in the PH matrix method as follows. (i) In the PH matrix method, an arbitrary number of additional variables can be introduced to the random polynomial term in the public key, which is eliminated by the multiplication of the PH matrix to the public key in the decryption. Thus these additional variables enables the public key to have more than one solution, and therefore increases the difficulty to solve the public key. We show, in an experimental manner, that the PH matrix method improved in this way is secure even against the Gröbner basis attack. (ii) In the nonlinear PH matrix method proposed previously, the degree of polynomials in the public key is more than two, and this may cause an undesirable increase in the length of the public key. In this paper, we propose a nonlinear PH matrix method, where the degree of the public key is kept the same as the degree of the public key of the original cryptosystem, which is normally two.