Cryptology ePrint Archive: Report 2017/322

Approximate Polynomial Common Divisor Problem Relates to Noisy Multipolynomial Reconstruction

Jun Xu and 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.

Category / Keywords: foundations / Approximate polynomial common divisor problem, noisy multipolynomial reconstruction, polynomial lattice

Date: received 11 Apr 2017

Contact author: {xujun,hulei} at iie ac cn,sarkar santanu bir@gmail com

Available format(s): PDF | BibTeX Citation

Version: 20170414:174651 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]