Another fantastic video. I run an Oxbridge Engineering activity at my school and the kids, who have never done anything with information theory before, absolutely love these videos and topics.
@@ArtOfTheProblem 16 to 18 year olds. It's always great when a new student comes in and the subject is broached. They have this wide eyed look of 'This is a field!?'
People like you contribute to making the internet a place where anyone can learn no matter where you come from or what your background is. Great explanation!
Absolutely amazing! I love these videos. For some one who didn't study computer science formally, rather ended up in this profession by interest and coincidence, these videos are a gold mine. Please keep them coming. I am sure I am not alone.
The wikipedia article is sofa king we todd did. Im a literal mathematician, degree and all, and I couldnt make heads or tails of that gibberish. So much for the wikipedia being written for laymen. A mathematician couldnt make sense of it. The wikipedia articles are clearly written for people who are NOT laymen in the field. This video immensely IMMENSELY simplifies whats going on. Great video.
Please continue this with a followup describing how a consensus group can distributively sign a message without anyone learning the secret and risk signing other messages without consensus. As always your videos are the best.
Wow this was very informative, I love it. It's amazing how easy you break it down. I hope you gain more exposure so students at Universities or anyone for that matter can get a better understanding of how something so complex can easily be explained. It really shows the depth of your knowledge on such topics.
I came across Shamir's secret sharing scheme a few weeks ago, but this explanation makes everything crystal clear. I'd love to see more info on the modular arithmetic version of the polynomial this scheme uses. I'd also love to see an explanation as to why knowing less than k shares reveals no information. This is not the case for the Real polynomial example (it's not 100% clear what it means to be a random point on the R^2 plane, but a naïve y-axis encoding seems like it would leak some information based on the statistical properties of the rest of the points. Even worse if the numbers are integers, or at least rational.)
I don’t think any information is leaked, although I’m not certain. Imaging two points are required (secret line). Having just one point without knowing the slope means any number on the y axis could be the correct secret (all are still equally likely). The same logic should apply for higher order secret curves. Any number of possible curves would remain equally likely until as many points as required are know.
Also, I believe the numbers would need to be integers to be fully solveable. (You wouldn’t want to store a secret non-integer anyways...) That’s okay because even though there are fewer integers than real numbers, there is still an infinite amount of integers.
I think the more severe issues start with two points onward (especially on an integer lattice). I do think there may be something happening depending on the way the line is chosen with k=2 (uniformly random slope vs uniformly random angle vs random point on the plane, etc.), which may bias certain slopes and/or points, and revealing information if the attacker knows (or can guess) the way the points were generated. My intuition fails me since infinities are involved, and I don't know a way to think of a limit that doesn't inherently bias the calculation (that may actually be impossible, consider the limit of choosing a random point uniformly on differently shaped rectangles as they grow to cover the whole R^2 plane - different shapes of the rectangle will lead to different biases for the chosen slope)
animowany111 two thoughts: 1) I just checked. The paper linked in the description states that no information is leaked even with k-1 points known. This may not be 100% true in practice. Not sure. 2) I agree that the way the secret curve / points are chosen would definitely affect the nature of how secure this method is, and I don’t know how best that could be done. You also correctly point out that the ‘random points’ would of course need to come from some predetermined rectangle on the R^2 plane, and that would limit the possible curves that could be solutions. Perhaps a higher dimensional space is used in practice, or the rectangle is chosen to be large enough that it is ‘secure enough’ that finding the solution would be impractical given modern computer power. 🤔 lots to consider.
I’d never thought about this problem before. The solution really is elegant. I’d love to know more details about how the curve is found from the points given. I feel like that is something I learned at one point but no longer remember. EDIT: The method used for finding a curve that exactly fits a set of points is the Lagrange interpolation polynomial. You would need to know the order of the function for it to work (which you should know anyway).
Wow, this video is amazing, I also feel clever after watching this video. Your videos make me so curious about learning new things and give me a reason why one should be learning and how to proceed for the solution to a new problem.
that's really inspiring to hear, thank you for sharing this. I love hearing that these make people feel smart as my goal for this channel was to address how stupid I felt during many lectures in my life.
This is a great video, thank you! I think I understand how to generate the secret, generate the shares, and distribute the shares but only if the generation is done by one party. That would mean that the whole secret is known to that originating party. Can anybody point me to a resource for how to do this without such a centralized originator?
Very nice indeed! I just guess the random points are made a bit 'smarter' as a random pont with low X value closes in to the correct Y value. All in all a very recommendable video!
Great video. I have an idea of non transferable information. Choose a random face from a 10x10 grid, repeat for 3 grids. You try and describe 3 faces from 300 - can't be done. Only the original person has this one unique key. Is this an original idea? I imagine a bank manager tied up at home, threatened.. but 100x100x100 x(correct sequence) makes it impossible for them to give over the key - which cannot be brute forced..
If you love this channel, and appreciate this work for what it is -- an unusual kind of art that can only be produced by a technically fluent mind (a mind that can choose to do any number of other things, things that would compensate him handsomely) -- please support Brit by pledging REAL DOLLARS to his patreon: www.patreon.com/artoftheproblem I am a patron and I approve this message without reservation!
That got me thinking. Could there be a master authorizator point which doesn't belong to the same curve but implements the curve on a different height. The idea being that you just move the curve until it lines up with the master authorizator. Are there any flaws in this idea?
1:48 so x+1=y and y does not contain information about x ? Aren't we sure y contains x plus some number which is some information about x ? For example if we have y that is 10 characters long we can be sure x is not million characters long, unless they are all the same or majority is the same, which is some information. Also diving into cryptography and compression algorithms we can pretty much know min and max characters that x can have just looking into y. Also we can know that y is not the image if it has less than some amount of characters which also is some information about x the original secret ..... so we can know bunch of stuff or information about x by analyzing y and statement that it does not contain any information about x is simply not true ! There always is some information in everything, you just need to look hard enough.
The 12-word original mnemonic code was split using the Shamir Secret Sharing scheme with 3 out of 5 threshold schemes were used. This means that any three shares are sufficient to restore the original mnemonic code. The goal is to break the Shamir Secret Sharing scheme or break the implementation of software for SSSS. We publish 2 of 3 shares needed to restore the original mnemonics. Share 1: session cigar grape merry useful churn fatal thought very any arm unaware Share 2: clock fresh security field caution effort gorilla speed plastic common tomato echo
This is art.
Another fantastic video. I run an Oxbridge Engineering activity at my school and the kids, who have never done anything with information theory before, absolutely love these videos and topics.
Thrilled to hear this. What age group?
@@ArtOfTheProblem 16 to 18 year olds. It's always great when a new student comes in and the subject is broached. They have this wide eyed look of 'This is a field!?'
@@Virgilijus87 wonderful to hear. I didn't get proper exposure until I was 21!
People like you contribute to making the internet a place where anyone can learn no matter where you come from or what your background is. Great explanation!
Absolutely amazing! I love these videos. For some one who didn't study computer science formally, rather ended up in this profession by interest and coincidence, these videos are a gold mine. Please keep them coming. I am sure I am not alone.
Thanks to you I'm learning information theory on the go. I'm glad to be alive in the information age!
The wikipedia article is sofa king we todd did.
Im a literal mathematician, degree and all, and I couldnt make heads or tails of that gibberish.
So much for the wikipedia being written for laymen. A mathematician couldnt make sense of it. The wikipedia articles are clearly written for people who are NOT laymen in the field.
This video immensely IMMENSELY simplifies whats going on. Great video.
I find these explanations incredible ❤️
Never thought I would see coordinate geometry come up like this. I knew it had applications but this is golden content ❤
right, this is one of the better cases
Please continue this with a followup describing how a consensus group can distributively sign a message without anyone learning the secret and risk signing other messages without consensus. As always your videos are the best.
thank you for the suggestion!
This is simple and brilliant. And simply and brilliantly explained.
thank you for the support ever
Was not expecting this video to be nearly as good as it was. Absolutely exceptional explanation, thank you!
appreciate the feedback :)
Wow this was very informative, I love it. It's amazing how easy you break it
down. I hope you gain more exposure so students at Universities or anyone
for that matter can get a better understanding of how something so complex
can easily be explained. It really shows the depth of your knowledge on such
topics.
Thanks so much for sharing
@@ArtOfTheProblem You're welcome!
A small token of appreciation 😊
thank you! much appreciated
Excited for you to see new video: ua-cam.com/video/PvDaPeQjxOE/v-deo.html
Yes! Fantastic video as always. Love the information theory videos especially.
your video was a really great way to demonstrate quadratic equations. As well as providing an intuitive use case
I came across Shamir's secret sharing scheme a few weeks ago, but this explanation makes everything crystal clear. I'd love to see more info on the modular arithmetic version of the polynomial this scheme uses.
I'd also love to see an explanation as to why knowing less than k shares reveals no information. This is not the case for the Real polynomial example (it's not 100% clear what it means to be a random point on the R^2 plane, but a naïve y-axis encoding seems like it would leak some information based on the statistical properties of the rest of the points. Even worse if the numbers are integers, or at least rational.)
I don’t think any information is leaked, although I’m not certain. Imaging two points are required (secret line). Having just one point without knowing the slope means any number on the y axis could be the correct secret (all are still equally likely).
The same logic should apply for higher order secret curves. Any number of possible curves would remain equally likely until as many points as required are know.
Also, I believe the numbers would need to be integers to be fully solveable. (You wouldn’t want to store a secret non-integer anyways...) That’s okay because even though there are fewer integers than real numbers, there is still an infinite amount of integers.
I think the more severe issues start with two points onward (especially on an integer lattice).
I do think there may be something happening depending on the way the line is chosen with k=2 (uniformly random slope vs uniformly random angle vs random point on the plane, etc.), which may bias certain slopes and/or points, and revealing information if the attacker knows (or can guess) the way the points were generated.
My intuition fails me since infinities are involved, and I don't know a way to think of a limit that doesn't inherently bias the calculation (that may actually be impossible, consider the limit of choosing a random point uniformly on differently shaped rectangles as they grow to cover the whole R^2 plane - different shapes of the rectangle will lead to different biases for the chosen slope)
animowany111 two thoughts:
1) I just checked. The paper linked in the description states that no information is leaked even with k-1 points known. This may not be 100% true in practice. Not sure.
2) I agree that the way the secret curve / points are chosen would definitely affect the nature of how secure this method is, and I don’t know how best that could be done.
You also correctly point out that the ‘random points’ would of course need to come from some predetermined rectangle on the R^2 plane, and that would limit the possible curves that could be solutions.
Perhaps a higher dimensional space is used in practice, or the rectangle is chosen to be large enough that it is ‘secure enough’ that finding the solution would be impractical given modern computer power. 🤔 lots to consider.
Thank you for your work. Simple, elegant and to the point.
That is a brilliant solution! How have I not heard of this before?
Loved it. I would like to see just a little more detail. Thanks for all the hard work.
Truly beautiful and simpler explanation of secret behind keeping secret among parties.
Thanks for the easy-to-understand explanation and great visualisation!
stay tuned for more!
the best crypto video i have ever watched.
just posted new video on RL ua-cam.com/video/Dov68JsIC4g/v-deo.html
Thanks!
I really really appreciate thisn
This was an incredible explanation and the visuals were beautiful, simple, and intuitive. Thank you so much!!!
thrilled to hear you liked this video. it was definitely a fun one to make
I’d never thought about this problem before. The solution really is elegant.
I’d love to know more details about how the curve is found from the points given. I feel like that is something I learned at one point but no longer remember.
EDIT: The method used for finding a curve that exactly fits a set of points is the Lagrange interpolation polynomial. You would need to know the order of the function for it to work (which you should know anyway).
You could just solve the system of linear equations obtained from substituting the known points into the equation of the curve.
Excellent way to visually explain these concepts..Loved it. Great job.
appreciate the feedback, the next one we are doing is on recommendation systems
I love clearly explained design. Well done!
Salute for the video. Excellently explained for people who just needs to get the basic idea.
appreciate the feedback
Link to the entire great papers series: ua-cam.com/play/PLbg3ZX2pWlgJOTf5YXNq-rdXXuUkJTXHm.html
Perfect! Best explanation eveeeer! It makes concepts soooo simple to understand! Really amazing job!!
Wow... Such an amazing, easy to understand explanation... Thanks so much for this!
Wow, this video is amazing, I also feel clever after watching this video. Your videos make me so curious about learning new things and give me a reason why one should be learning and how to proceed for the solution to a new problem.
that's really inspiring to hear, thank you for sharing this. I love hearing that these make people feel smart as my goal for this channel was to address how stupid I felt during many lectures in my life.
This is the best video I've seen in my life
wow, that's no small compliment :)
It would be interesting to learn how does the curve map to a Galois field for the practical application.
I've known the abbrv SSS for sometime, but I can't believe I've only learned about this in my 40s.
I know the feeling
Great video as always, Brit.
I wonder what Adi Shamje must've felt when he cane up with this... fucking mind blowing
i know!
What happens when we expand this way of thinking into 3d-space? Is that something that is used for even more security?
That was amazing man, thank you!
glad you found this!
This is a great video, thank you! I think I understand how to generate the secret, generate the shares, and distribute the shares but only if the generation is done by one party. That would mean that the whole secret is known to that originating party. Can anybody point me to a resource for how to do this without such a centralized originator?
Very nice indeed! I just guess the random points are made a bit 'smarter' as a random pont with low X value closes in to the correct Y value.
All in all a very recommendable video!
incredible. Thanks
Great video. I have an idea of non transferable information. Choose a random face from a 10x10 grid, repeat for 3 grids. You try and describe 3 faces from 300 - can't be done. Only the original person has this one unique key. Is this an original idea? I imagine a bank manager tied up at home, threatened.. but 100x100x100 x(correct sequence) makes it impossible for them to give over the key - which cannot be brute forced..
ohhh, interesting
I am happy for you to be coauthor, as by being a retired doctor I have no clout :)
masterful explanation
If you love this channel, and appreciate this work for what it is -- an unusual kind of art that can only be produced by a technically fluent mind (a mind that can choose to do any number of other things, things that would compensate him handsomely) -- please support Brit by pledging REAL DOLLARS to his patreon: www.patreon.com/artoftheproblem I am a patron and I approve this message without reservation!
So clear and precise
beautiful idea
That got me thinking. Could there be a master authorizator point which doesn't belong to the same curve but implements the curve on a different height. The idea being that you just move the curve until it lines up with the master authorizator. Are there any flaws in this idea?
what a great channel!
Good explanations thank you! Do you know of a real implementation of this algorithm?
Exploring future chain abstraction concepts brought me here.
interesting, can you say more??
well explained...thanks😇
thank you. fantastic video
Magnificient video
appreciate the feedback
great video
thanks, great explanation
Thank you very much.
thanks, king
Good Video Thanks. But in 2:22 you did the sum wrong. you don't add digit by digit from left you do that from the right.
Brilliant video
Thanks for video. I've come here cause of Cicada 3301 puzzle
Please can you make a video on Zero Knowledge Proofs.
thanks for the suggestion, oddly enough I made a strange student short film on this around 10 years ago right before I started this channel.
So good!
but, are high order equation always solvable?
Beautiful
1:48 so x+1=y and y does not contain information about x ? Aren't we sure y contains x plus some number which is some information about x ?
For example if we have y that is 10 characters long we can be sure x is not million characters long, unless they are all the same or majority is the same, which is some information. Also diving into cryptography and compression algorithms we can pretty much know min and max characters that x can have just looking into y. Also we can know that y is not the image if it has less than some amount of characters which also is some information about x the original secret ..... so we can know bunch of stuff or information about x by analyzing y and statement that it does not contain any information about x is simply not true ! There always is some information in everything, you just need to look hard enough.
Holy shit, why can't we teach math this way? Now it has reason to me, and I'm interested.
glad to hear it :)
why this person disliked the video.Saying that he thought that it is download button is NOT A JOKE.
amazing
Wowwww ❤
2:10 You adding wrong 5+6 = 11 so next number supposed be 4+ 1+ 1 = 6 so score is 96174478 but not 95174478
Awesome.
Thanks
yeah, subscribed.
welcome to the family
would love if you could help share my newest video: ua-cam.com/video/5EcQ1IcEMFQ/v-deo.html
Pls upload Video for each week.
please support via patreon to help make that a reality: www.patreon.com/artoftheproblem
so good
I HATE theory. It drives me up a wall, but this was really cool somehow.
ThanQ for sharing!
I remember art of the problem. like the videos are extremely good but no one knows what it is. its like a secret
good vid tnx
7:56
If we ignore the farthest two secret shares on the X axis and take the other three isn’t the secret revealed?
Wow
The 12-word original mnemonic code was split using the Shamir Secret Sharing scheme with 3 out of 5 threshold schemes were used. This means that any three shares are sufficient to restore the original mnemonic code. The goal is to break the Shamir Secret Sharing scheme or break the implementation of software for SSSS. We publish 2 of 3 shares needed to restore the original mnemonics.
Share 1:
session
cigar
grape
merry
useful
churn
fatal
thought
very
any
arm
unaware
Share 2:
clock
fresh
security
field
caution
effort
gorilla
speed
plastic
common
tomato
echo
1 point of failure? that would be multiple points of failure
Why I can't give 2 or more likes to this video?
appreciate it!
Cool ill make a secret polygon
elo
Š ê ç r ē t l ï n è
it’s secret
Second ^_^
wow
@@J0Y22 thanks for in the way