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 CR P to BDD~p (Covering Bounded Distance Decoding Problem). Furthermore, we show that there are polynomial-time reductions from BDD~p 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.