In what way, does adding dimensions to lattice based cryptography decrease vulnerability to quantum computers? and why?

Question

In RSA encryption, the larger the size of the prime numbers utilized for the creation of the public key, the more computational power is required in order to "Brute force" decryption.

• Does a similar concept apply when considering lattice-based encryption?
• Naturally, I would assume so, but how much more safe would a 3d lattice be, rather than a 2D lattice?
• Would it be exponential? and if so why?

Answer 1

The analysis of the security of cryptographic schemes is complex and simplified statements like "the security increases exponentially based on the number of dimensions" are difficult to prove. Especially because we have a different problem class, prime factorization and lattice problems are very different.

But yes, increasing the dimensions also increases the security of a lattice problem. But defining exactly how much the security increases is difficult. I think this paper somewhat answers your questions. We can look at this table from the paper:

So you see, we need hundreds or even thousands of dimensions to match modern security requirements. And you can also see to some extent, how much the dimensions have to increase. Nevertheless, I would take the data with a grain of salt, because there may be newer papers, with better analysis, I am not aware of.