Error-correcting Code VS Lattice-based Crypto

Question

I'm not an expert in PQ-crypto, but as I understand error-correcting code and lattice-based crypto, the cryptographic assumptions are very similar. The key difference for me is the nature of the noise. In one case, the noise is inspired by the "physical noise," in the other, it's more mathematical and considers a more complex distance (Euclidean distance instead of Hamming distance).

Intuitively, this reason makes sense because every application I know involving lattice-based crypto is more efficient than those based on error-correcting crypto.

1. Does my intuition seem correct to you?

2. If yes, is there a theorem that certifies that every cryptographic protocol based on an error-correcting-code assumption could be transformed into a more efficient lattice-based protocol (i.e., with the same level of security and based on a weaker lattice assumption)?

3. If no, is there a more informal claim of available research which considers this question? Or it just doesn't make sense to compare these two families of assumptions?

Answer 1

Regarding your first paragraph, I would not say that the key difference is the type of noise, because lattice-based cryptography (LBC) uses a lot of different noises: Gaussian, binary, ternary, etc. (also see this SE thread: Uniform vs discrete Gaussian sampling in Ring learning with errors). However, something extremely useful in LBC is that you can play with the modulus $q$ of the ring $\mathbb{Z}_q$ you are working on. Many problems in LBC can be solved by simply increasing $q$, which of course has an influence on the hardness of the underlying assumption, but in many cases the impact is manageable.

On the other hand, in code-based cryptography (CBC), most of the time the modulus is fixed to 2 (e.g. BIKE). When this happens, the modulus is one less tool that CBC can leverage. In conjunction with the modulus, the metric certainly has an influence. For example, suppose you add $n$ vectors $x_i$ of dimension $n$ with the same Euclidean norm (resp. Hamming weight):

• With the euclidean norm, you have $\|\sum_i x_i \| \leq \sum_i \|x_i\|$. So if you set the modulus $q$ to be large enough, you can still argue that the sum is short, which is useful for both security and correctness.
• Similarly, with the Hamming weight w, you have $w(\sum_i x_i) \leq \sum_i w(x_i)$. So if you add $n$ vectors of Hamming weight $1$ each, you can't say anything meaningful on the Hamming weight of the sum.

Regarding question 1, 2, 3, it is true that the state-of-the-art LBC schemes are more efficient than their CBC counterparts at the moment. But there is no guarantee that this will always be true because CBC has been around for more than 40 years, so cryptanalysts have had plenty of time to find optimized attacks. LBC is much more recent (20~ years). Note that when correctly parametrized, both families seem to provide exponential hardness in their parameters:

• For CBC: $O(2^{0.0885 \cdot n})$ where n is a system parameter, see this paper.
• For LBC: $\tilde{O}(2^{0.295 \cdot B})$ where B is a mess to compute but seems to grow more or less linearly with systems parameters, see this paper.

Like you mentioned, assumptions of both families are similar (e.g. schemes based on QC-MDPC use assumptions that look extremely similar to NTRU and Ring-LWE, see slide 4 of this presentation), and most simple LBC schemes have CBC equivalents, and reciprocally. To some extent, one can even draw analogies at a deeper level, which I find conceptually satisfying.

Answer 2

Broadly speaking, it's true that the main difference between "code-based cryptography" assumptions and "lattice-based" assumptions is the noise distribution. There are of course exceptions, e.g. code-based cryptosystems using the rank metric, or binary LPN, where the noise can be described as either small Hamming weight or small Euclidean distance.

In one case the noise is inspired of the "physical noise", and in the other one, it's more mathematical and consider a more complex distance (euclidean distance instead hamming distance).

I'm not sure about these analogies of "physical" and "mathematical" noise. Both types of noise may be useful mathematical models in different physical scenarios, e.g. low Hamming weight noise can model bits flipped during transmission, while Gaussian noise can model small perturbations in an image from a noisy sensor. In any case, these analogies aren't really relevant to cryptography.

is there a theorem which certify that every cryptographic protocol based on an error-correcting code assumption could be transformed in a more efficient protocol based on lattice (i.e with the same level of security and based on a weaker lattice assumption)?

I don't know of any general theorems like this. While lattice-based protocols are often more efficient, this is not always the case and it very much depends on the cryptographic application.

A natural example where lattices beat codes is key exchange. Here, lattice-based protocols such as Kyber are much simpler and faster than their code-based analogues like BIKE, largely due to an expensive error-correction step in the code-based setting, compared with cheap rounding techniques to correct errors in the lattice setting.

Another example is the challenge of constructing linearly homomorphic encryption schemes. This is quite straightforward using lattices, but still an unsolved problem from code-based assumptions. There is even evidence that this is impossible to achieve using natural "arithmetic" techniques - see the paper of Applebaum, Avron and Brzuska; this work only looks at specific applications, but may contain the types of theorems you are interested in.

On the other hand, there are cases where small-Hamming-weight noise can give efficiency benefits. A fairly recent example is when generating private, correlated randomness (e.g. multiplication triples or random oblivious transfers) for use in secure multi-party computation protocols. Using code-based assumptions, there are efficient techniques for compressing the correlated randomness down to much shorter seeds, which can be later expanded. This compression technique crucially relies on the sparse noise distribution, and analogous methods in the lattice setting are much more expensive. (See for instance, these works)

Answer 3

Just to add another quick answer, but one can add "Mersenne Prime"-based crypto to this list, which was initially concieved as a variant of lattice-based crypto where one does "big-int" arithmetic rather than polynomial arithmetic (see this paper). Some authors have tried to formalize the abstract sense in which these are all similar, for example in A framework for Cryptographic Problems from Linear Algebra, which states that by varying:

• The underlying ring arithmetic occurs within (which one can generally take to be of the for $\mathbb{Z}[x] / (f(x), g(x))$, where $g(x)$ is generally of quite small degree, i.e. 0 or 1).

• The notion of "small" (which you seem to have caught onto)

• The hardness assumption one works with (roughly there are LWE-type, LWR-type, SIS-type, and NTRU-type assumptions, although defined appropriately one can even view LWR-type assumptions as being a special case of LWE-type assumptions with non-i.i.d. noise).

One can get a diversity of schemes. I don't that that paper in particular gives constructions in this abstract framework, but it is not too difficult to do by generalizing existing schemes to this abstract setting.

This doesn't mean that they are all exactly equivalent, that instantiating a "template" scheme under separate assumptions leads to the same efficiency schemes, or even that among all the underlying hardness assumptions lattices always end up being most efficient (exploring this with concrete parameters would be interesting). But there is at least some overall conceptual similarity between the three areas which may be useful to keep in mind, at least at the level of constructing cryptosystems (but perhaps not yet at the cryptanalytic setting, although the "LLL-for-codes" paper of course is work in this direction).