Lattice-based cryptography: The tricky math of dots
HTML-код
- Опубликовано: 6 авг 2024
- Lattices are seemingly simple patterns of dots. But they are the basis for some seriously hard math problems.
Created by Kelsey Houston-Edwards (www.kelseyhoustonedwards.com)
Sponsored by Wire (www.wire.com)
________
Post-Quantum Cryptography: • Post-quantum cryptogra...
Learning with Errors: Coming January 5, 2023
________
Timestamps
0:00 - Post-quantum cryptography introduction
0:58 - Basis vectors
1:55 - Multiple bases for same lattice
2:50 - Shortest vector problem
4:32 - Higher dimensional lattices
4:59 - Lattice problems
5:55 - GGH encryption scheme
8:00 - Other lattice-based schemes
________
What more information about lattice-based cryptography? Check out the many resources as thelatticeclub.com/
Lattice-based cryptography (blog, part 1): writing.chelseakomlo.com/gent...
Lattice-based cryptography (blog, part 2): writing.chelseakomlo.com/a-ge...
GGH-Encryption Scheme (Wiki): en.wikipedia.org/wiki/GGH_enc...
Security of GGH Encryption Scheme (research paper): link.springer.com/chapter/10....
This channel is wildly underrated!
So good to see you back on RUclips talking math again, Kelsey!
Oh I wonder why her voice sounds familiar!
I'm so happy to find you again😢😢😊😊
this may be the most accessible explanation of lattice crypto on the Internet
This is a phenomenal video. Thank you so much for take the time to clearly explain a complex topic. I'm very grateful for your work!
I just found your channel from the PBS Infinite Series. It made my day to learn that you still make videos! I hope you keep uploading!
the best explanation of lattice in youtube 🔥
Stunningly great video. Super clear.
Thanks for this video, I could finally got the concept of the Shortest Vector Problem and Closest Vector Problem. I really appreciate your explanation.
Fascinating and well explained. Thank you
This video saved me a lot of time and confusion. Thank you so much for your great videos ♡♡♡
Great presentation! The basic concept of lattice-based cryptography looks simple which I think is good for analyzing it in terms of security.
Well-articulated! Thank you.
I love your videos .keep up the good work.
such a beautifully well done video. Thank you for taking an intimidating concept and making it accessible.
Amazing video, really really good. Thanks so much!!!
Great video!
Awesome!
You videos are amazing and I recommended it to every person interested in cryptography, keep up the great work
Very good video, glad this is the first video that showed up when I searched for this topic
Thank you so much. It's so simple and understandable
very pleasant to watch.
Thanks for video
This video really helped, thanks!
good one, thanks.
Great video
c'est si clair et si bien expliqué. merci beaucoup !
this was amazing!
This video is so cool 😎 thx
Thanks for the follow up on PQC standardization procedure. Maths part is always interesting?
Very informative.. thanks for putting together the insane math concepts in an easy to understand capsule!! I have one question though, which could be dumb 🙃 The strength with the algorithm is on keeping the 'good' basis confidential, and am curious on how it could be shared between Alice & Bob, without compromising it 🤔
It's not shared. As it was said, Alice would receive a bad basis from Bob as a public key for encryption. The point is, no matter how bad basis is, its easy to combine vectors and get the point. But to decompose that point to the combination is VERY hard, having only bad vectors. Decryption is run by the owner of good basis to receive messages. This is how asymmetrical keys work
Wow!!
I think there was an interesting problem we just blew past in this video around 6:05, where Alice sets up two bases with the same lattice. Is there an easy algorithm that allows someone to generate the "bad" basis from the "good" basis in a non-reversible way? Or was the fact that there's a way to reverse that the algorithm the "sneakiness" you allude to around 7:50?
I am not an expert on this, but I found the papers and the answer appears to be:
1) yes, several
2) no.
GGH (1996) generate their bad basis by multiplying the good basis by some randomly generated unimodular (determinant ±1) matrix and picking a result in which the basis vectors are sufficiently parallel (the threshold value is a parameter to their scheme and is called "dual orthogonality defect" of the unreduced basis). They discuss a few ways to generate these unimodular matrices - for example you can put 1's along the diagonal, random numbers along the middle row or column, and zeros everywhere else.
Nguyen's (1999) sneakiness is to solve the closest vector problem modulo "some well chosen integer".
In addition to the bad basis, Alice needs to share a maximal error e, so that Bob knows how far from his lattice point the encrypted point can be. Nguyen then solves the problem modulo 2e which is much easier, and uses this to recover information with high probability.
@@TheAqissiaq I appreciate you doing the legwork on the actual papers. The unimodular matrix transformation seems reasonable, although I still have a nagging feeling that it would be tractable reversible if Eve knew the implementation they were using.
Knowing that the maximal error is part of the public key also makes me feel a little better; I was thinking the "closest point" problem could be arbitrary under most lattices across a rational coordinate system given mutually prime bases, but having a fixed maximal error solves that issue. I was wondering if there was some principle of linear algebra that allowed for conclusive confirmation of the closest possible point I wasn't privy to.
The problem is hard to solve in the general case, because there _is_ no "good" basis. Given two vectors that are near-parallel, it is possible to reduce one with respect to the other so they are more orthogonal. In higher dimensions, it can be a bit trickier.
are you one from pbs infinite series i was waiting for your video
I was really disappointed at the lack of visual representation of 17-dimentional lattice at 4:53 :(
you should be grateful she didn't show it. It would have caused anyones head who viewed it to explode.
How could Bob create the list of all lattice points using bad basis?
If everyone having bad basis can create the lattice, what is stopping them from finding the closest lattice point just by visual inspection?
Could someone please share KYPER technique that perform the encryption and decryption?
If you know the bad basis and the closest vector is it easy to verify?
finally. an educational video without ear-splitting intros, pointless soundbites and effects and people speaking broken english. keep up the simple and good work
All lattice propositions have been dropped by NIST at round 4, what does this imply for those protocols?
The thing is I was thinking of some “lattice” based encryption method a while ago. And then I got to thinking… it’s all just perceived as a lattice based on a data structure and algorithm. I mean… it’s a lattice in our heads because of how we think. But in a computer it’s literally just abstract bits lol.
They already chose to standardize some algorithms, including lattice-based ones. The fourth round is being used to explore additional non-lattice algorithms. It's slightly different than the previous rounds.
Regular people: just another thing to look at.
Mathematician: why can't I make a mathematical model of this
I just was getting notifications from PBS Infinite Series. And there you are.
Plan to restart those? Or production pace is too exausting?
Can you provide books and references to read more on this? Also I'm planning to take courses on this. Please do recommend. Thanks. :)
5:02
Anybody here heard about fourier trans in crystalography? Or about voronoi triangulation?
How do you create this kind of representation and animations of point lattices? I am writting a university project about post quantum cryptography, and I would like to introduce pictures and visualizations about lattices. Thanks :)
You'd think going from a good basis to a bad basis would be easier! Like translating a vector! 🤔
Otherwise very nicely explained, won't be for everyone but perfect level for me! Thanks
Why is it always Alice & Bob
Because the alphabet goes, A, B, C...
I love you ❤
* Two different looking basis vectors can generate same lattice.
* Shortest Vector Problem: The point constructed by basis that is closest to origin, other than origin
* Closest Vector Problem: Similar to SVP, but the point can be anything, not only origin.
Why can't the bad basis simply be orthonormalized?
0:41
wawawewa, it's a very nice!
noooooooooooo why are you gone again?!? why did I not find the channel earlier? whhhhhy
edit: oh, I am so sad