Paper 2019/195
Algorithms for CRT-variant of Approximate Greatest Common Divisor Problem
Jung Hee Cheon, Wonhee Cho, Minki Hhan, Minsik Kang, Jiseung Kim, and Changmin Lee
Abstract
The approximate greatest common divisor problem (ACD) and its variants have been used to construct many cryptographic primitives. In particular, variants of the ACD problem based on Chinese remainder theorem (CRT) are exploited in the constructions of a batch fully homomorphic encryption to encrypt multiple messages in one ciphertext. Despite the utility of the CRT-variant scheme, the algorithms to solve its security foundation have not been studied well compared to the original ACD based scheme. In this paper, we propose two algorithms for solving the CCK-ACD problem, which is used to construct a batch fully homomorphic encryption over integers. To achieve the goal, we revisit the orthogonal lattice attack and simultaneous Diophantine approximation algorithm. Both two algorithms take the same time complexity
Metadata
- Available format(s)
-
PDF
- Publication info
- Preprint. MINOR revision.
- Keywords
- CCK-ACDLatticeorthogonal lattice attackSDA
- Contact author(s)
-
changmin lee @ ens-lyon fr
tory154 @ snu ac kr
wony0404 @ snu ac kr
hhan_ @ snu ac kr - History
- 2019-02-27: received
- Short URL
- https://ia.cr/2019/195
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2019/195, author = {Jung Hee Cheon and Wonhee Cho and Minki Hhan and Minsik Kang and Jiseung Kim and Changmin Lee}, title = {Algorithms for {CRT}-variant of Approximate Greatest Common Divisor Problem}, howpublished = {Cryptology {ePrint} Archive, Paper 2019/195}, year = {2019}, url = {https://eprint.iacr.org/2019/195} }