Secret Sharing Explained Visually
Vložit
- čas přidán 19. 06. 2024
- The IEEE Information Theory Society presents an overview of Adi Shamir's 1979 paper on secret sharing. This is part of our series on the greatest papers from information theory. Link to playlist: • Information Theory col...
Paper featured in this video: users.cms.caltech.edu/~vidick/...
Support this program:
/ artoftheproblem
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!
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 ❤️
Thanks to you I'm learning information theory on the go. I'm glad to be alive in the information age!
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.
Thank you for your work. Simple, elegant and to the point.
Yes! Fantastic video as always. Love the information theory videos especially.
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.
your video was a really great way to demonstrate quadratic equations. As well as providing an intuitive use case
Thanks for the easy-to-understand explanation and great visualisation!
stay tuned for more!
Perfect! Best explanation eveeeer! It makes concepts soooo simple to understand! Really amazing job!!
Loved it. I would like to see just a little more detail. Thanks for all the hard work.
That is a brilliant solution! How have I not heard of this before?
I love clearly explained design. Well done!
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
Was not expecting this video to be nearly as good as it was. Absolutely exceptional explanation, thank you!
appreciate the feedback :)
Wow... Such an amazing, easy to understand explanation... Thanks so much for this!
This is simple and brilliant. And simply and brilliantly explained.
thank you for the support ever
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!
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
Excellent way to visually explain these concepts..Loved it. Great job.
appreciate the feedback, the next one we are doing is on recommendation systems
Great video as always, Brit.
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!
Truly beautiful and simpler explanation of secret behind keeping secret among parties.
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
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.
It would be interesting to learn how does the curve map to a Galois field for the practical application.
Awesome video! Loved it
That was amazing man, thank you!
glad you found this!
Salute for the video. Excellently explained for people who just needs to get the basic idea.
appreciate the feedback
thank you. fantastic video
Exploring future chain abstraction concepts brought me here.
interesting, can you say more??
masterful explanation
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.
what a great channel!
thanks, great explanation
Thank you very much.
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!
This is the best video I've seen in my life
wow, that's no small compliment :)
Brilliant video
So good!
So clear and precise
beautiful idea
well explained...thanks😇
great video
thanks, king
I wonder what Adi Shamje must've felt when he cane up with this... fucking mind blowing
i know!
Beautiful
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?
A small token of appreciation 😊
thank you! much appreciated
What happens when we expand this way of thinking into 3d-space? Is that something that is used for even more security?
amazing
Awesome.
Magnificient video
appreciate the feedback
Good explanations thank you! Do you know of a real implementation of this algorithm?
That got me thinking. Could 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?
so good
Thanks
Wowwww ❤
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!
Thanks for video. I've come here cause of Cicada 3301 puzzle
good vid tnx
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 :)
why this person disliked the video.Saying that he thought that it is download button is NOT A JOKE.
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.
ThanQ for sharing!
but, are high order equation always solvable?
Wow
Holy shit, why can't we teach math this way? Now it has reason to me, and I'm interested.
glad to hear it :)
yeah, subscribed.
welcome to the family
would love if you could help share my newest video: czcams.com/video/5EcQ1IcEMFQ/video.html
Link to the entire great papers series: czcams.com/play/PLbg3ZX2pWlgJOTf5YXNq-rdXXuUkJTXHm.html
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.
Pls upload Video for each week.
please support via patreon to help make that a reality: www.patreon.com/artoftheproblem
I HATE theory. It drives me up a wall, but this was really cool somehow.
Cool ill make a secret polygon
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.
I remember art of the problem. like the videos are extremely good but no one knows what it is. its like a secret
2:10 You adding wrong 5+6 = 11 so next number supposed be 4+ 1+ 1 = 6 so score is 96174478 but not 95174478
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!
7:56
If we ignore the farthest two secret shares on the X axis and take the other three isn’t the secret revealed?
elo
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
Second ^_^
Š ê ç r ē t l ï n è
it’s secret