4
$\begingroup$

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?
$\endgroup$
2
  • $\begingroup$ It'strange to say "the more integers in the prime numbers" just say the larger the size of the prime numbers. $\endgroup$
    – kodlu
    Apr 18, 2023 at 19:49
  • 1
    $\begingroup$ 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... $\endgroup$
    – poncho
    Apr 18, 2023 at 20:06

1 Answer 1

2
$\begingroup$

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:

enter image description here

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.