Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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
add comment

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.