Approximating Closest Vector Problem in l_∞ Norm Revisited

摘要

The security of most lattice-based cryptography schemes are based on two computational hard problems which are the Short Integer Solution (SIS) and Learning With Errors (LWE) problems. The computational complexity of SIS and LWE problems are related to approximating Shortest Vector Problem (SVP) and Bounded Distance Decoding Problem (BDD). Approximating BDD is a special case of approximating Closest Vector Problem (CVP). In this paper, we revisit the study for approximating Closest Vector Problem. We give one proof that approximating the Closest Vector Problem over l_∞ norm (CVP_∞) within any constant factor is NP-hard. The result is obtained by the gap-preserving reduction from Min Total Label Cover problem in l_1 norm to CVP_∞ This proof is simpler than known proofs.