What is the relation between LWE and coding based cryptography?

Anon

4/3/24, 10:12 PM

I've recently heard about coding based cryptography and it seems very close to the LWE assumption in that it is based on the idea that the error is hard to identify. They are both post-quantum schemes too.

Is there a direct link between the two? (e.g., coding based can be seen as an instance of LWE under certain assumptions) or is there absolutely no relation?

1 + 0

post-quantum-cryptography

lwe

Score:1

Crypto

kodlu

4/4/24, 12:19 AM

Yes the two are definitely related, but it can be a bit complicated to describe it. This will be a sketch of some related points. I know mainly about coding theory, so I will point out a few obvious links. The experts here would be able to tell you more:

Code based cryptography (take McEliece as an example) is based on randomizing a structured error correcting code, adding an error vector which is of weight exactly equal to the code correction capability and using the structure of the code as the trapdoor information. This is typically over the binary field, $n$ is the codeword length, $t$ is the error correction capability and the rate $k/n$ of the code is fixed (the code has $2^k$ codewords in the space $\mathbb{F}_2^n$ with $2^n$ vectors.
Most closely related is LPN (learning parity with noise) based cryptography where corresponds to the decoding problem where $n$ is the number of samples, $k$ the length of the secret while the error is sampled according to a Bernoulli distribution of fixed rate $t/n.$ As the number of samples in LPN is unlimited, this problem actually corresponds to decoding a random code of rate arbitrarily close to $0.$
While the security of many code-based cryptosystems relies on the hardness of the decoding problem, it can also be based on finding a “short” codeword for the Hamming metric. For LPN there are reductions which converts the decoding problem to finding a short codeword.
Since the original code based systems were inefficient, other ones were proposed using different codes (quasicyclic instead of Goppa). Independently people proposed LWE over lattices and later on over rings as well. The Ring-LWE problems are the most closely related to decoding a classical code but I don't have deep knowledge about this area. The link between codes and lattices in general is quite deep and complicated, with Leech Lattice and Golay Codes playing a part. Conway and Sloane have a classical text of many hundreds of pages on lattices and links to classical codes is discussed there.

+ 0

Elon Musk

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

EN: What is the relation between LWE and coding based cryptography?

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.