A New Variant of the Matsumoto-Imai Cryptosystem through Perturbation

Jintai Ding Department of Mathematical Sciences, University of Cincinnati, Cincinnati, OH, 45220, USA

TBD mathscidoc:2207.43010

Public Key Cryptography 2004, 305-318, 2004.3
Though the multivariable cryptosystems first suggested by Matsumoto and Imai was defeated by the linearization method of Patarin due to the special properties of the Matsumoto-Imai (MI) cryptosystem, many variants and extensions of the MI system were suggested mainly by Patarin and his collaborators. In this paper, we propose a new variant of the MI system, which was inspired by the idea of “perturbation”. This method uses a set of r (a small number) linearly independent linear functions z_i=∑_{j=1}^n α_{ij}x_j + β_i, i=1,..,r, over the variables x_i , which are variables of the MI system. The perturbation is performed by adding random quadratic function of z i to the MI systems. The difference between our idea and a very similar idea of the Hidden Field Equation and Oil-Vinegar system is that our perturbation is internal, where we do not introduce any new variables, while the Hidden Field Equation and Oil-Vinegar system is an “external” perturbation of the HFE system, where a few extra (external) new variables are introduced to perform the perturbation. A practical implementation example of 136 bits, its security analysis and efficiency analysis are presented. The attack complexity of this perturbed Matsumoto-Imai cryptosystem is estimated.
No keywords uploaded!
[ Download ] [ 2022-07-07 16:49:43 uploaded by dingjt ] [ 230 downloads ] [ 0 comments ]
  title={A New Variant of the Matsumoto-Imai Cryptosystem through Perturbation},
  author={Jintai Ding},
  booktitle={Public Key Cryptography 2004},
Jintai Ding. A New Variant of the Matsumoto-Imai Cryptosystem through Perturbation. 2004. In Public Key Cryptography 2004. pp.305-318. http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20220707164943822669587.
Please log in for comment!
Contact us: office-iccm@tsinghua.edu.cn | Copyright Reserved