## Cryptology ePrint Archive: Report 2018/1208

Revisiting Orthogonal Lattice Attacks on Approximate Common Divisor Problems and their Applications

Jun Xu and Santanu Sarkar and Lei Hu

Abstract: In this paper, we revisit three existing types of orthogonal lattice (OL) attacks and propose optimized cases to solve approximate common divisor (ACD) problems. In order to reduce both space and time costs, we also make an improved lattice using the rounding technique. Further, we present asymptotic formulas of the time complexities on our optimizations as well as three known OL attacks. Besides, we give specific conditions that the optimized OL attacks can work and show how the attack ability depends on the blocksize $\beta$ in the BKZ-$\beta$ algorithm. Therefore, we put forward a method to estimate the concrete cost of solving the random ACD instances. It can be used in the choice of practical parameters in ACD problems. Finally, we give the security estimates of some ACD-based FHE constructions from the literature and also analyze the implicit factorization problem with sufficient number of samples. In the above situations, our optimized OL attack using the rounding technique performs fastest in practice.

Category / Keywords: public-key cryptography / Fully homomorphic encryption, approximate common divisor problem, implicit factorization problem, lattice, orthogonal lattice attack, lattice reduction algorithm