The Reductions for the Approximating Covering Radius Problem

摘要

We establish the direct connection between CRP (Covering Radius Problem) and other lattice problems. We first prove that there is a polynomial-time rank-preserving reduction from approximating CRP to BDD~ρ (Covering Bounded Distance Decoding Problem). Furthermore, we show that there are polynomial-time reductions from BDD~ρ to approximating CVP (Closest Vector Problem) and SIVP (Shortest Independent Vector Problem), respectively. Hence, CRP reduces to CVP and SIVP under deterministic polynomial-time reductions.