Paper 2018/1208

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

Jun Xu, Santanu Sarkar, and Lei Hu


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.

Available format(s)
Public-key cryptography
Publication info
Preprint. Minor revision.
Fully homomorphic encryptionapproximate common divisor problemimplicit factorization problemlatticeorthogonal lattice attacklattice reduction algorithm
Contact author(s)
xujun @ iie ac cn
sarkar santanu bir @ gmail com
2018-12-19: received
Short URL
Creative Commons Attribution


      author = {Jun Xu and Santanu Sarkar and Lei Hu},
      title = {Revisiting Orthogonal Lattice Attacks on Approximate Common Divisor Problems and their Applications},
      howpublished = {Cryptology ePrint Archive, Paper 2018/1208},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.