[Cryptography] Lattice cryptography

[Syber Shock]

On Mon, 12 Feb 2024 06:55:01 -0500
Pierre Abbat <phma at bezitopo.org> wrote:

<snip>
 
> I've watched them, and now I understand the trapdoor, but how big are the 
> problems? How many dimensions are needed to equal the security of 128-bit or 
> 256-bit symmetric ciphers? How big are the numbers in a good basis and in a 
> bad basis?

Looking at recent systems such as Kyber and NTRU may give a definite answer per their cryptosystems:

https://pq-crystals.org/kyber/

The Kyber page gives key sizes for particular bit strengths. But that is just for Kyber. It can't be assumed as an answer for LWE in general because there are so many ways to modify the problem and build on the problem.

Complicating this is the fact that even NIST seemed to publish contested bit strength calculations. If memory serves me right, the objection was that they used the wrong multiplicative operation on parameters to get the bit strength calculation.

Wikipedia says this:

"A major advantage that RLWE based cryptography has over the original learning with errors (LWE) based cryptography is found in the size of the public and private keys. RLWE keys are roughly the square root of keys in LWE. For 128 bits of security an RLWE cryptographic algorithm would use public keys around 7000 bits in length. The corresponding LWE scheme would require public keys of 49 million bits for the same level of security. On the other hand, RLWE keys are larger than the keys sizes for currently used public key algorithms like RSA and Elliptic Curve Diffie-Hellman which require public key sizes of 3072 bits and 256 bits, respectively, to achieve a 128-bit level of security. From a computational standpoint, however, RLWE algorithms have been shown to be the equal of or better than existing public key systems." (https://en.wikipedia.org/wiki/Ring_learning_with_errors)

You could research at the source from the papers of Oded Regev:

https://scholar.google.com/citations?user=3-gk0ioAAAAJ&hl=en

-- 
    Syber Shock | sybershock.com | alt.sources.crypto | sci.crypt