When utilizing the closest vector problem for decrypting data, does lattice size matter. For example, is a 1000x1000 grid necessarily more safe than a 100x100 grid? And if so, why would these affect the computations of quantum computers? Also is there a "safest way" of choosing a lattice point that guarantees higher success?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Most of the answer is already covered here
But I want to elaborate more on your question because there is something I find interesting. In general, we don't talk about grids, but about dimensions for input size of the problem. The grid results from the dimension vectors.
And the interesting point here is, that more dimensions do not need to result in a more difficult problem. I try to answer this simplified: For prime factors it is some kind of obvious, that factoring bigger numbers seems to be harder and in general this statement holds. But the Lattice problems are completely different, mainly because they are based on different assumptions. Lattice problems are based on the P-NP assumption and are part of the NP-class. Not every problem in this class has the same properties, e.g. for crypto we want average case hardness and stuff like that. Therefore it can occur, that increasing the dimensions may lead to a weaker problem in some sense. BUT, in general, more dimensions lead to more difficult problems.
(I simplified a lot here, because I assume the author of the questions does not have deep knowledge in crypto or theoretical computer science. I just wanted to a glimpse of the ideas behind Lattice problems in crypto.)
