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"