#44 Public Key Encryption from LWE | Part 1 | Quantum Algorithms & Cryptography

Estimated read time: 1:20

Summary

The lecture initiates with a basic overview of lattices and their problems, emphasizing the hardness of these problems for both classical and quantum computers. This leads to an exploration of cryptography based on lattice problems such as Learning With Errors (LWE) and the Short Integer Solutions problem. The presentation delves into the hardness proofs for LWE, highlighting its connection to worst-case lattice problems and the effects of error distribution on its difficulty. The session concludes by describing a method to create public key encryption using LWE, emphasizing parameter fine-tuning to balance between security and efficiency.

Highlights

Lattices and their classic problems act as the backbone for cryptography development. 🦴
Despite advancements, lattice problems are hard nuts to crack on any computer! 🖥️🔒
Learning With Errors (LWE) offers a promising path for quantum-resistant cryptography. 🌌
Error distribution plays a crucial role in the hardness of the LWE problem. 📊
Creating public key encryption from LWE involves clever manipulation of parameters. 🛠️

Key Takeaways

Lattices hold the key to post-quantum cryptography! 🔑
LWE problem: The secret to secure cryptographic systems! 🔒
From classical to quantum, lattice problems remain hard-core! 💪
Public key encryption just got a lattice makeover! 🔐
Balancing security and efficiency in cryptography is like walking a tightrope! 🎯

Overview

The lecture embarks on a journey into the realm of lattices, setting the stage by defining essential concepts and problems intrinsic to this mathematical structure. It accentuates the complex nature of these problems, which continue to challenge both classical and quantum computing efforts, forming the foundation for advanced cryptographic measures.

Attention then shifts to the pivotal Learning With Errors (LWE) problem, a core construct in lattice-based cryptography. This method underscores the potential of lattices to not only fortify security postures against quantum attacks but also to innovate beyond pre-existing cryptographic capabilities. The lecture reviews breakthrough work and improvements in this field, emphasizing the interplay between error distributions and computational difficulty.

The session wraps up with a practical exposition on generating public key encryption via the LWE problem. Emphasis is placed on strategic parameter selection to ensure the desired security level does not compromise system efficiency. This deep dive illustrates how cryptography can leverage structured mathematical problems to not only withstand, but also thrive in a quantum computing era.

Chapters

00:00 - 05:30: Introduction and Basics The chapter introduces the basics of lattices, initiating the course content.
05:30 - 10:30: Classic Problems on Lattices The chapter titled 'Classic Problems on Lattices' provides a fundamental introduction to the theory of lattices, which the text notes is a rich and complex field. The chapter offers definitions and explanations of important concepts like lattices themselves and 'successive minima,' denoted by Lambda 1 to Lambda n. It further explores significant problems associated with lattices such as the shortest vector problem, the closest vector problem, and the shortest independent vectors problem. Additionally, the chapter discusses approximate versions of these problems, aiming to provide a comprehensive overview of classical challenges in the study of lattices.
10:30 - 17:30: Learning with Errors (LWE) The chapter discusses the classic problems on lattices known as Learning with Errors (LWE), which have been studied for a long time. Despite ongoing research, the progress in solving these problems remains moderate, with existing algorithms still requiring exponential time, albeit with some modest improvements. The emphasis is on the belief that these problems are inherently complex.
17:30 - 25:50: Hardness of LWE and Related Problems In this chapter, the focus is on the hardness of the Learning with Errors (LWE) problem and its related problems. The discussion points out that these problems are believed to be difficult not only for classical computers but also for quantum computers. It highlights the connection between lattice problems and problems in non-commutative groups, specifically referencing the dihedral hidden subgroup problem. The chapter underscores the lack of efficient methods to solve these problems, emphasizing their complexity and computational challenges.
25:50 - 32:00: Public Key Encryption using LWE The chapter discusses public key encryption using LWE (Learning With Errors), a method believed to be secure even against quantum computers. The speaker refers to the use of lattices for cryptography, which is currently considered a secure approach. Traditional lattice problems like the Shortest Vector Problem (SVP) and the Closest Vector Problem (CVP) are not directly useful for cryptography; hence, alternative approaches are explored.
32:00 - 44:00: Encryption and Decryption Process This chapter delves into the connections between various lattice problems and how they underpin significant cryptographic methods. Key lattice problems like the Learning With Errors (LWE) and the Short Integer Solutions (SIS) are discussed, both of which were mentioned in previous sections. The chapter emphasizes the rich and diverse research landscape that explores building cryptography from these foundational problems.
44:00 - 48:00: Correctness and Error Analysis This chapter explores the transformative impact of lattices in computing, particularly in the context of quantum technologies. Unlike in the pre-quantum era, lattices are providing not only post-quantum or quantum-resistant solutions but also enabling the development of entirely new functionalities that were previously inconceivable. The instructor expresses the intent to demonstrate one or two of these innovations in upcoming lectures.
48:00 - 52:00: Conclusion In the conclusion chapter, the focus is on building a basic understanding and implementation of encryption using the learning with errors (LWE) problem. There's a recap of the previous lesson where the LWE problem was defined, and an invitation for the class to recall the intuitive one-line description of it. This sets the stage for implementing vanilla public key encryption based on this concept.

#44 Public Key Encryption from LWE | Part 1 | Quantum Algorithms & Cryptography Transcription

00:00 - 00:30 foreign [Music] [Music] let's get started so we started looking at some basics of lattices last time as I already said what we are looking at in this course is really just a very very
00:30 - 01:00 superficial treatment of lattices which is a very rich theory in itself but nevertheless we defined lattices we defined a few important quantities in particular we defined the successive Minima right Lambda 1 to Lambda n and we defined some useful and interesting problems on lattices the shortest Vector closest Vector shortest independent vectors problem and so on and approximate versions of those as well
01:00 - 01:30 now as I told you last time ah these are the classic problems on lattices that you know have been studied for a very long time surprisingly though you know there is still progress that's being made on solving these problems but but only in the improvements that we get are very modest so they remain exponential time algorithms but you know we can still get some modest improvements so we really believe that these problems
01:30 - 02:00 are hard and not only do we believe they are hard for a classical computer we also believe they are hard for a quantum computer all of you will remember that I talked about how you know uh problems on lattices correspond to problems in non-commutative groups of the ah dihedral hidden subgroup problem so we don't have any nice way that we know of solving these ah these problems even
02:00 - 02:30 using a quantum computer okay so fine so you know assuming that we're good to go with lattices which is which is what is currently believed uh let's try to see how to do some cryptography using lattices right and last time I also told you that these classic problems which we defined the shortest Vector closest Vector problem being the main two these are not immediately useful for building cryptography so what we will do is we will actually look at sort of other ah
02:30 - 03:00 sort of the same lattice problems disguised as other problems ah notably this learning with errors problem and the short integer Solutions problem which we also saw last time and we will see how to build some cryptography using that okay now uh I will again mention that ah building cryptography from these lattice problems is a very very rich and diverse area of research notably there
03:00 - 03:30 are things that we can do from lattices that we did not even know how to do in the pre Quantum setting so you know uh it's not just that lattices are giving us ah post Quantum or Quantum resistant versions of things that we could do otherwise but they are also giving us new and amazing things that we just did not know how to do before so I would like to show you at least one or two in the you know few more lectures that we have remaining but before that you know
03:30 - 04:00 let's get a few more Basics out of the way okay so with all that let me sort of Dive Right In so what we'll do today is you know we'll we'll build encryption just you know vanilla public key encryption from the learning with errors problem okay so we defined the learning with errors problem last time can anyone remind the class what is ah what is the intuitive one line description of
04:00 - 04:30 learning with errors let me Define it for you again okay so learning with errors okay so uh this is sort of abbreviated as lwe no prices for guessing why okay and we have two versions of this there is a search and a decision version Let Me Define the search version First so we will ah denote this as s l w e
04:30 - 05:00 with parameters n m q and Chi OK and this is the question of finding s a vector s which lives in ah you know z q to the n given a i s
05:00 - 05:30 plus e i such that s was chosen randomly from z q to the n so over a i in fact okay and e i is chosen from some distribution Chi and I am giving you m of these samples okay so find s
05:30 - 06:00 given these ah noisy inner products so I have inner products with respect to a secret Vector s and the I am giving you these inner products perturbed with a little bit of noise and the goal is going to be to find this secret Vector so the one line intuitive description I was referring to was this that you know think of noisy inner products and you are trying to find the uh the secret Vector with respect to which these inner
06:00 - 06:30 products are generated okay so this is the search version there is also a decision version foreign Q chi I will be referring to the decision version and this is you know simply distinguish
06:30 - 07:00 the above samples from uniform all right so obviously the decision version is uh you know it it seems like a stronger assumption because ah even if I mean if I can solve the search version then I can certainly solve the decision version right if I can search
07:00 - 07:30 and recover the secret Vector s then certainly I know that this is not the uniform distribution but uh if I can solve the decision version it is not immediately obvious how I can solve the search version nevertheless the other direction also holds true okay so given the given uh an efficient algorithm for solving the decision version I can also use that to solve the search version but we will not do this reduction in class now one important ah quantity here that
07:30 - 08:00 I did not Define is this ah you know this distribution Chi so ah everything else here is defined right so n is the dimension of the vector m is the number of samples I am giving you right and Chi is a distribution from which I take the error so how should I choose this error I mean obviously it has to be something small now can you tell me why it should be small for instance why can I not
08:00 - 08:30 choose e i ah from ah z q what happens that's exactly right the inner product will no longer I mean the output will no longer be a noisy inner product it will just be statistically random right because I am giving you random plus something over a finite field so it's just uh it's just going to be statistically uh uniform so the problem will not make any sense in that
08:30 - 09:00 case okay so this is the search and the decision version of the problem ah now this chi I was talking about this guy I'm not for the moment I am not going to Define it so even last time I said that you can think for it think of it for Simplicity to just be you know zero and one like sampling the error from let's say minus one one or zero one uh this distribution actually matters like when you do these reductions between you know
09:00 - 09:30 learning with errors and these classic lattice problems like SVP and so on shortest Vector problem and so on at that time the distribution of error here really matters in you know what what for the reduction to work uh and in fact since I have already said so much about it it will turn out that the the nicest distribution here that works is a so-called discrete gaussian distribution
09:30 - 10:00 I am not going to Define it in this this class at least that is not my plan we will see yeah so just think of a gaussian distribution but discretized ah over integer points okay so this is just just for your knowledge but yeah we will not really use use any properties of it in what what we do in class except the fact that you know with with overwhelming probability we expect the norm of this
10:00 - 10:30 to be bounded we expect the norm to to be you know small so ah everybody knows what gaussian looks like right so it's something like this right so it's something like this and now I'm sort of discretizing it so basically it will be something like this so what this means is that you know if if my mean is 0 right then whatever is this distance
10:30 - 11:00 ah the standard deviation of this gaussian I can expect that my my sample will not be larger than that right so everybody knows this all of us have played with this hundreds of times so that's really the only property that we'll use in class for the purpose of constructing cryptography but I I want you to know that underlying this this distribution does matter because it is how we connect this problem to the ah
11:00 - 11:30 you know the classic problems on lattices that we talked about so let me just uh uh write down what what we know about the hardness of lattices of lwe again a little informally so I will not prove this so there is a seminal work by Odette reggae which in fact introduced this
11:30 - 12:00 problem and for which he won the very prestigious godell prize okay and then there's a follow-up work by brocketsky at all uh which uh you know improves the result so I am just writing informally so it was shown by these works and other works also I should say by
12:00 - 12:30 these and other works that for appropriate choices of parameters so what are our parameters you know this n m q and Chi l w e n m q Chi
12:30 - 13:00 is I should say search lwe is as hard as solving worst case lattice problems such as sivb
13:00 - 13:30 or something known as Gap SVP which is a like a a problem related to SVP but uh with with an additional promise that makes it easier okay so is ah solving worst case lattice problems such as Gap SVP and sivp
13:30 - 14:00 with approximation Factor poly n Q over gamma and Gamma here is you know it's actually the standard deviation of the gaussian that I was talking about but you know let's just say something related to Chi because for our purpose it really
14:00 - 14:30 doesn't matter okay so we believe that we believe that LW is hard here I should mention that we really are ah using the approximate version of these underlying problems okay so if you remember how we defined the shortest Vector problem and and so on we had approximate versions where we said that even if you can't get the exact solution if you can get it up to some
14:30 - 15:00 approximation that ah you know that is still useful so here we are using the approximate version of these problems and I should mention that for these approximation factors this these problems are not known to be NP hard okay so ah really just like with the rest of cryptography we are conjecturing that these problems for these approximation factors are hard this is just based on our knowledge of what are
15:00 - 15:30 the best known algorithms to solve them okay so I will just make a note here that the best known algorithms for 2 to the K approximation of this Gap SVP and sivp
15:30 - 16:00 run in time 2 to the order n over k okay so you can see that ah you know as the approximation Factor gets bigger so as K gets bigger uh okay the the time to run this uh these algorithms will get smaller so that is why when I when I assume the hardness of lwe with such
16:00 - 16:30 parameters that this underlying approximation Factor becomes very large then I have to worry so there's a lot of signs even behind how to choose these parameters and so on in in the real world I can always choose it very conservatively right so that the problem is very hard why don't we do that in practice that's right so it becomes less efficient I mean the real system will become less efficient if I choose
16:30 - 17:00 you know if if I focus on choosing parameters only based on security guarantees then efficiency will suffer okay so one more really handy thing about learning with errors is that uh there's actually uh there's a lot of flexibility in how you choose the distributions from which the secret and the error is sampled okay so uh there's there's a
17:00 - 17:30 particular form of lwe called The Hermit normal form which I'll quickly Define and that's what we'll use okay so we will the The Hermit normal form okay or ah we can also call it short secret lwe is ah
17:30 - 18:00 like lwe but with the difference that the secret s is also chosen from Chi from the error distribution Chi
18:00 - 18:30 okay so remember we are generating a S Plus e right and previously we were talking about we when we defined it uh last time as well as today we were sampling s uniformly from z q to the N right uniformly so these are large entries and I was telling you how the error obviously has to have small entries about otherwise
18:30 - 19:00 there's no sense in defining this problem so the hermit normal form or the short secret lwe says that even if you sample the secret from the same low Norm error distribution whatever you sample the error from sample the secret from the same distribution then also lwe remains hard okay so ah there is a quite a cute proof for this ah maybe we can do it if time permits okay but first I would like to just show you a public key
19:00 - 19:30 encryption from this now public key encryption from learning with errors there are many different ways of doing it I'll show the simplest one okay so let's let's construct public key encryption
19:30 - 20:00 okay so we have our key gen algorithm first right so remember this takes a security parameter Lambda and uh you know sample s from Chi to the n okay a uniformly from
20:00 - 20:30 z q let's think of it as a square Matrix and error e also from Chi to the n okay and let the public key be equal to a and why which is s transpose a plus e transpose okay so this is going to be in
20:30 - 21:00 z q n by n cross z q n okay so basically I I uh my public key is a matrix and my secret key is ah sorry my public key is a matrix together with an lwe sample generated with respect to that Matrix and my secret key is the lwe error okay so my
21:00 - 21:30 my secret key is going to be s ok so I will write it here so that everyone remembers so public is a and S transpose a plus e transpose and the secret key is s ok so now I want to encrypt so this will take the public key and the
21:30 - 22:00 message M for now I am just going to think of M as a bit okay so I I just want to encrypt a bit so what will I do well I will compute a as ah or let me first sample okay so sample R and X from Chi to the n and also X Prime from Chi
22:00 - 22:30 okay and now compute a as a r plus X and B as y transpose R plus X Prime plus m q over 2. mod Q all this is mod Q it's all over z q okay and you output
22:30 - 23:00 the comma B all right so uh what did we do we generated More lwe Sample so our public key was already an lwe instance right the secret key was the lwe secret no prices for guessing that uh the cipher text is LW is samples generated with respect to the public key so now the public key is itself or Matrix and a
23:00 - 23:30 vector right I am going to now use those as the you know as the sort of the seeds for lwe so those will be the ah I shouldn't say seeds I those as the sort of the public labels or matrices of lwe okay so I will now use those to generate more lwe samples okay Now can anyone tell me how to decrypt so
23:30 - 24:00 now I am given s and I am given a and b so let me compute I I compute s transpose a so what is this this is s transpose a r plus X right ah yeah so this is ah ok ok so this is this is s transpose a r plus s transpose X now what is b b is y
24:00 - 24:30 transpose R plus X prime plus m q over 2 so let me expand what was why why was s transpose a plus e transpose right times R plus X prime plus m q over 2 okay so this is s transpose a r plus e transpose R plus X prime plus m q over 2.
24:30 - 25:00 now the key thing to observe is ah that the only big terms that occur in s transpose a as well as B are these why is that remember that we sampled s as well as X from the error distribution so once again think of binary for Simplicity okay so s is binary let us
25:00 - 25:30 say x is also binary okay e uh e is also binary R is also binary X Prime is also binary so let me highlight the binary things or you know the error distribution things with with pink so now what what does this mean basically if I subtract you know if I subtract s transpose a
25:30 - 26:00 from B then this large term which I have right this uh this large term this this will get canceled out right if I do B minus s transpose a the large term gets canceled out okay and what do I get I get some s transpose X Plus e transpose R right plus X prime plus m Q over two this is what I get now I
26:00 - 26:30 claim that all of these are quite small okay now my message remember I said it's a bit so it's either 0 or 1 and I am scaling it with Q over 2 so think of you know this this is ah you know 0 to Q let us say ok so Q over 2 is somewhere here so now suppose I can bound this error term let me say I can bound it by some B
26:30 - 27:00 okay and this B let us say is quite small so suppose you know I I can say that b is going to be at most Q over 4. then what happens when my message is 0. then 0 plus sum B will be somewhere here right and when my message is 1. then Q over 2 plus b will be here so what can I do I can recover the
27:00 - 27:30 message bit just by seeing whether this you know this uh subtraction gave me something which is close to 0 or is it close to Q over 2. this lets me recover the message bit is the correctness clear so we need to set the parameters uh we you know for correctness we need to ensure that the error will be small let's do that but at least at a high level is this idea
27:30 - 28:00 clear okay so let's ah you know write down correctness ok so let me say that you know the support of chi so again not getting into the distribution of chi but
28:00 - 28:30 if I can say that you know this is my support for this for any sample chosen from chi I can bound its value ok so it it lives in this set you will see why I am choosing it like that suppose this you know this this is
28:30 - 29:00 uh doable by the way what is the only possible hurdle in setting Kai to have this support you have to make sure that for this kind of a chi the lwe problem remains hard okay so I hope that you can see that there is a sort of a tension between correctness and security if I have very large error then Security will be better and better right but correctness will be
29:00 - 29:30 harder and harder and vice versa if I have a very small error correctness will become easier but hardness will become worse okay so suppose that my support is like this ok then ah you know what what was my final error let let me remember so my final error you know is uh so this is B minus s transpose a right so this is s transpose X plus e transpose R plus X Prime you can
29:30 - 30:00 confirm right s transpose X Plus e transpose R plus X Prime this was my final error okay and here this s is of is of length n x is of length n this is also of length n this is of length n and this is of length one okay so given that s x e r and X Prime are all
30:00 - 30:30 sampled from Chi and I have a bound on Chi I should be able to bound this whole quantity right and a very simple bound is ah Q over 4 to 2 N plus 1 times 2 N Plus 1. which is Q over 4. this is a very simple bound you can see how it comes about okay so basically when I take inner product of s and X
30:30 - 31:00 every entry will get squared right so I'll get Q over 4 to n Plus 1. and then ah there are two n of these right there is ah in this inner product so the first one is ah an inner product of two n length vectors the second is also of two n length vectors right so uh and and X Prime is just a scalar right
31:00 - 31:30 so it can be bounded by square root of this quantity which means it can be bounded by the quantity itself so basically adding it up I I can get this very trivial bound so as long as you know the final error remains bounded I am going to get correctness and once again what did we use here we just used this picture right so I am only encoding bits so if I if my error is bounded and I'm
31:30 - 32:00 scaling my bit by a sufficiently large scaling Factor then what happens is that the error does not cause enough perturbation for a zero to flip as one or one to flip as zero right when can one flip a zero if it wraps around q and comes back because we are in z q