8
$\begingroup$

I'm not an expert in PQ-Crypto. As I understood Error Correcting Code and Lattice based crypto. The cryptographic assumptions are very similar. And the key-difference for me is the nature of the noise. 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).

Intuitively, this reason makes sense about the fact that in every apllications I know lattice-based crypto is more efficient than Error-correcting based crypto.

  1. Is my intuition seems correct to you?

  2. If yes, 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)?

  3. If No, is there more informal claim of known researcher which consider this question. Or it just doesn't make sens to compare these two families of assumptions?

$\endgroup$
4
+50
$\begingroup$

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.

| improve this answer | |
$\endgroup$
7
$\begingroup$

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)

| improve this answer | |
$\endgroup$
  • $\begingroup$ "If anything, I'd imagine that small Gaussian noise accurately models many real-world noisy signals." In the real world noise doesn't make any difference between least significant bit and most significant bit. $\endgroup$ – Ievgeni Aug 31 at 8:32
  • $\begingroup$ Depends on the application, e.g. a noisy image sensor might just perturb the colour value of each pixel by a small amount. But it's probably true that both types of noise are useful models in different scenarios. Will rephrase. $\endgroup$ – pscholl Aug 31 at 18:43
  • $\begingroup$ "In the real world noise doesn't make any difference between least significant bit and most significant bit."; depends on what in the real world you are modelling. If the samples are from a ADC-converted analog signal (that has a small noise added), then the effects of the noise will be concentrated in the lsbits. @levgeni $\endgroup$ – poncho Aug 31 at 21:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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