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
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.