Paper 2017/322
Approximate Polynomial Common Divisor Problem Relates to Noisy Multipolynomial Reconstruction
Jun Xu, Santanu Sarkar, and Lei Hu
Abstract
In this paper, we investigate the hardness of the approximate polynomial common divisor problem, which is regarded as a polynomial analogy of the approximate integer common divisor problem. In order to solve this problem, we present a simple method by using the polynomial lattice reduction algorithm and contain complete theoretical analyses. Further, we propose an improved lattice attack to reduce both space and time costs. Moreover, these two attacking methods can be directly applied to solving the noisy multipolynomial reconstruction problem in the field of error-correcting codes. On the basis of the above situations, our improved lattice attack performs fastest.
Metadata
- Available format(s)
- -- withdrawn --
- Category
- Foundations
- Publication info
- Preprint. MINOR revision.
- Keywords
- noisy multipolynomial reconstructionpolynomial lattice
- Contact author(s)
-
xujun @ iie ac cn
sarkar santanu bir @ gmail com - History
- 2019-10-29: withdrawn
- 2017-04-14: received
- See all versions
- Short URL
- https://ia.cr/2017/322
- License
-
CC BY