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
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"