MathSciDoc: An Archive for Mathematician ∫

 
Log In
Sign Up
Help
Go
 

Cryptanalysis of a Public Key Cryptosystem Based on Diophantine Equations via Weighted LLL Reduction

Jintai Ding University of Cincinnati, Cincinnati, USA Momonari Kudo Graduate School of Mathematics, Kyushu University, Fukuoka, Japan Shinya Okumura Institute of Systems, Information Technologies and Nanotechnologies, Fukuoka, Japan Tsuyoshi Takagi Institute of Mathematics for Industry, Kyushu University, Fukuoka, Japan Chengdong Tao South China University of Technology, Guangzhou, China

TBD mathscidoc:2207.43073

IWSEC 2016, 305–315, 2016.9
Okumura proposed a candidate of post-quantum cryptosystem based on Diophantine equations of degree increasing type (DEC). Sizes of public keys in DEC are small, e.g., 1,200 bits for 128 bit security, and it is a strongly desired property in post-quantum erea. In this paper, we propose a polynomial time attack against DEC. We show that the one-wayness of DEC is reduced to finding special (relatively) short vectors in some lattices. The usual LLL algorithm does not work well for finding the most important target vector in our attack. The most technical point of our method is to heuristically find a special norm called a weighted norm to find the most important target vector. We call this method “weighted LLL algorithm” in this paper. Our experimental results suggest that our attack can break the one-wayness of DEC for 128 bit security with sufficiently high probability.
No keywords uploaded!
[ Download ] [ 2022-07-15 10:20:51 uploaded by dingjt ] [ 458 downloads ] [ 0 comments ] 
@inproceedings{jintai2016cryptanalysis,
  title={Cryptanalysis of a Public Key Cryptosystem Based on Diophantine Equations via Weighted LLL Reduction},
  author={Jintai Ding, Momonari Kudo, Shinya Okumura, Tsuyoshi Takagi, and Chengdong Tao},
  url={http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20220715102052013719652},
  booktitle={IWSEC 2016},
  pages={305–315},
  year={2016},
}
Jintai Ding, Momonari Kudo, Shinya Okumura, Tsuyoshi Takagi, and Chengdong Tao. Cryptanalysis of a Public Key Cryptosystem Based on Diophantine Equations via Weighted LLL Reduction. 2016. In IWSEC 2016. pp.305–315. http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20220715102052013719652.
Please log in for comment!
 
 
Contact us: office-iccm@tsinghua.edu.cn | Copyright Reserved