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\|
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:
There exists a probabilistic polynomial-time algorithm which, on input $(B, p, r)$, outputs the set $\beta_\mathcal{L}(p,r)$ .
The probability that, any probabilistic polynomial-time algorithm with input $(B', p, r)$, outputs any point of $\beta_\mathcal{L}(p,r)$ is negligible.