Mathematics – Number Theory
Scientific paper
2011-08-12
Mathematics
Number Theory
17 pages
Scientific paper
We analyze the multivariate generalization of Howgrave-Graham's algorithm for the approximate common divisor problem. In the m-variable case with modulus N and approximate common divisor of size N^beta, this improves the size of the error tolerated from N^(beta^2) to N^(beta^((m+1)/m)), under a commonly used heuristic assumption. This gives a more detailed analysis of the hardness assumption underlying the recent fully homomorphic cryptosystem of van Dijk, Gentry, Halevi, and Vaikuntanathan. While these results do not challenge the suggested parameters, a 2^(n^epsilon) approximation algorithm with epsilon<2/3 for lattice basis reduction in n dimensions could be used to break these parameters. We have implemented our algorithm, and it performs better in practice than the theoretical analysis suggests. Our results fit into a broader context of analogies between cryptanalysis and coding theory. The multivariate approximate common divisor problem is the number-theoretic analogue of multivariate polynomial reconstruction, and we develop a corresponding lattice-based algorithm for the latter problem. In particular, it specializes to a lattice-based list decoding algorithm for Parvaresh-Vardy and Guruswami-Rudra codes, which are multivariate extensions of Reed-Solomon codes. This yields a new proof of the list decoding radii for these codes.
Cohn Henry
Heninger Nadia
No associations
LandOfFree
Approximate common divisors via lattices does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Approximate common divisors via lattices, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Approximate common divisors via lattices will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-635641