Paper 2018/1208
Revisiting Orthogonal Lattice Attacks on Approximate Common Divisor Problems and their Applications
Jun Xu, 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.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Preprint. MINOR revision.
- Keywords
- Fully homomorphic encryptionapproximate common divisor problemimplicit factorization problemlatticeorthogonal lattice attacklattice reduction algorithm
- Contact author(s)
-
xujun @ iie ac cn
sarkar santanu bir @ gmail com - History
- 2018-12-19: received
- Short URL
- https://ia.cr/2018/1208
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2018/1208,
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},
url = {https://eprint.iacr.org/2018/1208}
}
