MathSciDoc: An Archive for Mathematician ∫

 
Log In
Sign Up
Help
Go
 

Complexity Estimates for the F_4 Attack on the Perturbed Matsumoto-Imai Cryptosystem

Jintai Ding Department of Mathematical Sciences, University of Cincinnati, Cincinnati, OH 45211-0025, USA J. E. Gower Department of Mathematical Sciences, University of Cincinnati, Cincinnati, OH 45211-0025, USA D. Schmidt Department of Electrical & Computer Engineering and Computer Science, University of Cincinnati, Cincinnati, OH 45211-0030, USA C. Wolf K.U. Leuven ESAT-COSIC, Kasteelpark Arenberg 10, B-3001 Leuven-Heverlee, Belgium Z. Yin Department of Mathematical Sciences, University of Cincinnati, Cincinnati, OH 45211-0025, USA

TBD mathscidoc:2207.43016

IMACC 2005, 262-277, 2005.12
Though the Perturbed Matsumoto-Imai (PMI) cryptosystem is considered insecure due to the recent differential attack of Fouque, Granboulan, and Stern, even more recently Ding and Gower showed that PMI can be repaired with the Plus (+) method of externally adding as few as 10 randomly chosen quadratic polynomials. Since relatively few extra polynomials are added, the attack complexity of a Gröbner basis attack on PMI+ will be roughly equal to that of PMI. Using Magma’s implementation of the F 4 Gröbner basis algorithm, we attack PMI with parameters q = 2, 0 ≤ r ≤ 10, and 14 ≤ n ≤ 59. Here, q is the number of field elements, n the number of equations/variables, and r the perturbation dimension. Based on our experimental results, we give estimates for the running time for such an attack. We use these estimates to judge the security of some proposed schemes, and we suggest more efficient schemes. In particular, we estimate that an attack using F 4 against the parameters q = 2, r = 5, n = 96 (suggested in [7]) has a time complexity of less than 250 3-DES computations, which would be considered insecure for practical applications.
No keywords uploaded!
[ Download ] [ 2022-07-08 16:58:43 uploaded by dingjt ] [ 529 downloads ] [ 0 comments ] 
@inproceedings{jintai2005complexity,
  title={Complexity Estimates for the F_4 Attack on the Perturbed Matsumoto-Imai Cryptosystem},
  author={Jintai Ding, J. E. Gower, D. Schmidt, C. Wolf, and Z. Yin},
  url={http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20220708165843657328593},
  booktitle={IMACC 2005},
  pages={262-277},
  year={2005},
}
Jintai Ding, J. E. Gower, D. Schmidt, C. Wolf, and Z. Yin. Complexity Estimates for the F_4 Attack on the Perturbed Matsumoto-Imai Cryptosystem. 2005. In IMACC 2005. pp.262-277. http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20220708165843657328593.
Please log in for comment!
 
 
Contact us: office-iccm@tsinghua.edu.cn | Copyright Reserved