International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Shigeo Tsujii
Kohtaro Tadaki
Ryou Fujita
Download:
URL: http://eprint.iacr.org/2006/051
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-2006-21544,
  title={Proposal for Piece In Hand Matrix Ver.2: General Concept 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/2006/051},
  note={ tadaki@kc.chuo-u.ac.jp 13192 received 13 Feb 2006},
  author={Shigeo Tsujii and Kohtaro Tadaki and Ryou Fujita},
  year=2006
}