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