Simple introduction to Shamir's Secret Sharing and Lagrange interpolation

A presentation part of the cryptography course at Chalmers University, 2015. Starting with simple examples, we introduce Shamir's Secret Sharing Scheme and how Lagrange interpolation fits in.
I may have misspoken at some points, but that's to keep you alert :)
Solution and follow up in • Shamir's Secret Sharin...

[@saadhaider9576]

This was a brilliant and simple easy to understand explanation that I was trying to look for but couldn't find elsewhere. Thank you so much for this!

[@abhijitchitnis8847]

Simply brilliant! Sets a gold standard for communicating mathematical concepts to the world at large. Never seen a better explanation of a concept of this importance being explained so effectively in well under 20 min.

[@aashrithh]

Awesome Explanation! Very crisp and clear! Thank you!!

[@YouTubist666]

This is an excellent explanation. It is the clearest video I have seen on this topic. Clear presentation, excellent production. Thank you very much for your efforts!!

[@madykz101]

Best description I've ever seen! I've been searching for this after watching tons of unclear videos

[@Shubham23PFocus]

great vide man , no one on youtube has explained in this depth

[@josephballesteros6698]

This was very helpful! The use of the delta functions helped clear up some of my confusions, and it made the formula easier to remember. Thanks!

[@gopikris2]

Phenomenally simple to understand. Wish I could explain concepts like this. Thanks !

[@JohnAlanWoods]

You need to produce more videos, these are super accessible! great job.

[@beback_]

So elegant! That was beautiful.

[@abhineethmishra]

This is the best resource to learn about this topic. Thank you!

[@VasundharaGhose]

you are life saver.. awesome.. very very clear and seriously now Lagrange interpolation is really my friend. thankuuu

[@JeremyLeeTW]

clear explanation! Thank you for my graduate degree

[@mhdmazzeh]

Man please do more, this is awesome!

[@bryanredd4654]

Excellent video! The slide at 16:08 solved my problem. I just goofed and wasn't doing the division correctly. Thank you!

[@HarshKumar-hy1ug]

this was simply awesome....best video on this topic

[@LeCaNiVideos]

Thank you, this helped me a lot! I'm taking the exam on Chalmers the day after tomorrow!

[@tobiaspeyton7911]

Amazing job explaining the best video on this topic I've seen

[@hind2202]

very simple explanation so clear, thanks

[@RocketSpecialist]

Amazing and clear video! Thank you!!!

[@ankushgupta630]

This was so good and brilliant . Loved It.

[@bangvu2127]

Thanks for the very short but sharp explanation. My prof explained this in 2 lectures and I still didn't understand a thing hahahaha

[@thulasigoriparthi]

Just beautiful. Thank you very much.

[@alwaysisnever5896]

your explanation is soooo good

[@NXVIINXVII]

Magic! This is fantastic

[@RhayaderGoesToTown]

Great explanation. Thank you

[@giangdang8115]

awesome! it opens my eyes!

[@jingz.9684]

Great explanation! Thanks!!!

[@richa2921]

Why dint i see this video earlier...awesome video ...keep it up

[@AnumitKaur0211]

Perfect! Thank you!

[@hammadazaz1229]

superb explaination.

[@hesahesa]

this is the best, thanks!

[@ShahzadKhan-zq9ty]

superb explanation

[@VidyaBhandary]

Thank you !! Very clear ....

[@842Mono]

great explanation! :D

[@user-kq6ms1cj3i]

Excellent video! But how to get around when (i - j) has no inverse when working on finite fields?

[@nawalzaman2268]

hi , that was fantastic, can you also provide a video tutorial of its implementation in C++

[@Denverse]

This is Awesome!

[@mostafaramezani8364]

Perfect! Thanks

[@muhammadishaq6514]

very elegant

[@anotherperson2620]

Good stuff.

[@vryandeleon5672]

Thank you.

[@Abhishek-pb8kt]

perfect!

[@utilizator1701]

The exercise answer: f(x)=10*(x^2+x+1) (mod 11). Then f(0)=10 mod 11. Edit: True it is that f(x)=x^2+3*x+6 (mod 11). Then f(0)=6 mod 11.

[@KeithGalli]

nice video! :)

[@ChinmeshManjrekar]

excellent

[@amerkiller1995]

nice, thanks!

[@dominicloro]

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

[@m4rtinsk]

Hey. At 10:20, I don't understand why f(x) = 0 + 2 + 0 + 2. "which is two!" My question is: Why does the last deltafunction become 2, when I understand it should be 0??? Thanks for the answer.

[@ShimrraJamaane]

He misspoke. He meant to say 0 for the last number.

[@m4rtinsk]

@@ShimrraJamaane thank you for clearing that up.

[@anubhavvats5366]

Thanks for such a excellent explanation. But I am unable to get how you written f(x) = d5(x) + d7(x) + d12(x) + d30(x) at 09:21 is there any proof that we can say so.

[@CryptoClear]

We need to create a function that hits all the points of the shares. The delta-functions are chosen so that, when evaluated, f(5) = 3, f(7) = 2, etc. That this is true is hopefully clear from their definition? The only problem is that these are not mathematical, polynomial functions but "programs". So the next step is to find polynomials that behave exactly like these programs. Once we have done that, we have a polynomial which is of the right degree. And therefore, it has to be *the* polynomial that was used to share the secret.

[@PriyeshuGarg]

woah. hats off

[@lherfel]

thanks

[@abuaws1064]

many many manyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy Thanx

[@leesweets4110]

How do you ensure that the secret shares are integer pairs? Or do you? Obviously a share constitutes an (x,y) coordinate pair on an arbitrary polynomial curve. Im just curious how many decimal values are required and how secrets are expressed for digital storage. Should I assume that the secret is expressed as an integer and so too are the shares? Introducing new members n to the scheme and giving them their own share is done easily enough, but how do you extend the number k of required shareholders to unlock the secret, for a scheme thats already in the field? Since any k-members can agree to bring new shareholders into the mix, why do we call it a (k,n) scheme and not just a k-scheme? The n seems to be meaningless to the mathematics since it is arbitrarily extendible at any time by any k of the members. Does the sharing algorithm extend well to surfaces in 3D space, or do we only ever talk about 2D curves? Im wondering if there is a practical value in this extension.

[@CryptoClear]

Great questions! 1) The video is mostly on the mathematical concept and theory, in practice you would indeed only use integers (for secret, secret parameters and the shares) by using a finite field rater than real numbers (see my other video on the topic of finite fields -- kzbin.info/www/bejne/eaDPhIiundWhbKM). 2) I do not believe it is possible to increase "k" after you have already released k shares. The first k participants will be able to reconstruct the secret. You could lower "k" if the number of shares given out ("p") is strictly less than k, to any number k' between p and k. You'd do this taking the p shares already shared, generating more shares to get a total of k'-1 shares (these you can keep private), and then add the secret at f(0) to these, making a total of k' shares. You then compute the polynomial that goes through these k' points exactly and replace the old polynomial with this new one. 3) I think you are right that it is mostly k that is the true parameter here. Perhaps the name reflects some envisioned use case where both k and n are static. E.g. a country has 5 military leaders, at least 3 of them have to agree to reveal the nuclear launch codes. When using finite fields, there is the technical constraint that "n" must be smaller than the size of your field, but I doubt this would often be a real issue. 4) Interesting idea. There might be some practical value to it but I'm not sure right away what it would be.

[@savimcgee7443]

Oh my God... I get it. I understand!

[@savimcgee7443]

5 videos posted: 1.22k subscribers. Well done.

[@charlesgerard5721]

I understand how it is A 3rd degree polynomial that passes through all 4 points, but how do we know it's the ONLY one?

[@user-ci3cu3kv6f]

By definition. Take for example the straight line 2:03 . You cannot create another straight line that differs from this line, but still goes through the two points. This continues if you increment the degree and the points used.

[@nahiyanalamgir7056]

12:16 You meant x - 12, and not x-13, right?

[@conformist]

The polynomial is x^2 - 8x + 17, and thus the secret is 17. Did I do it right? Not sure how to take the field Z_{11} into account when calculating the polynomial. Edit: Tried doing modulus on all the coefficients, so I end up with p(x) = x^2 - 8x + 6. If I then do a mod 11 after evaluating the polynomial at the point, the results still holds. So the secret is 6; I think I got it this time?

[@CryptoClear]

Yes, perfect! The field Z_{11} only contains numbers 1 .. 10, you can think of all the other numbers as applying mod 11. So in a way both your solutions are correct since 17 mod 11 = 6. (as a nit: "-8" would not be a value in Z_{11}, instead it would be 3 (= -8 mod 11).). That's simplifying finite fields a lot though, you could read Wikipedia for a more thorough description (en.wikipedia.org/wiki/Finite_field). Thank you so much for trying the exercise!

[@aaallami]

hi Chestnutric, what are the values of x in the delta function. could you explain how were you able to plug numbers in the delta equation? Thanks

[@snehakhemani214]

@@CryptoClear i got the equation x^2 - 8x +17 so the secret is 17. Cant understand the mod form ,how 6 is the secret are there two secrets.

[@user-ci3cu3kv6f]

I love you

[@bubblesgrappling736]

I really dont understand how to do this if the secret is a string of natural language?

[@CryptoClear]

Good question. You'd need an agreed mapping from numbers to strings. One (not super efficient) option could be to use the ASCII value of a character, and have a separate secret polynomial for each character. The participants would receive one share per character.

[@bubblesgrappling736]

@@CryptoClear ah yes ok, this would make sense :) Also, I am a bit confused whether the secret secret s would be the gradient of the polynomial, or the point where the polynomial hits the y-axis? I feel that ive seen things thtat indicate both

[@CryptoClear]

S is where it hits the y axis (x=0). The gradient (for a degree 1 polynomial) and other coefficients are kept secret as well, but can be chosen at random and are only used to share the actual secret. E.g in y=3+4x+5x^2, the secret being shared is 3, while coefficients 4 and 5 are also kept hidden in order to keep the polynomial secret.

[@bubblesgrappling736]

@@CryptoClear great! thanks a lot! I have a bit of a dumber question; How/when do you decide which polynomial function to use? I mean, if I have my secret sharing scheme implemented, and I all of the sudden want to share the secret 200. Then I would need a function where f(0) = 200. But how do does my program know how to "spit out" a polynomial that has this property?

[@CryptoClear]

You just pick a polynomial of the form 200 + a*x + b*x^2 + c*x^3 ... And choose random values for a, b, c etc. If x is 0, it becomes 200 + 0 + 0 + 0 ...

[@leckam]

7:07 "5 points" oh shiiiit, f(x) is so long "10 points..." Fuck!

[@CryptoClear]

:) I admit I computed those the lazy way: www.dcode.fr/lagrange-interpolating-polynomial

[@danielepalombi4066]

It's Lagrange, not LaGrange

[@CryptoClear]

Thanks! I updated the video description and corrected it for the next one: kzbin.info/www/bejne/qIizi6KwZcaorpY