Approximating Closest Vector Problem in ℓ∞-Norm Revisited. (13th September 2021)

• Record Type: Journal Article
• Authors: Chen, Wenbin; Chen, Jianer
• Is Part Of: Computer journal. Volume 65:Number 12(2022)
• Page Start: 3100
• Page End: 3105
• Publication Date: 2021-09-13
• Subjects: closest vector problem -- computational complexity -- NP-hardness -- min total label cover problem -- probabilistically checkable proofs; Computers -- Periodicals; 005.1
• DOI: 10.1093/comjnl/bxab129
• Languages: English
• ISSNs: 0010-4620

Abstract

Abstract: 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 and bounded distance decoding (BDD) problem. Approximating BDD is a special case of approximating closest vector problem (CVP). In this paper, we revisit the study for approximating CVP. We give a proof that approximating the CVP over $\ell _\infty $ -norm (CVP$_\infty $ ) within any constant factor is NP-hard. The result is obtained by the gap-preserving reduction from Min Total Label Cover problem in $\ell _1$ -norm to to CVP$_\infty $ . This proof is simpler than known proofs [ 10 ].