1
$\begingroup$

Can someone tie everything together for me? I'm interested in H.E and I have some background in AES, DES, RSA and the like. While reading around I stumbled on Shai Halevi's course on lattice cryptography as well as Vaikuntanathan's course.

Looking around I found Fully Homomorphic Encryption from Ring-LWEand Security for Key Dependent Messages which didn't really help me solidify the concepts I'm learning.

I "know" that lattice cryptography revolves around lattices and finding shortest vectors which is thought to be(?) NP-hard. I also found Homomorphic Encryption, LWE, and Practical Applications but it seems the asker there is ahead of me in terms of understanding how everything ties together

$\endgroup$
1
  • 1
    $\begingroup$ Could you try to solidify your thoughts into a concrete question? Otherwise the only real way I can think of responding to this is to write some generic thing on lattice-based cryptography, but it is not clear this would be more useful than the course notes you have found (except for likely being more informal, which can often be good at first). $\endgroup$
    – Mark
    Apr 7 at 3:56
6
$\begingroup$

While I still think it would be good for you to ask more specific questions, the following might be useful in clearing up your understanding of the underlying hard problems on lattices. I do not see a way to discuss homomorphic encryption as well without essentially writing some (informal) lecture notes, so won't in this answer.

The LWE Problem:

The central hard problem for building constructions in lattice-based cryptography is the Learning With Errors problem. There is a search and decisional form. The decisional form is to distinguish:

$$(A, As + e)\stackrel{?}{\approx}_c(A, u)$$

Here:

  1. $A \gets\mathbb{Z}_q^{m\times n}$ is a uniformly random matrix
  2. $s\gets \mathbb{Z}_q^n$ is a uniformly random vector
  3. $e\gets \chi^m$ is a random "concentrated" value (meaning $\lVert e\rVert_\infty$ is "small").

The search problem is to recover $s$, given $(A, As + e)$. This problem has a natural coding-theoretic [1] interpretation --- we can view $A$ as being the "generator matrix" of a random code, and $As + e$ being an encoding of $s$ under the aforementioned code that is sent through some "noisy" channel. In this setting, the problem of recovering $s$ is equivalent to the problem of decoding a random linear code, which is thought to be hard. Note that this is a problem we would want to do in practice --- random linear codes tend to achieve optimal parameters (up to constant factors), so coding theorists would be very happy if we could decode them.

Average-case Hardness:

Before discussing lattices more, I'll quickly discuss average-case hardness (as this is quite relevant to lattice-based cryptography). There are roughly two settings where one can discuss the complexity of some problem:

  1. In a "worst-case" setting. I.e., given any input instance, how long does it take you to solve the problem?
  2. In an "average-case" settting. I.e., given an input instance drawn at random from a particular distribution, how long does it take you to solve the problem?

Concepts such as NP-hardness discuss the former, but they are not particularly useful for cryptography. This is because one can have problems that are worst-case hard, but "most" instances of the problem are easy. If one chose an "easy" instance of the problem during key generation in some cryptographic construction, it could lead to the scheme breaking, despite the problem being worst-case hard.

This means that cryptographic constructions have to pin down some distribution such that the underlying problem is thought to be average-case hard. This can be more involved than you may think. If you think the underlying problem for RSA being "Factoring" vaguely, then one quickly runs into the unfortunate fact that random numbers are not too difficult to factor (for example, they are divisible by 2 with probability $1/2$ --- depending on how you define the factoring problem this may already suffice to "break" it). One can think about the problem of factoring semi-primes as being the general factoring problem where one specifies a plausible average-case hard distribution (that of semi-primes). This distribution is only plausibly hard though, and there are a number of non-trivial attacks depending on how a particular RSA instance is generated (for example, Pollard's $p-1$ algorithm). This is all to say that you can find some distribution over RSA instances which is likely average-case hard, but it is a more involved process than "just picking things randomly", and that the existence of non-trivial attacks even against the factoring of semi-primes means that we are really left with heuristic hardness of factoring in the end (although this has been fairly resilient over the years).

Lattice-based cryptography differs from this in a significant way due to the existence of worst-case to average-case reductions [2]. This essentially means that there exists some worst-case problem called SIVP (a slight generalization of the shortest vector problem you allude to) such that one can roughly [3] prove something of the form:

If SIVP is worst-case hard, then LWE is average-case hard

This is to say that lattice-based cryptography has a formal proof that the LWE distribution has a certain amount of average-case hardness, provided that a certain natural problem is worst-case hard.

The Ring Setting:

In the above I have only talked about LWE. The "Ring" setting (so working with RLWE rather than LWE) can be viewed as not choosing $A$ to be uniformly random, but instead uniformly random over some "structured subset of all matrices". This is not the most natural way to discuss things from a mathematical perspective, but may be useful initially. This structured subset admits a compact representation, and more efficient operations generically. This is to say that RLWE is mostly a way to improve efficiency, which while quite important in practice is not necessary to get the broad picture of lattice-based cryptography.


[1] There are some nuances here, the linear code should not be viewed as being a code in the binary symmetric channel (i.e. a "code with respect to the Hamming norm"), but instead in the additive white gaussian noise channel (say if you take $\chi$ to be discrete Gaussian, which is common).

[2] Note that there are other cryptographic problems with randomized "self-reductions" (for example it is know that if the discrete-log problem is worst-case hard, then it is average-case hard as well). The reductions in lattice cryptography are notable for being to an independently-studied (at least in the non-ring setting) worst-case problem.

[3] There are many caveats one must state here, but the largest one is that one does not work with SIVP in lattice-based cryptography, but instead an approximate version of it. It is known that this approximation problem is in $\text{NP}\cap\text{coNP}$, i.e. is not NP hard unless the polynomial hierarchy completely collapses, which is thought to be unlikely. Other caveats are mostly that there are many ancillary parameters that must satisfy certain inequalities. This is important in practice, but can ignored when just trying to get intuition.

$\endgroup$

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.