The Shortest Vector Problem (SVP) and the Closest Vector Problem (CVP) are the fundamental algorithmic questions in the geometry of numbers. In the past two decades, their algorithmic complexity has been studied quite extensively due to their connection with lattice based cryptosystems. In this paper, we study these problems in the setting of generic black-box metric query model, which captures algorithms that rely on distance evaluations without exploiting specific geometry of the underlying metric. We prove that any randomized algorithm for solving SVP or CVP within any constant factor $\gamma < 2/\sqrt{3} \approx 1.154$ which accesses the metric as a black-box oracle needs to make at least $2^{\Omega(n)}$ queries to the metric oracle.
Our results rely on fundamental tools from the geometry of numbers and convex geometry. For our SVP lower bound, we use Siegel's Mean Value Theorem and Rogers' second moment bound to probabilistically construct an adversarial metric by introducing $2^{\Omega(n)}$ disjoint local convex perturbations to the underlying Euclidean norm. The lower bound for CVP follows from the SVP lower bound by observing that the known Turing reduction from SVP to CVP works in the black-box metric query model.
Fixed some typos and added some details in the proofs from section 4. Added sub-section 3.3 (in the current version): our original construction based on Siegel's Mean value theorem gives a real lattice with dense epsilon shell, sub-section describes how to obtain an integer lattice with dense epsilon shell with similar properties.
The Shortest Vector Problem (SVP) and the Closest Vector Problem (CVP) are the fundamental algorithmic questions in the geometry of numbers. In the past two decades, their algorithmic complexity has been studied quite extensively due to their connection with lattice based cryptosystems. In this paper, we study these problems in the setting of generic black-box metric query model, which captures algorithms that rely on distance evaluations without exploiting specific geometry of the underlying metric. We prove that any randomized algorithm for solving SVP or CVP within any constant factor $\gamma < 2/\sqrt{3} \approx 1.154$ which accesses the metric as a black-box oracle needs to make at least $2^{\Omega(n)}$ queries to the metric oracle.
Our results rely on fundamental tools from the geometry of numbers and convex geometry. For our SVP lower bound, we use Siegel's Mean Value Theorem to probabilistically construct an adversarial metric by introducing $2^{\Omega(n)}$ disjoint local convex perturbations to the underlying Euclidean norm. The lower bound for CVP follows from the SVP lower bound by observing that the known Turing reduction from SVP to CVP works in the black-box metric query model.
