Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.