Thanks for this video, I could finally got the concept of the Shortest Vector Problem and Closest Vector Problem. I really appreciate your explanation.
Fabulous! (could have done with a little more info about the congruity of the good/bad bases choice but- hey, I'm happy). Also- I had a dream once where I felt I may have invented (some parts of) a novel scheme for asymmetric crypto - take a point (the message) and perform any (reasonable) number of geometric transformations of the point (e.g. mirror in the X-axis, translate by vector V etc etc), the resulting point is the encrypted message- it is infeasible to recover the original message from this point and I expect there is a way to partition the transformations into public/private halves. After thinking more, I thought that I had only probably reinvented an inefficient implementation of ECC but now I think that I had only probably reinvented an inefficient implementation of Lattice-based crypto!. True story!!! ;))
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.
finally. an educational video without ear-splitting intros, pointless soundbites and effects and people speaking broken english. keep up the simple and good work
Hi, I'd like to ask you is the green point is target point and the point that is closest to green point represents the secret information, right? Many thanks.
What's to stop me taking choice linear combinations of the public basis so that it spans the space more efficiently? I understand it would be a large set of vectors, but it doesn't seem like a problem whose complexity grows fast
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
My brain keeps on wanting to try to work out an easy way to solve the shortest vector problem, because it feels like it should be simple. I guess I should nurture that kind of thinking, but it feels weird already knowing that it isn't before starting. I keep on thinking of possible steps to take, but I can also begin to imagine how they could be countered on purpose.
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 :)
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.
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?
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
* 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.
I believe, because it would be also a solution to the closest vector problem. If you knew how to "normalize" the bad basis, it should drastically reduce the search space. Also, I believe you would be able to induce to the "goodest basis" which I think would be the easiest one to solve the problem with
Hold on there my math senses tingling by the very definition of the whole number lattice that you’ve described in these examples doesn’t that mean that while it may take infinite steps to reach somewhere every whole number point on the plane or in the quote unquote probability phase space is reachable so any whole number coordinate is a valid solution. Therefore, the closest or shortest vector is one whole number unit away and thiswould hold true for n dimensions.
This channel is wildly underrated!
So good to see you back on UA-cam 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
Great presentation! The basic concept of lattice-based cryptography looks simple which I think is good for analyzing it in terms of security.
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!
Great quality content: very well structured and articulated, I hope you do more videos, you have a gift!
Thanks for this video, I could finally got the concept of the Shortest Vector Problem and Closest Vector Problem. I really appreciate your explanation.
Fabulous! (could have done with a little more info about the congruity of the good/bad bases choice but- hey, I'm happy). Also- I had a dream once where I felt I may have invented (some parts of) a novel scheme for asymmetric crypto - take a point (the message) and perform any (reasonable) number of geometric transformations of the point (e.g. mirror in the X-axis, translate by vector V etc etc), the resulting point is the encrypted message- it is infeasible to recover the original message from this point and I expect there is a way to partition the transformations into public/private halves. After thinking more, I thought that I had only probably reinvented an inefficient implementation of ECC but now I think that I had only probably reinvented an inefficient implementation of Lattice-based crypto!. True story!!! ;))
this video helped me so much with my discrete mathematics exam! thank you!
This video saved me a lot of time and confusion. Thank you so much for your great videos ♡♡♡
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.
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!
the best explanation of lattice in youtube 🔥
Stunningly great video. Super clear.
such a beautifully well done video. Thank you for taking an intimidating concept and making it accessible.
Very good video, glad this is the first video that showed up when I searched for this topic
Well-articulated! Thank you.
Fascinating and well explained. Thank you
Brilliant
This is a great video
Amazing video, really really good. Thanks so much!!!
Thank you so much. It's so simple and understandable
very pleasant to watch.
Great video
c'est si clair et si bien expliqué. merci beaucoup !
5:02
Great video!
finally. an educational video without ear-splitting intros, pointless soundbites and effects and people speaking broken english. keep up the simple and good work
This video really helped, thanks!
You videos are amazing and I recommended it to every person interested in cryptography, keep up the great work
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.
Horrors beyond human comprehension.
Hi, I'd like to ask you is the green point is target point and the point that is closest to green point represents the secret information, right? Many thanks.
Thanks for video
Awesome!
I just was getting notifications from PBS Infinite Series. And there you are.
Plan to restart those? Or production pace is too exausting?
this was amazing!
she just broke my brain and my encryption 😂
Thanks for the follow up on PQC standardization procedure. Maths part is always interesting?
I love your videos .keep up the good work.
What's to stop me taking choice linear combinations of the public basis so that it spans the space more efficiently? I understand it would be a large set of vectors, but it doesn't seem like a problem whose complexity grows fast
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
My brain keeps on wanting to try to work out an easy way to solve the shortest vector problem, because it feels like it should be simple. I guess I should nurture that kind of thinking, but it feels weird already knowing that it isn't before starting.
I keep on thinking of possible steps to take, but I can also begin to imagine how they could be countered on purpose.
This video is so cool 😎 thx
Regular people: just another thing to look at.
Mathematician: why can't I make a mathematical model of this
are you one from pbs infinite series i was waiting for your video
Can you provide books and references to read more on this? Also I'm planning to take courses on this. Please do recommend. Thanks. :)
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 :)
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.
If you know the bad basis and the closest vector is it easy to verify?
lord i just found you again. i've missed you. where ya been?
Could someone please share KYPER technique that perform the encryption and decryption?
Why was I not notified you had this channel... bad youtube algorithm!
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?
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
* 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.
Wow!!
Why can't you use the bad basis to make another good basis and use that to solve the closest vector problem?
I believe, because it would be also a solution to the closest vector problem. If you knew how to "normalize" the bad basis, it should drastically reduce the search space. Also, I believe you would be able to induce to the "goodest basis" which I think would be the easiest one to solve the problem with
0:41
Anybody here heard about fourier trans in crystalography? Or about voronoi triangulation?
Yes, and I also know about the infamous Phase Problem in crystallography. That is integral to the inverse Fourier Transform, and not having it is huge
@@MusingsAndIdeas i havent heard about phase problem - must look it up - thanks :)
I love you ❤
Hold on there my math senses tingling by the very definition of the whole number lattice that you’ve described in these examples doesn’t that mean that while it may take infinite steps to reach somewhere every whole number point on the plane or in the quote unquote probability phase space is reachable so any whole number coordinate is a valid solution. Therefore, the closest or shortest vector is one whole number unit away and thiswould hold true for n dimensions.
Why is it always Alice & Bob
Because the alphabet goes, A, B, C...
Because ladies come first ;)
What happened? Where are youu?
Why can't the bad basis simply be orthonormalized?
You could use Gram-Schmidt but the orthogonal vectors aren't guaranteed to be short, so the basis is still "bad" in a sense
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
Bravias lttice
It would be great to see more Americans involved in the tech industry. Imagine the same presentation from someone from India!
good one, thanks.