Cryptology ePrint Archive: Report 2006/051

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

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

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

Date: received 13 Feb 2006

Contact author: tadaki at kc chuo-u ac jp

Available format(s): PDF | BibTeX Citation

Version: 20060214:163003 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]