Loading
Notes
Study Reminders
Support
Text Version

Set your study reminders

We will email you at these times to remind you to study.
  • Monday

    -

    7am

    +

    Tuesday

    -

    7am

    +

    Wednesday

    -

    7am

    +

    Thursday

    -

    7am

    +

    Friday

    -

    7am

    +

    Saturday

    -

    7am

    +

    Sunday

    -

    7am

    +

Foundations of Cryptography Dr. Ashish Choudhury Department of Computer Science Indian Institute of Science – Bengaluru Lecture - 56 Secret Sharing (Refer Slide Time: 00:29) Hello everyone. Welcome to this lecture. So in this lecture we will discuss about interactive protocols. Namely our focus till now was on solving the problem of secure communication where we had two entities a sender and a receiver and we extensively discussed how to design algorithms to solve the problem of secure communication. But now what we are going to discuss is a scenario, a well-known problem, where we have multiple entities. And our goal is to design cryptographic protocol which requires interaction among the entities. So, specifically the roadmap for this lecture is as follows. We will introduce the problem of secret sharing. We will see additive secret sharing, replicated secret sharing and then we will see the classic construction of secret sharing scheme due to Adi Shamir. (Refer Slide Time: 01:17)So let us see the motivation of secret sharing. So imagine we have a banking application, say where the locker in the bank is accessible only by the managers in the following way. The password for the locker is shared among the three managers and it shared in such a way that if only two of the managers go together and enter their respective passwords, the locker can be accessed. But if only a single manager tries to enter the password and access the locker, the access is not possible. So, for instance if the second manager goes and tries to open the locker, it should not able to do that. In the same way, if the third manager goes alone, it should fail. But if we take any set of two or more number of managers and they go and enter their respective passwords, they should be able to access the locker. So that is what we require here. (Refer Slide Time: 02:14)In the same way, consider another real-world scenario. This is a real-world scenario, which really happened during 90s. So this is regarding how Russia’s Nuclear Weapons was accessible by the top leaders of the countries. So it is believed that the password to launch the Russia’s nuclear weapon, it was shared between top three entities of the country namely the president, prime minister and defense minister in such a way that the weapon could be accessed or launched only if at least 2 of the 3 entities come together and enter their passwords, whereas if only a single entity tries to launch or access the weapon, the access will be denied. (Refer Slide Time: 02:55) So both these applications can be abstracted by the following problem, which we call as (Secret Sharing. And this problem was independently formulated by Shamir in 1979 and Blakley in 1979. So what we are given here is, we are given the following setting. We have a set of parties 1, ⋯ and they are connected by pair-wise private and authentic channel. What it means is, if any information wants to send it to , we assume that it has a dedicated channel with which it is connected to . And anything sends over that channel to , it will be received correctly and securely by . If you are wondering how exactly that such channels are available in real-world, well, we can use any of the well-known secure communication protocol that we have extensively discussed till now, to ensure that such channels are available between every pair of parties. Now apart from these parties, we have a designated party among those parties and everyone will know the identity of that party and it is called as dealer. And dealer has some private input, a secret from a bigger space , which is a set of all possible secrets. Now the goal of this dealer is to distribute its secret among the parties by coming up or computing a share for each of these parties and distributing the shares. So first shareholder gets a share 1 , second party should get the second share and the party should get the share . And these shares are distributed over the pair-wise channel with which the dealer is connected to the individual shareholders. Now we require the following properties from these distributions of shares. We require that it should be impossible for any set of or less number of shareholders to exchange their shares and reconstruct back the secret . And depending upon whether the set of shareholders who are trying to reconstruct back the secret, whether they are computationally bounded or they are computationally unbounded, we achieve either perfect secrecy or computational secrecy. So that is the first requirement from this distribution of shares. On the other hand, if any set of or more shareholders pull together their shares then it should possible to reconstruct back the secret . So the parameter here is acting as a threshold for you. That means we require a sharing mechanism such that if any set of or less number of shareholders come together, they should fail to access or they should fail to reconstruct the secret. The shares should be completely independent from the underlying secret. On the other hand, if any set of or more number of shareholders come together, the secret should be reconstructed, it should be possible to reconstruct back the secret. (Refer Slide Time: 05:39) So let us see a very simple construction of (additive secret sharing scheme. So basically here my threshold . That means I require a sharing mechanism where all the shareholders should come together to reconstruct back the secret. But if any single shareholder is missing then it should not be possible to reconstruct back the secret. And why it is called additive secret sharing, it would be clear to you very soon. So here my secret space ℓ . The sharing algorithm is as follows. So imagine dealer has a secret . To share it, it picks shares randomly from the set . That means the first share 1 is a random ℓ-bit string, the second share is a random ℓ-bit string and in the same way the share is also a random ℓ-bit string. Now once the first shares are fixed by the dealer, the last share is set as = 1⨁ ⋯ ⨁. And once the shares are computed, the dealers sends the respective shares to the respective shareholders. Namely the share is given to the party over the dedicated secure and authentic channel between the dealer and the party . So the correctness property here is trivial for this secret sharing, namely if all the shareholders come together and exchange their shares with each other then indeed they can perform the xor of all the shares and they will uniquely get back the underlying secret which was shared by the dealer. W next formally prove the privacy property here. So for privacy our goal is to show that if among these shareholders, any shareholders come together and pull their shares, they should not learn anything about underlying secret . So we divide the proof into two cases. Consider the case when the set of shareholders who are corrupted and who are trying to reconstruct the secret are the first shareholders. It turns out that if the first shareholders are corrupt, then from their shares they learn absolutely nothing about underlying secret . Because if you see the sharing algorithm, the first shares they are picked independently of the actual secret of the dealer. So that means if the adversary controls the first shareholders and access their shares, the adversary learns absolutely nothing about the dealer secret. That is the case one. On the other hand, consider the case when the set of shareholders definitely include the nth shareholder, where the the share is a function of a secret and a remaining shares. So the second case is when coalition of shareholders excludes some party , where is definitely different from the party . So for simplicity you can imagine that my = 1, that means the adversary is corrupting the last shareholders here. It turns out that the missing share which the set of shareholders are missing, which in this example is the share 1, that is independent of the secret . Because that was picked randomly by the dealer and that ensures that even though the adversary learns , it is the share is also independent of the secret . Because for instance, if we are considering the case where 1 is missing in the coalition, then from the view part of the attacker, attacker knows that the value = 1⨁ ⋯ ⨁, where and 1are not known to the adversary. And where 1 is independently and randomly picked by the dealer. So you can imagine that this is nothing but a onetime pad encryption of the message with a key, where the key is nothing but the xor of the shares 2, ⋯ , which are known to the adversary and the random value 1, which is not known to the attacker.That means even though adversary is seeing , it cannot figure out whether is actually a share corresponding to the secret or corresponding to a secret . Because it does not know the value of the missing share 1, which was randomly picked and independently picked of the actual secret of the dealer. That ensures that even if the adversary controls the last shareholder it will learn absolutely nothing about the underlying secret . And that is why the secret sharing satisfies the requirements of an (secret sharing scheme. (Refer Slide Time: 11:01) So it turns out that the additive secret sharing that we have discussed, it works only if my threshold is . But in general I might be interested to design a secret sharing where my threshold may not be , my threshold could be strictly less than . So now let us see a solution, a naive solution of coming up with a secret sharing scheme for any threshold . So the idea here is we take every proper subset of the set of the parties, say , where the size of is and run a dedicated independent instance of additive secret sharing among the parties in as the shareholders, with the threshold being . And the idea here is that if we do this for every subset of size , then when it comes to the actual coalition of shareholders who might try to learn about the secret, that coalition of shareholders will miss at least one share to reconstruct back the actual shared secret. So what I am trying to say is best demonstrated by this example. So imagine my and I want to design a scheme where my threshold . That means any subset of three shareholders should be able to reconstruct back the secret, but any set of two shareholders, if they try to pull their shares they should fail to reconstruct back the secret. So the idea here is that the dealer divides this set of four parties into different subsets 1,2, 3, 4 of size three parties. Now in the first subset 1 = {1, 2,3}, dealer runs an instance of additive secret sharing scheme with the threshold being t = 2. Namely dealer picks random shares 11, 12, 13, such that 11⨁12⨁13, and then the shares are given to the respective shareholder 1,2,3. Similarly, the dealer runs an independent instance of (3, 3) additive sharing for the subset 2, 3 and 4 . Now the overall share for 1 will be all the shares which it receives in various instances of the (3, 3) additive sharing, depending upon the various subsets in which it is present. Namely its share will be 11, 21 and 31. Now it is easy to see that irrespective of which two parties get corrupt, because my threshold in all the instances of additive sharing, those two shareholders learn absolutely no information about the secret s. So for instance if 1 and 2 gets corrupt, if they are under the control of the adversary then based on their shares that they learn, due to their presence in the subset 1, the parties 1,2 fail to learn the secret , because they will be missing the share 13. In the same way with respect to the subset 2 , these two parties will be missing the share 23 and that is why the secret will not be known to them and so on. So it does not matter which subset of parties get corrupt, based on their shares they fail to learn the actual secret . So now you might be wondering that we now have a secret sharing scheme for any threshold with respect to the value of . But it turns out that this scheme is inefficient because the number of subsets of size is ( 1), which becomes an exponential quantity if is approximately . That means dealers basically has to deal with exponential number of values here and same is the case for every shareholder. So this is an inefficient solution. (Refer Slide Time: 15:53)And let us know discuss a very clever solution for (Secret-Sharing due to Adi Shamir. And this is one of the simplest cryptographic constructions that you can think of. This is my personal favorite. And this is based on simple arithmetic which you might have learned during your high school. So the idea here is, if you want to share a secret , then to share it you pick a random polynomial of degree , such that the constant term of the polynomial is the secret which you want to share. And let the shares be the distinct points or values lying on that polynomial. To demonstrate my point, imagine my threshold and I have a secret and I am the dealer. What I can do is, to share the secret , since my threshold , I pick a random straight line, it could be any straight line in the plane with the only restriction been that its constant term should be the secret which I want to share. And what I now do is, I compute the value of the straight line at some fixed publicly known distinct values, say at 1 , at 2 and at 3 . And these are the shares for the first party, second party and third party respectively. It will be publicly known to everyone that the first party is obtaining the value of straight line the dealer has picked at 1 and so on. So these values, they are publicly known and everyone will know that is associated with the party . Now let us try to prove that why intuitively it satisfies the requirements of (secret sharing. So it is easy to see that if shareholders come together then they can uniquely reconstruct back the degree polynomial which dealer has picked. Because distinct values on an unknown degree polynomial suffice to uniquely reconstruct back that polynomial. So for example if and say the first two shareholders come up with their shares 1 and 2 , then they can uniquely find the straight line passing through the points (1, 1) and (2, 2) by fitting a straight line equation. Once they obtain the straight line, they can take the constant term of the straight line to be the recovered secret. On the other hand, the second fact that we can use for polynomials of degree is that, if you take any shareholders who are the bad guys and they are trying to reconstruct back the dealer’s secret, they will fail to do that. Because distinct values does not suffice to uniquely recover back the unknown degree polynomial which was picked by the dealer. More specifically, in this example since , say the first shareholder is corrupt. Then from its viewpoint there could be infinite number of straight lines possible in the plane passing through the point (1, 1) and hence infinite number of possible secrets. That means just based on shares, adversary will completely fail to uniquely reconstruct back the dealer’s original polynomial and hence the dealer’s original secret . That is the intuitive idea. It turns out that we have to perform all the above computations over some finite field to achieve security and to avoid working over an infinite domain. (Refer Slide Time: 20:01) So let us try to first understand some basic facts about polynomials over a finite field. So imagine I am given a finite field (. A degree polynomial over is of the form 0 + 1 ∙ ∙ , where 0, … , ∈ . A value is called a root of (), if () =0I stress here that all the operations here are the + and ∙ operations over the field. Now another wellknown fact from abstract algebra which we can use here is the following. If you are given a degree polynomial over a field, then it can have at most t roots. For example, if , then a straight over a field meets the y-axis at atmost one point. And this is true for any t degree polynomial over a field. And based on this result, we can state that two distinct -degree polynomials (), () over can have at most common values. So for instance if you have 2 distinct straight lines they can intersect at atmost one point. They cannot intersect at 2 points because if they intersect at two common points then the 2 straight lines are basically the same straight line and in general, this generalizes for any value of . Again I am not proving this theorem. These are some well-known results from abstract algebra. And the final result which I am going to use for giving the description of Shamir’s sharing is the Lagrange interpolation formula. So what this theorem basically says is if you are given t + 1 pairs of values (1, 1), …, (, ) from the field, where 1, … , are distinct. Then there exists a unique -degree polynomial over , such that ) = , for 1 ≤ To see how exactly we can compute this polynomial , let me define a sequence of polynomials, where the polynomial ((−1)(−2)⋯(−−1)(−1)⋯(−+1) (−1)(−2)⋯(−−1)(−1)⋯(−1) , which has degree . And the way I have defined this polynomial (it follows that () = 1, while (1) = (2) = ⋯ () = () = ⋯ () = 0. That means these (polynomials are such that they survive at =, whereas they vanish at all other values. Now my unknown polynomial passing through the t + 1 given pairs of (xi, yi) values. And I can represent that unknown polynomial 1(1 + ⋯ + (. (Refer Slide Time: 24:43)And it is easy to see that indeed 1) = 1 , because for 1, my 1(polynomial will survive and give the value 1 and 1 multiplied by 1 will be 1, whereas all the other (polynomials will vanish off. In the same way for 2, all my delta polynomials will vanish except the 2(polynomial, which will give the value 1 and 1 multiplied by 2 will give me 2, which satisfies my condition. So that is the unique degree polynomial , which you can find out passing through the given points (1, 1), …, (, ), where 1, … , are distinct. Now you might be wondering that why 1, … , are distinct have to be distinct? They have to be distinct to ensure that each of the (polynomials have a denominator which is non-zero. And if denominator is non-zero then basically this numerator divided by denominator should be interpreted as if this numerator is multiplied by the multiplicative inverse of my denominator, because I am doing the division here. And this division should be interpreted as multiplying the numerator with the multiplicative inverse of the denominator. And the multiplicative inverse of the denominator will exist only if my denominator is non-zero. (Refer Slide Time: 26:08)So now let us go to the description of Shamir’s Secret Sharing. As part of public setup, we will be given some finite field where the size of the field will be at least , the number of shareholders. And associated with the shareholders will be publicly known non-zero distinct values, namely 1, … , , which are the values from the finite field. The sharing algorithm of Shamir secret sharing is as follows. If the dealer has a secret value , which he wants to share then it picks a random polynomial over the field by choosing random elements as the coefficients from the field, such that the constant term of the polynomial is the secret which dealer wants to share. And now the shareholder, namely the party , gets the share , where is nothing but the value of this polynomial picked by the dealer at . The correctness of this secret sharing is trivial. That means, imagine out of these shareholders, any subset of shareholders come together by exchanging their shares, then they can uniquely interpolate back the degree polynomial using the Lagrange’s interpolation formula that we have discussed earlier. And to prove the privacy we are going to prove that if we take any set of shareholders among these shareholders, then their shares are independent of the underlying share secret , because intuitively this comes from the fact that the coefficients of polynomial which are picked by dealer for sharing the secret, are chosen uniformly at random from the underlying field. (Refer Slide Time: 27:55)So let us make it more rigorous. So let me define a set ℱto denote the set of all -degree polynomials selected from the finite field whose constant term is the secret . So it turns out that the number of such polynomial of degree whose constant term is the secret is nothing, but |. This is because in every such polynomial, apart from the constant term which is , there are other coefficients 1, ⋯, picked from the field and for each of these coefficients, there are |candidates. Hence |ℱ| = |. For simplicity and without loss of geniality, assume that first shareholders are corrupt, that means they have seen the shares 1, … , . And they know that these shares are nothing but the value of some unknown degree polynomial , evaluated at 1, … , . We will show that the probability distribution of these shares is independent of the secret picked by the dealer. For this, we first note that given any arbitrary shares 1, … , , there exists a unique polynomial ℱ, with = ), for . This follows from the fact that the distinct points (0, ), (1 , 1 ), …, (, ) can lie only on a single -degree polynomial. Now based on all these things, I claim that the shares 1, … , are independent of the actual secret shared by the dealer. And to prove this claim, let us consider a pair of arbitrary secrets (′) from , such that . We will show that from the view point of the adversary, 1, … , could be the shares of as well as with equal probability. Let (be unique polynomial from the set ℱwhich would have produced the shares 1, … , for the secret . And similarly, let ′ (be the unique polynomials from the set ℱ′, , which would have produced the shares 1, … , for the secret . Now the probability that given adversary has seen the shares 1, … , , dealer’s secret is is the same as dealer has used the polynomial (for sharing. And this event occurs with probability 1/|, as dealer’s polynomial is randomly picked over , where all the coefficients except the constant term are randomly selected from . Using exactly the same argument, we conclude that the probability that given adversary has seen the shares 1, … , , dealer’s secret is is the same as dealer has used the polynomial ′ (for sharing. And this event occurs with probability 1/|. That proves that the probability distribution of 1, … , is independent of the underlying secret and hence on seeing these shares, adversary will be clueless whether dealer has shared the secret or secret . So that brings me to the end of this lecture. Just to summarize. In this lecture we introduced the problem of (secret sharing and we saw three constructions. We saw the construction of additive secret sharing where the threshold is . And then using this (secret sharing