Secret Sharing Explained: Shamir's Threshold Protocol

[00:00:01][Music] e [Music] hello and welcome to inedia we have learned many things about Cipher systems and network security up to the state today we will see how a secret can be protected without using encryption systems join [Music] us [Music] hi today we will see how to design and carry out a protocol to protect a secret from possible loss theft or damage in particular we will see how to protect a seet key that we have used to encrypt a document or the private key that we use to sign digitally does that mean that if I lose my secret key or if it gets damaged I can recover it or that I can prevent someone from stealing it even if I have it hidden in my house that would be fantastic well not exactly Bob what I mean is that you can take measures to avoid losing your secret keys or prevent someone from stealing them if you keep them somewhere that is not adequately protected for this there are protocols that allow a secret to be recovered from certain pieces of information that have been prepared previously these are known as sharing protocols or secret sharing protocols this doesn't mean sharing or Distributing secrets with other people it has to do with dividing the secret into many pieces in a way that will allow you to recover the secret later that sounds great but I still don't understand it very well don't worry Bob you'll see how easy it is let me show you in the next chapter the original idea for recovering a secret is to divide it into several pieces so that if later on you have some of these pieces not all of them necessarily it is possible to recover the secret that had been hidden let's see if I understand this suppose I have written my secret key on a piece of paper what you saying is that I have to break the paper into several pieces so that I will be able to recover the key just by gluing the pieces of the original paper back together again in that case it doesn't seem like a very bright idea the example you've given doesn't work because the method you suggest is too simple and insecure in fact it isn't a good method because it has several problems for example you won't be able to recover the key if you lose only one piece of paper and if someone gets one of your pieces of paper they will know part of your key in practice a protocol for sharing and distributing Secrets is a cryptographic process that allows you to obtain a series of values or Shadows from a given secret so it is possible to recover the original secret using a previously specified number of those Shadows but impossible if there are fewer Shadows if I've understood correctly you mean Shadows that are derived from the original secret but are not part of the secret does that mean that the Shadows don't contain pieces of the secret information like the pieces of paper that I mentioned earlier that's it the aim is to obtain different values from the secret so that these values don't give clues about the content of the secret I haven't said anything about the size of the Shadows if the Shadows are the same size as the secret the protocol is said to be ideal furthermore there is no need to use all the Shadows that were generated in in order to recover the secret to be more precise if in a secret sharing protocol and shadows are generated and we need K of them to recover the secret the K is considered a threshold value and the protocol is called a k and threshold protocol in this way if less than K Shadows are known that is K minus one or less it is impossible to recover the secret so for example if I use a three five threshold protocol to share share my password I will obtain five Shadows from my secret key and I will be able to recover the complete original key using any three shadows is that correct can I keep one shadow of my secret in my laptop another on a flash drive another at home one more in the office and the last one in a CD of course that way if you lose the CD for example you won't lose the key you would have only lost one of the shadows and you could use any of the three remaining Shadows to recover the secret this way your password is protected against loss damage and theft an attacker won't be able to recover your password if they retrieve in this example two or fewer Shadows Alice you've convinced me about the usefulness of these protocols but how are they used in practice are they complicated it's easy to understand we'll take a look at an example in the next chapter one of the easiest ways to conduct a secret sharing protocol is using pols as a mathematical tool although it's not the only way to do it there are other ways but they are more complicated well I think I can handle polinomial they are very difficult so please explain how they are used in secret sharing first of all remember that a polom can be used to plot a curve through the points that verify this polinomial secondly a polom of a fixed degree can be determined if we know the values that this polom takes on as many points as its degree Value Plus One do you mean that to find the three coefficients of a polinomial of degree 2 for example I just need to know the values of the polinomial in three points that is for three values of X that's the idea remember that two points determine a single line that is a polinomial of degree 1 3 three points determine a single Parable which is a polom of degree 2 and so on so if you know the values of a polinomial for certain points you can determine the polom that passes through these points and whose degree is one less than the number of known points the process of calculating a polom from its points is known as the log range interpolation method sorry Alice but I still can't see how you can use polinomial to hide secrets patience we're on to it AI Shamir one of the most important cryptographers of today came up with the idea of using polynomials for this protocol the idea is to hide a secret inside of a polinomial so that given certain partial information of the polom you can recover the secret that was hidden in it okay but there are two problems the first one is to hide the secret in the polinomial and the second is to recover the polinomial to recover the secret let's see the first one if my secret is for example the number 263 and we use a three five threshold protocol how can we hide it in a polinomial bob you have chosen the value k equal 3 as the threshold so we will use a polom of degree 2 which has three factors PX equal a per X raed to 2 plus b x plus C so the threshold is the same as the number of coefficients in the polom once this has been decided the polinomial independent term will correspond to the secret value that is C is equal to 263 for the other two coefficients two random numbers are chosen for example a equal 167 and b equal 227 so our polom would be PX = 167 per X raed to 2 + 227 per x + 263 now we just have to calculate the polinomial for any five values of X5 Shadows for example to make it simple we can choose for X the values 1 2 3 4 and five although it can be any other set of five numbers that's something I can do if I substitute the value x equal 1 in the polinomial it would be P1 = 167 by 1 + 227 by1 1 + 263 equal 657 and the other values would be 1,385 2,447 3,843 and 5,573 well done you built the five Shadows you needed each Shadow is the pair formed by the value of x and the corresponding value of the polinomial that is your five Shadows are the following pairs of numbers one 657 2 1,385 3 2,447 4 3,843 and 5 5,573 now you can save them in five different places as you can see in this example none of the Shadows look like your secret there is no way that anyone could find out that your secret value is 263 by stealing or finding a pair of the above numbers but you must not forget to destroy the paper where you had written your secret number or delete the file where you had saved it by the way you should also delete all traces of the polinomial so that no one can find it and see your secret number on it this was easy but now comes the second part how can we recover the secret value using only three of the five sh Shadows to recover the secret we must obtain the polinomial and consider its independent term to do this we consider three of the five Shadows for example the 2 2 1,385 the 3 3 2447 and the fifth 5 5,573 and we use the lag range interpolation method to recover the polom let's calculate it we would have K points X1 y1 x k y k and the polom is determined by calculating PX in our example the three points are X2 Y2 X3 Y3 X5 y5 to simplify the calculation the corresponding auxiliary polom QX is calculated for each point the original polom is obtained by calculating PX with QX so the final result is PX equal 1385 per q2x + 2447 per q3x + 5,573 per q5x equal 167 per X raed to 2 + 227 per x + 263 and your secret number is 263 you can do the same calculation with any other three shadows no matter which ones you use you will always get the same polinomial I love it it's fantastic it's clear that with three shadows my secret can be recovered so I'll have to be careful that no one gets three of the Shadows I imagine that secret sharing protocols have other uses you're right although protection was their original motivation nowadays these Protocols are used and applied in other situations for example a secret can be divided and each Shadow can be given to a different person so the secret is recovered only if a certain number of people agree to share their shadows and create the secret this approach is used for Access Control opening safes or military device initialization Alice I only have one question how safe is this protocol has anyone tried to break it the security of the protocol has been demonstrated it is true that there have been attempts to break it but so far there is no known way to violate the protocol provided that the established guidelines are followed and that there implementation has no errors well this is enough for today in future lessons we will see different protocols that allow other interesting actions on the inedia website you will find additional documentation for this lesson like an example of the impossibility to recover a secret with K minus one Shadows goodbye see you [Music] later [Music]