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

Eugenio Kuri Student

4/18/24, 6:24 PM

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?

1 + 2

kodlu

4/18/24, 7:49 PM

It'strange to say "the more integers in the prime numbers" just say the larger the size of the prime numbers.

poncho

4/18/24, 8:06 PM

Also, 3D lattices aren't much more safe than 2D lattices; the various lattice problems are trivial for both of them. In crypto, we use lattices with dimensions in the hundreds, if not higher...

Score:2

Crypto

Titanlord

4/19/24, 7:11 AM

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.

+ 0

Elon Musk

I sit in a Tesla and translated this thread with Ai:

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

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.