Learning with errors: Encrypting with unsolvable equations
Вставка
- Опубліковано 16 лип 2024
- Learning with errors scheme.
This video uses only equations, but you can use the language of linear algebra (matrices, dot products) to discuss lattices and learning with errors. Check out the resources below for more information.
Created by Kelsey Houston-Edwards (www.kelseyhoustonedwards.com)
Sponsored by Wire (www.wire.com)
________
Post-Quantum Cryptography: • Post-quantum cryptogra...
Lattice-Based Cryptography: • Lattice-based cryptogr...
________
Timestamps
0:00 - Introduction
0:35 - Learning without errors
1:58 - Introducing errors
3:36 - Modular arithmetic
3:59 - Encrypting 0 or 1
7:14 - Relationship to lattices
________
Modular arithmetic (wiki): en.wikipedia.org/wiki/Modular...
Modular arithmetic (Khan Academy): www.khanacademy.org/computing...
Modular arithmetic (video, blackpenredpen): • What does a ≡ b (mod n...
LWE (expository notes): cims.nyu.edu/~regev/papers/lw...
LWE (lecture): • The Learning With Erro...
Encryption from LWE (lecture notes): courses.grainger.illinois.edu...
Kyber (website): pq-crystals.org/kyber/index.s...
This is the first video I’ve seen on this channel. I saw you on infinite series and liked those videos. It’s a shame you don’t have more subscribers. Someone like Matt Parker or Brady from Numberphile should have you on to get the word out.
Awesome video! This is the first thing I've seen which actually covers the nitty-gritty of post-quantum cryptography. I'd love to see more videos :)
hopefully you create more of this great content!
Such a great series. I hope we see more from this channel.
Imprecise information to get the enciphered data "close enough" for Alice to read it is a fascinating approach, but I always have this gnawing thought at the back of my mind that these kinds of encryption must have a statistical attack that also gets you close enough. Of course, that's the same bit in the back of my head that says there must be a counter example to the four-color theorem and that surely I can write a short bit of code that computes Ramsey(6,6) in an afternoon.
I would assume it would depend on how big the error is. In the example with 44, if you sum the equations then you also sum the errors, and if the summation of errors gets you closer to 44 than to 0 (meaning >= 22) then it seems like it would become difficult to tell a 0 and a 1 apart. Since there are 10 equations in her example, if the errors are randomly generated and the equations they select are also randomly generated, then the error range could not be greater than +/- 2 because otherwise it would be technically possible (although highly unlikely), let's say it was +/- 3 that the private key holder's random number generator spit out 3 as the error for every equation and the public key holder's random number generator select to use every single equation, and the total error would be 30, making a 0 they encrypt falsely read as a 1 since it would be closer to 44 than to 0. That would mean you could make it absolutely impossible to run into such a scenario if, given m is the modulus and n is the number of equations in the public key and the +/- range of our error is e, that e < ⌊m/n/2⌋. I don't have any idea if this is how they actually do it but if this is satisfied it would not be possible in even the worst case scenario for the error to ever be too great to cause incorrect decryption. You could probably also just verify the errors aren't too large in the worst case and regenerate them if they are.
Your whole channel is very interesting. I discovered many things thank to you. So thank you for your work !
The cleanest explaination with simple examples, thank you
I'm so happy you are back on youtube :)
Really hope this is your own channel and that it will grow bigger than before.
I'm very grateful to you for clear explaination of such diffcult crypto concepts which is really helpful for my academic work!
Pretty informative and clean video. It’s unreal to imagine that you’ve only made 5 videos given how good your edits are. And the content is delivered in a very intuitive and gentle introduction kind of fashion. Thanks for this and hope your channel grows and you gain steam soon :)
I have rarely seen a video where i understood so much and so little at the same time.
Awesome video! Going with the intuition first without going into too much details. I wish to see more in the future.
amazing video, amazing series, and amazing effort.
Thank you so much for the illustration, really helped so much.
Great videos! I understand it very well now. I'm now using this knowledge to develop the encryption algorithm with c++.
this short video series was very informative on learning the core of PQC algorithms. Especially since now apple after signal implemented a PQC algorithm.
Very clear explanation! Thank you!
Fantastic videos! You make absurdly difficult subjects extremely easy to understand!
Linear algebra is not absurdly difficult. It’s high school level, at least in all high schools except in the US perhaps.
@@kosterix123 in all first world* high schools may be bro
Excellent video! Thank you.
Well-articulated! Thank you.
Thank you so much! Video is intuitive enough to cover working principles of Post Quantum Cryptography. :)
Your video is actually the 5000th video that i hit like on UA-cam. I hope you have some course about quantum computing. You are the best ❤❤❤
Please do consider going on Numberphile! Your content is amazing!
Loved the video!
LWE in almost full clarification😊Warm Congrats on your output❤
First sponsorship I ever saw with less than 5k subscribers.
nice work! thanks : )
What an amazing explanation!!! I believe you should teach Mathematicians how to teach!
This only works with very short messages.
It’s not generalizable to, say, a one page letter.
It’s equivalent to sending a blurry image that the recipient can sharpen but so could a mitm.
I’m not so sure this is as unsolvable as you think, and if it were, both Alice and Bob would need a way to share the actual errors securely in the future.
Nice work, as always, Kelsey. Though, I'm not sure that I'm sold on this as a concept for secure communications.
5:15 but couldnt malkob(bobs bully) just calculate that 30x+67y+53z+24w=19(mod 89) is 0 and then check if it is equal to 0
Thanks! Would those noisy linear constraints be solved with linear regression?
wawawewa, it's a very nice!
In the lattice video you stated, that with a trick it is easily broken. How does lattice become safer with LWE and why do I need lattices then anyways? Wouldn‘t LWE alone be enough then?
Thanks for the video, maybe someone can enlighten me regarding my question. 😊
When Bob adds 44 to encode a "1", how do we know that it results in a point that is far from all the lattice points? Is there an argument to show this?
Hey! Love the channel so far. I remember you from infinite series and I’m glad you are back on UA-cam.
The way you present the algorithm it would be trivial for the attacker to find what combination of the equations were used to recover the sent bit. But I suppose that if you make it not just a sum but any linear combination the difficulty could be scaled as high as necessary.
can you explain how?
😍 i'm in love. Who said maths arent Beautyful ?
Why did you depart with pbs? Are there reasons that you can't share?
Can you describe the LPN problem also?
3:06
How would bob know the modulus number choosen is 89 so that he could add 44 ?
Anyone know what happened to the channel? or where to find similar ed videos?
How are things supposed to be bruteforce proof if the decryption is supposed to offline
can it be that some point on lattice has more than one closest points ?
I guess it's possible, but the receiver can always ask for a new point until the data is transmitted successfully. Thou I'm not sure if this can be exploited so the real lattice points can be eventually found.
Quantum cpu can break Aes-256 bits easly ! so why we focus on public/private key encryption resistant to quantum ?!!
I thought GGH based on ( closest vector ) lattice cryptography was insecure. Does learning with errors ( which sounded like is was equivalent to lattice cryptography ) somehow fix the insecurity ?
GGH can be reduced to a special case of the closest vector problem, which makes it insecure. But in general the closest vector problem is thought to be a secure basis for cryptography
@@chalktalkmath GGH signatures are insecure but I don't think it reduces to a special case of CVP. The idea is that if you observe a bunch of signatures, then you can recover the fundamental domain of the good basis. This can actually be fixed with SIS and a version of Babai's nearest plane algorithm that is not deterministic. GGH encryption is not insecure afaik (but not really used).
Why use lattice instead of this simpler approach?
Lets say mod 89 is denoted by Q, is Q made publicly known? From my understanding it shouldn't be made known because then I can just guess the message since there are only 2 possible outcomes.
Also when actually using this encryption technique, are there certain criteria? Like in RSA it requires prime numbers to be very large
Q is pubilcly known, but it doesn't mean that there are only two answers. The result of an equation can be any number, and that number mod 89 can go from 0 to 88, and to that number, 44 is added. the resulting number sent back to alice can be anything from 0 to 88, yes you added 44, but it doesn't mean that it's going to be closer to 88 or 0 since you are counting in mod 89. Since the equations chosen to mesh together by bob are random, the attacker doesn't know what that number should have been before adding 44 to it.
@@celivalg thank you for this answer, I assume when actually implementing this, new equations are to be made public everytime a new message is to be encrypted?
@@EastSideGameGuy I don't know for a fact, but I assume that this isn't the case, at least they don't need to. Here she showed it using a 4 dimensional vector, but imagine using a n dimensional vector, and sending thousands of equations, with Bob encrypting his message using dozens of equations. The shear combinations that makes are huge and an attacker won't be able to guess that in a reasonnable time.
Now, I doubt they actually store those equations between communications, rather I think the base vector stays the same, but the public key can be regenerated from those at random between different communications. But I don't think they need to. Remember that the equations themselves don't allow to get the base vector, and that base vector might be 1024 dimensional. So no random guessing.
waiting for more chalk talk. What happened why are you not posting the videos
cant wait for new videos to come
I dont know where you came from, but thanks.
5:15, the right side 19 is the sum of some public keys (b's). Can't an eavesdroper find that 19 is actually a sum of some public keys and know Bob is encrypting 0? 19+44 is not a sum of public keys so it's encrypting 1.
My guess is that in a real world scenario you would randomly pick the equations to sum and there would be a lot of them. So they could theoretically compute all possible combinations but if there's let's say 64 different equations then they'd have to compute about 18 quintillion unique combinations.
Is AES post-quantum?
All symmetrical ciphers like AES and ChaCha20 are because they are not based on the discrete logarithm problem. Only asymmetrical cryptography is.
@@amihart9269 I appreciate that answer, and I understand why you gave it and where it comes from.... but strictly speaking its not what I asked. I still dont know if quantum algorithms can crack AES any faster than a traditional computer.
@@leesweets4110 I'm not an expert, but from what I read online, quantum algorithms shouldn't be able to crack AES. I've read there are some attacks that can reduce the cracking time with conventional computers, but you can just use a longer key to avoid those. That's not the real problem though. AES being secure doesn't solve the problem of online cryptography. You won't be able to communicate securely with people you don't know and don't have a pre-shared-key with. That's the real problem that public-key-crypthography solved. Meaning you won't be able to order stuff online or do online payments. That said nobody knows what algorithms are possible with quantum computers. So maybe everything can be cracked using a quantum computer. Maybe our understanding of the quantum phenomena is incomplete and cloning quantum information is possible, so even quantum cryptography is vulnerable. I highly doubt that though.
256bit AES is considered post-quantum given the best known quantum algorithms. 128bit AES is post-quantum for the "medium term."
@@MadocComadrin I dont believe the size of the number is relevant...
It's not intuitive to me this would be a hard problem. Firstly isn't it just an optimisation problem and secondly haven't we reduced to problem from finding a solution to just finding the X public equations that make up the encrypted message?
The proof of its hardness related to lattice problems (approximate Shortest Vector Problem in particular) isn't straightforward, so it makes sense it might appear easy at first.
Do I know this girl from another educational channel on youtube?
So this has a major concern in my mind, while the math for this might be challenging when you step things up into more variables, there is also a deterministic quality to these problems when there is a large sample population of messages with the same secret key and mod. You would have to find a way to modify the secret key and mod and also communicate those changes over the network. This is ultimately the challenge, especially considering the passive listening that is happening over networks by state actors that have access to these large quantum computers. These problems will basically create a guaranteed back door for whoever controls the network and only really protect against people who are not the government.
How about we use less than 1 and more that 0 ? Start there, not such a GIGANTIC broad Vector. 0-44 WAY TO BIG...To late I have the patent.
What happened to this channel? The videos were quite good and then they just stopped.
Looks like this channel is going (went?) the way of Infinite Series. Such quality content, such poor reception. People have no taste.