2020-02-23-sharing-a-secret.md (5068B) - raw

1 <!-- title: Sharing a secret --> 2 <!-- slug: sharing-a-secret --> 3 <!-- categories: Cryptography --> 4 <!-- date: 2020-02-23T00:00:00Z --> 5 <!-- extrafooter: <script id="MathJax-script" async src="/js/mathjax-3.1.0/tex-chtml.js"></script> --> 6 7 Making a backup of a secret can be tricky. For instance: I have a lot of 8 passwords stored in an encrypted file, which I can edit through my password 9 manager. The data in that file is both very sensitive and crucial. I currently 10 have some offline backups (which are updated every once in a while) in different 11 locations and one online backup in case I lose access to my passwords and I am 12 not able to go to one of the locations where other backups are kept. 13 14 The problem with having an online backup is that such sensitive data must be 15 kept away from untrusted third parties and, so far, there's no third party I 16 would trust with all those passwords. My solution is to distribute the trust. 17 The encrypted file is encrypted again multiple times with very long random 18 passwords. Those passwords are distributed across different services, and the 19 file in another one, so no one service has access to the encrypted file. 20 21 This seems like a reasonably secure system (considering the diversity of parties 22 that should agree to attack me/get hacked). However, a couple of days ago, I was 23 introduced to a much simpler and convenient method to "distribute" a secret: 24 [Shamir's Secret Sharing][sss]. 25 26 ## Shamir's Secret Sharing 27 28 Shamir's Secret Sharing was created by [Adi Shamir][as], a cryptographer who is 29 also the co-inventor of the—probably more widely known—[RSA algorithm][rsa] 30 (yes, that S stands for Shamir!). Here, I'll try to briefly explain how it 31 works. 32 33 Given a secret \\(S\\) (coded as a number), we want to distribute it among 34 \\(n\\) parties (giving each party a "share" of the secret) in such a way that 35 only \\(k \\leq n\\) shares are needed to retrieve the secret, but that 36 \\(k-1\\) shares don't grant any kind of knowledge on \\(S\\). 37 38 Shamir's method is based on the fact that given \\(n + 1\\) pairs \\((x_i, 39 y_i)\\) such that \\(i \\neq j \\implies x_i \\neq x_j\\), then there exists a 40 unique polynomial \\(p\\) of degree \\(n\\) or less that satisfies that 41 \\(p(x_i) = y_i\\), \\(\\forall i \\in \\{1, \\dots, n\\}\\) (and we have an 42 efficient method to find \\(p\\) given \\(n\\) points). 43 44 Let's put it into practice. Given a secret \\(S\\), to be shared with \\(n\\) 45 parties in a way that any \\(k\\) parties can retrieve it, we'll build the 46 following polynomial: 47 48 \\[p(x) = S + a_1 x + a_2 x^2 + ... + a_{k-1} x^{k-1},\\] 49 50 where \\(a_i\\) are random numbers, \\(\\forall i \\in \\{1, \\dots, k-1\\}\\). 51 Now we'll evaluate our polynomial on \\(n\\) different points (and different 52 from 0) to obtain \\(n\\) pairs of the form \\((x_i, p(x_i))\\). This will be 53 the shares of the secret. Each party will get one share. We know that \\(k\\) 54 shares define a unique polynomial \\(p\\) of degree \\(k-1\\), (if we find it, 55 we'll find \\(S\\)). On the other hand, there are an infinite amount of 56 polynomials of degree \\(k-1\\) that interpolate \\(k-1\\) points, so the secret 57 cannot be easily obtained by gaining access to \\(k-1\\) shares[^integers]. 58 59 [^integers]: This is not completely true when working with positive integers, 60 but it can be solved by working with finite fields. 61 62 If we want to recover the secret from \\(k\\) shares, we can interpolate the 63 \\(k\\) points \\((x_i, p(x_i))\\) using [Lagrange's form for the interpolation 64 polynomial][int][^proof]: 65 66 [^proof]: Let's quickly prove that the \\(p\\) defined in Lagrange's form 67 (\\(\\bar{p}\\) from now on) is the same as the previously defined \\(p\\). 68 \\(\\bar{p}\\) is clearly a polynomial of degree (at most) \\(k-1\\), since it 69 is the sum of polynomials of degree \\(k-1\\), so we only need to prove that 70 it interpolates the points given (we'll asume that the fact that there is only 71 one polynomial of degree at most \\(k-1\\) that interpolates \\(k\\) points is 72 true). That is easy to prove since \\(i \\neq j \\implies l_i(x_j) = 0\\) and 73 \\(l_i(x_i) = 1\\), therefore having \\(\\bar{p}(x_i) = p(x_i) l_i(x_i) = 74 p(x_i)\\). 75 76 \\[p(x) = \\sum_{i=1}^{k} p(x_i) l_i(x),\\] 77 78 where 79 80 \\[l_i(x) = \\prod_{\\begin{smallmatrix}1\\leq m\\leq k\\ m\\neq 81 i\\end{smallmatrix}} \\frac{x-x_m}{x_i-x_m}.\\] 82 83 Now, evaluating on \\(x = 0\\) we'll find the secret (because \\(p(0) = S\\)). 84 85 ## Final notes 86 87 Now we have a method to share our secret between multiple parties and being able 88 to retrieve it with only some of them. This method is not too hard to code 89 yourself, however, there are implementations online if you would rather not do 90 that (make sure you are running trusted code!). 91 92 93 [sss]: <https://en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing> "Shamir's Secret Sharing — Wikipedia" 94 [as]: <https://en.wikipedia.org/wiki/Adi_Shamir> "Adi Shamir — Wikipedia" 95 [rsa]: <https://en.wikipedia.org/wiki/RSA_(cryptosystem)> "RSA — Wikipedia" 96 [int]: <https://en.wikipedia.org/wiki/Lagrange_polynomial> "Lagrange polynomial — Wikipedia"