Location: Home > Research
Lattice reduction and information security
Update time: 2014-03-26
Text Size: A  A   A

More recently, we have given a more efficient algorithm for reconstructing algebraic numbers, which is based on our modification of the PSLQ algorithm that is one of the top 10 algorithms in the twentieth century. The new algorithm outperforms the existing ones in the literature. This work has been presented at ACM ISSAC 2013 held in Boston, USA.

Function, technical parameters and advantages

The exact degree of the algebraic number is usually not unknown in practice. Instead, an upper bound on can be always obtained. Our main contribution is to give an efficient algorithm which solves RMP within O(d5+ d4 logM) arithmetic operations, even though the exact degree is unknown. In this case, the new algorithm saves a factor d; see Table 1 for experimental data.


Lattice reduction is the foundation of FHE (Fully Homomorphic Encryption), which is the key technique for Cloud Computing and Big Data security, and can resist quantum attack.

Copyright 2011 - 2012 All Rights Reserved Chongqing Institute of Green and Intelligent Technology, Chinese Academy of Sciences
Add: No.266 Fangzheng Avenue,Shuitu Hi-tech Industrial Park, Shuitu Town, Beibei District, Chongqing     Postal: 400714