Welcome to the resource topic for 2019/195
Title:
Algorithms for CRT-variant of Approximate Greatest Common Divisor Problem
Authors: Jung Hee Cheon, Wonhee Cho, Minki Hhan, Minsik Kang, Jiseung Kim, 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 2^{\tilde{O}(\frac{\gamma}{(\eta-\rho)^2})} up to a polynomial factor to solve the CCK-ACD problem for the bit size of samples \gamma, secret primes \eta, and error bound \rho. Compared to Chen and Nguyen’s algorithm in Eurocrypt’ 12, which takes \tilde{O}(2^{\rho/2}) complexity, our algorithm gives the first parameter condition related to \eta and \gamma size. We also report the experimental results for our attack upon several parameters. From the results, we can see that our algorithms work well both in theoretical and experimental terms.
ePrint: https://eprint.iacr.org/2019/195
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .