TY - CHAP
T1 - A new variant of the matsumoto-imai cryptosystem through perturbation
AU - Ding, Jintai
PY - 2004
Y1 - 2004
N2 - 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 zi = ∑j=1 n αijxj+βi, i=1, .., r, over the variables xi, which are variables of the MI system. The perturbation is performed by adding random quadratic function of Zi 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. Keywords: open-key, multivariable, quadratic polynomials, perturbation
AB - 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 zi = ∑j=1 n αijxj+βi, i=1, .., r, over the variables xi, which are variables of the MI system. The perturbation is performed by adding random quadratic function of Zi 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. Keywords: open-key, multivariable, quadratic polynomials, perturbation
UR - http://www.scopus.com/inward/record.url?scp=35048862324&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-24632-9_22
DO - 10.1007/978-3-540-24632-9_22
M3 - Chapter
AN - SCOPUS:35048862324
SN - 3540210180
SN - 9783540210184
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 305
EP - 318
BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
A2 - Bao, Feng
A2 - Deng, Robert
A2 - Zhou, Jianying
PB - Springer Verlag
ER -