Cryptanalysis of Rational Multivariate Public Key Cryptosystems

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

TBD mathscidoc:2207.43033

PQCrypto 2008, 124-136, 2008.10
In 1989, Tsujii, Fujioka, and Hirayama proposed a family of multivariate public key cryptosystems, where the public key is given as a set of multivariate rational functions of degree 4. These cryptosystems are constructed via composition of two quadratic rational maps. In this paper, we present the cryptanalysis of this family of cryptosystems. The key point of our attack is to transform a problem of decomposition of two rational maps into a problem of decomposition of two polynomial maps. We develop a new improved 2R decomposition method and other new techniques, which allows us to find an equivalent decomposition of the rational maps to break the system completely. For the example suggested for practical applications, it is very fast to derive an equivalent private key, and it requires only a few seconds on a standard PC.
No keywords uploaded!
[ Download ] [ 2022-07-12 10:01:33 uploaded by dingjt ] [ 265 downloads ] [ 0 comments ]
@inproceedings{jintai2008cryptanalysis,
  title={Cryptanalysis of Rational Multivariate Public Key Cryptosystems},
  author={Jintai Ding, and John Wagner},
  url={http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20220712100133383219610},
  booktitle={PQCrypto 2008},
  pages={124-136},
  year={2008},
}
Jintai Ding, and John Wagner. Cryptanalysis of Rational Multivariate Public Key Cryptosystems. 2008. In PQCrypto 2008. pp.124-136. http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20220712100133383219610.
Please log in for comment!
 
 
Contact us: office-iccm@tsinghua.edu.cn | Copyright Reserved