# A variant of the “closest vector problem” (CVP) in lattice-based cryptography

Consider a public-key scheme on lattices, such as GGH.

The private key is a basis $\mathbf{B} \in \mathbb{Z}^{m \times n}$ of a lattice $\mathcal{L}$ with good properties (such as short nearly orthogonal vectors) and a unimodular matrix $U$. The public key is another basis of the lattice $\mathcal{L}$ of the form $\mathbf{B}' = U\mathbf{B}$.

We assume that the CVP is hard on $\mathbf{B}'$ but easy on $\mathbf{B}$.

For any point $p \in \mathbb{R}^{m}$, define $\beta_\mathcal{L}(p,r) = \{x \in \mathcal{L} \mid \|x -p\| <r \}$. This is the set of lattice points whose members' distance to $p$ is less than $r$.

I'm interested in the following problem:

Can we construct a lattice, and set $r$ to some value, such that for any point $p \in \mathbb{R}^{m}$, the following two conditions hold:

1. There exists a probabilistic polynomial-time algorithm which, on input $(B, p, r)$, outputs the set $\beta_\mathcal{L}(p,r)$ .

2. The probability that, any probabilistic polynomial-time algorithm with input $(B', p, r)$, outputs any point of $\beta_\mathcal{L}(p,r)$ is negligible.

-
Usually if $B$ is a very good basis and $B'$ is a bad basis of any sufficiently high-dimensional lattice, then 1. is easy and 2. is hard. I think 2. is too hard for PPT algorithms, but you'd have to check the literature if it has been proven or not. –  TMM Apr 29 '12 at 15:02