1
$\begingroup$

I had some questions regarding the basics of lattice-based cryptography I was hoping someone could answer:

  1. What are the advantages of using a parallelepiped vs a grid?

Parallelepiped vs Grid

Does a parallelepiped grant us something that a standard grid does not?

I only ask as I never see anyone use a standard grid when discussing lattice-based cryptographic scheme.

  1. What minimum lattice-size (X * Y) must we use in order to ensure a secure implementation?

In other words, must our lattice / grid be 100 x 100 in order to be secure, or must we use a larger lattice / grid (ex 1000 x 1000 or 10,000 x 10,000)?

  1. How do we determine the length of our shortest vector?

  2. How do we determine the lengths of our basis vectors?

  3. Can the origin of our shortest vector be located anywhere on the lattice / grid, or are certain places less secure than others?

In other words, would placing the origin of our shortest vector at the origin of our lattice be more or less secure than placing the origin of our shortest vector at some other location?

  1. What is the most secure way to choosing the random point, used in the CVP (Closest Vector Problem) lattice-based cryptographic scheme?

In other words, would choosing the random point at the origin of our lattice / grid be more or less secure than choosing some other location on our lattice / grid?

Thank you.

$\endgroup$
  • $\begingroup$ What is the name of the scheme cited in item 6? Do you have any reference about it? $\endgroup$ – Hilder Vítor Lima Pereira Aug 10 '17 at 11:27
  • $\begingroup$ You seem to be misunderstanding several things about lattices and lattice-based crypto. In particular (1) all lattices are infinite grids, and (2) the dimension of a lattice relates to the dimension of the space the vectors live in, and not to the "size of the grid". Both your figures describe 2-dimensional lattices, while in cryptography you'd use say 1000-dimensional lattices. And the origin of the vector space is always a point in the lattice - this point is not "picked". $\endgroup$ – TMM Sep 20 '17 at 21:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.