1<!DOCTYPE html>
  2<html lang="en">
  3
  4  <head>
  5    <meta name="description" content="" />
  6    <meta charset="utf-8">
  7    <title> Lagrange Polynomial Interpolation and Shamir secret sharing - arnaucube - blog</title>
  8    <meta name="title" content=" Lagrange Polynomial Interpolation and Shamir secret sharing - arnaucube - blog">
  9    <meta name="description" content="">
 10
 11    <meta property="og:title" content=" Lagrange Polynomial Interpolation and Shamir secret sharing - arnaucube - blog" />
 12    <meta property="og:description" content="" />
 13    <meta property="og:url" content="https://arnaucube.com/blog/shamir-secret-sharing.html" />
 14    <meta property="og:type" content="article" />
 15    <meta property="og:image" content="https://arnaucube.com/blog/" />
 16    <meta name="twitter:title" content=" Lagrange Polynomial Interpolation and Shamir secret sharing - arnaucube - blog">
 17    <meta name="twitter:description" content="">
 18    <meta name="twitter:image" content="https://arnaucube.com/blog/">
 19    <meta name="twitter:card" content="summary_large_image">
 20    <meta name="author" content="arnaucube">
 21
 22    <meta name="viewport" content="width=device-width, initial-scale=1">
 23
 24    <link href="css/bootstrap.min.css" rel="stylesheet">
 25    <link rel="stylesheet" href="css/style.css">
 26
 27    <!-- highlightjs -->
 28    <!-- <link rel="stylesheet" href="js/highlightjs/atom-one-dark.css"> -->
 29    <link rel="stylesheet" href="js/highlightjs/gruvbox-dark.css">
 30    <script src="js/highlightjs/highlight.pack.js"></script>
 31
 32    <!-- katex -->
 33    <link rel="stylesheet" href="js/katex/katex.min.css">
 34  </head>
 35
 36  <body>
 37
 38    <!-- o_gradient_background" -->
 39    <nav id="mainNav" class="navbar navbar-default navbar-fixed-top"
 40                      style="height:50px;font-size:130%;">
 41      <div class="container">
 42        <a href="/blog" style="color:#000;">Blog index</a>
 43        <div style="float:right;">
 44          <a href="/" style="color:#000;display:inline-block;">arnaucube.com</a>
 45          <div class="onoffswitch" style="margin:10px;display:inline-block;" title="change theme">
 46            <input onclick="switchTheme()" type="checkbox" name="onoffswitch" class="onoffswitch-checkbox"
 47              id="themeSwitcher">
 48            <label class="onoffswitch-label" for="themeSwitcher"></label>
 49          </div>
 50        </div>
 51      </div>
 52      <img style="height:5px; width:100%; margin-top:8px;" src="img/gradient-line.jpg" />
 53    </nav>
 54
 55
 56
 57    <div class="container" style="margin-top:40px;max-width:800px;">
 58      <h2>Lagrange Polynomial Interpolation and Shamir secret sharing</h2>
 59
 60<p><em>2021-10-10</em></p>
 61
 62<blockquote>
 63<p>If you read this post, be aware that I’m not a mathematician, I’m just an amateur on math studying in my free time, and this article is just an attempt to try to sort the notes that I took while learning about Lagrange polynomial interpolation and Shamir&rsquo;s secret sharing.</p>
 64</blockquote>
 65
 66<p>Imagine that you have a <em>secret</em> (for example a <em>private key</em> that can decrypt a file), and you want to backup that <em>secret</em>. You can split the <em>secret</em> and give each slice to a different person, so when you need to reconstruct the <em>secret</em> you just need to put together all the parts. But, what happens if one of the parts gets corrupted, or is lost? The secret would not be recoverable.
 67A better solution can be done if we use <em>Shamir Secret Sharing</em>, which allows us to split the <em>secret</em> in <span class="math inline">\(k\)</span> different parts, and set a minimum threshold <span class="math inline">\(n\)</span>, which defines the number of required parts to recover the <em>secret</em>, so just by putting together any <span class="math inline">\(n\)</span> parts we will recover the original secret.</p>
 68
 69<p>This has interesting applications, such as social recovery of keys or distributing a secret and ensuring that cooperation is needed in order to recover it. In the following lines we will overview the concepts behind this scheme.</p>
 70
 71<h3>Lagrange polynomial interpolation</h3>
 72
 73<p>Lagrange interpolation is also used in many schemes that work with polynomials, for example in <a href="https://arnaucube.com/blog/kzg-batch-proof.html">KZG Commitments</a> (an actual implementation <a href="https://github.com/arnaucube/kzg-commitments-study/blob/master/arithmetic.go#L272">can be found here</a>).</p>
 74
 75<p>The main idea behind is the following: for any <span class="math inline">\(n\)</span> distinct points over <span class="math inline">\(\mathbb{R}^2\)</span>, there is a unique polynomial <span class="math inline">\(p(x) \in \mathbb{R[x]}\)</span> of degree <span class="math inline">\(n-1\)</span> which goes through all of them.
 76From the &lsquo;other side&rsquo; point of view, this means that if we have a polynomial of degree <span class="math inline">\(n-1\)</span>, we can take <span class="math inline">\(n\)</span> points (or more) from it, and we will be able to recover the original polynomial from those <span class="math inline">\(n\)</span> points.</p>
 77
 78<p>We can see this starting with a line. If we are given any two points <span class="math inline">\(P_0=(x_0, y_0)\)</span> and <span class="math inline">\(P_1=(x_1, y_1)\)</span> from that line, we are able to recover the original line.</p>
 79
 80<div style="text-align:center;">
 81    <img style="width:300px;margin-bottom:20px;" src="img/posts/shamir-secret-sharing/line.png" />
 82</div>
 83
 84<p>We can map this into the previous idea, seeing that our line is a degree <span class="math inline">\(1\)</span> polynomial, so, if we pick <span class="math inline">\(2\)</span> points from it, we later can recover the original line.</p>
 85
 86<p>Same happens with polynomials of degree <span class="math inline">\(2\)</span>. Let <span class="math inline">\(p(x)\)</span> be a polynomial of degree <span class="math inline">\(2\)</span> defined by <span class="math inline">\(p(x)= x^2 - 5x - 6\)</span>. We can create infinity of polynomials of degree <span class="math inline">\(2\)</span> that go through <span class="math inline">\(2\)</span> points, but with 3 points there is a unique polynomial degree <span class="math inline">\(2\)</span></p>
 87
 88<p>As the degree is <span class="math inline">\(2\)</span>, if we pick <span class="math inline">\(3\)</span> points from the polynomial, we will be able to reconstruct it.
 89<div style="text-align:center;">
 90    <img style="width:300px;margin-bottom:20px;" src="img/posts/shamir-secret-sharing/degree2.png" />
 91</div></p>
 92
 93<p>This is generalized by using <em>Lagrange polynomial interpolation</em>, which defines:</p>
 94
 95<p>For a set of points <span class="math inline">\((x_0, y_0), (x_1, y_1), ..., (x_n, x_n)\)</span>,</p>
 96<p><span class="math display">\[
 97I(x) = \sum_{i=0}^n y_i l_i(x)\newline
 98where \space\space\space l_i(x) = \prod\_{0\leq j \leq n, j\neq i} \frac{x-x_j}{x_i - x_j}
 99\]</span></p>
100<h3>Shamir&rsquo;s secret sharing</h3>
101
102<p>As we&rsquo;ve seen, for a degree <span class="math inline">\(n-1\)</span> polynomial we can pick <span class="math inline">\(n\)</span> or more points and we will be able to reconstruct the original polynomial from it. This is the main idea used in <em>Shamir&rsquo;s secret sharing</em>.</p>
103
104<p>Let <span class="math inline">\(s\)</span> be our secret. We want to generate <span class="math inline">\(k\)</span> pieces and set a threshold <span class="math inline">\(n\)</span> which is the minimum number of pieces that are needed to reconstruct the secret <span class="math inline">\(s\)</span>. We can define a polynomial of degree <span class="math inline">\(n-1\)</span>, and pick <span class="math inline">\(k\)</span> points from that polynomial, so in this way with just putting together <span class="math inline">\(n\)</span> points of <span class="math inline">\(k\)</span> we will be able to reconstruct the original polynomial. And, we can place our secret <span class="math inline">\(s\)</span> in the <em>constant term</em> of the polynomial (the one that has <span class="math inline">\(x^0\)</span>), in this way, when we reconstruct the polynomial using <span class="math inline">\(n\)</span> out of <span class="math inline">\(k\)</span> points, we will be able to recover the secret <span class="math inline">\(s\)</span>.</p>
105
106<p>We can see this with an example with actual numbers (we will use small numbers):
107Imagine that we want to generate <span class="math inline">\(5\)</span> pieces from our secret, and define that just by putting together <span class="math inline">\(3\)</span> of the pieces we can recover the secret, this means setting <span class="math inline">\(n=3\)</span> and <span class="math inline">\(k=5\)</span>. Then we will generate a polynomial of degree <span class="math inline">\(n-1=2\)</span>, by <span class="math inline">\(p(x) = \alpha_0 + \alpha_1 x  + \alpha_2 x^2\)</span>, where <span class="math inline">\(\alpha_0 = s\)</span> (the secret).</p>
108
109<p>We will work over a finite field of size <span class="math inline">\(p\)</span>, where <span class="math inline">\(p\)</span> is a prime number. For our example we will work over <span class="math inline">\(\mathbb{F}_{19}\)</span>, in real world we would work with much more bigger field. You can find an <a href="https://en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing#Example">example without finite fields in Wikipedia</a>.</p>
110
111<p>Let our secret be <span class="math inline">\(s=14\)</span>. We now generate our polynomial of degree <span class="math inline">\(n-1=2\)</span>, where <span class="math inline">\(s\)</span> will be the constant coefficient: <span class="math inline">\(p(x)= s + \alpha_1 x^1 + \alpha_2 x^2\)</span>. We can set <span class="math inline">\(\alpha_1\)</span> and <span class="math inline">\(\alpha_2\)</span> into any random value, as example <span class="math inline">\(\alpha_1=4\)</span> and <span class="math inline">\(\alpha_2=6\)</span>. So we have our polynomial: <span class="math inline">\(p(x) = 14 + 4 x + 6 x^2\)</span>.</p>
112
113<p>Now that we have the polynomial, we can pick <span class="math inline">\(k\)</span> points from it, using incremental indexes for the <span class="math inline">\(x\)</span> coordinate: <span class="math inline">\(P_1=(1, p(1)), P_2=(2, p(2)), \space\ldots\space, P_k=(k, p(k))\)</span>. With the numbers of our example this is (remember, we work over <span class="math inline">\(\mathbb{F}\_{19}\)</span>):</p>
114<p><span class="math display">\[
115p(x) = 14 + 4 x + 6 x^2,\newline
116p(1)=14 + 4 \cdot 1 + 6 \cdot 1^2 = 24 \space (mod \space 19) = 5\newline
117p(2)=14 + 4 \cdot 2 + 6 \cdot 2^2 = 46 \space (mod \space 19) = 8\newline
118p(3)=14 + 4 \cdot 3 + 6 \cdot 3^2 = 80 \space (mod \space 19) = 4\newline
119p(4)=14 + 4 \cdot 4 + 6 \cdot 4^2 = 126 \space (mod \space 19) = 12\newline
120p(5)=14 + 4 \cdot 5 + 6 \cdot 5^2 = 184 \space (mod \space 19) = 13
121\]</span></p><p>So our <span class="math inline">\(k\)</span> points are: <span class="math inline">\((1,5), (2,8), (3,4), (4,12), (5,13)\)</span>. We can distribute these points as our &lsquo;secret parts&rsquo;.
122In order to recover the secret, we need at least <span class="math inline">\(n=3\)</span> points, for example <span class="math inline">\(P_1\)</span>, <span class="math inline">\(P_3\)</span>, <span class="math inline">\(P_5\)</span>, and we compute the <em>Lagrange polynomial interpolation</em> to recover the original polynomial (remember, we work over <span class="math inline">\(\mathbb{F}\_{19}\)</span>):</p>
123<p><span class="math display">\[
124I(x) = \sum_{i=0}^n y_i l_i(x) \space\space
125where \space\space\space l_i(x) = \prod\_{0 \leq j \leq n \\ j\neq i} \frac{x-x_j}{x_i - x_j}
126\]</span></p><p><span class="math display">\[
127l_1(x) = \frac{x-3}{1-3} \cdot \frac{x-5}{1-5} = \frac{x-3}{17} \cdot \frac{x-5}{15}=\frac{x^2+11x+15}{8}\newline
128l_3(x) = \frac{x-1}{3-1} \cdot \frac{x-5}{3-5} = \frac{x-1}{2} \cdot \frac{x-5}{17} =\frac{x^2+13x+5}{15}\newline
129l_5(x) = \frac{x-1}{5-1} \cdot \frac{x-3}{5-3} = \frac{x-1}{4} \cdot \frac{x-3}{2} = \frac{x^2 + 15x + 3}{8}\newline
130\]</span></p><p><span class="math display">\[
131I(x) = y_2 \cdot l_2(x) + y_4 \cdot l_4(x) + y_5 \cdot l_5(x)\newline
132= 5 \cdot (\frac{x^2+11x+15}{8}) + 4 \cdot (\frac{x^2+13x+5}{15}) + 13 \cdot (\frac{x^2 +15x + 3}{8})\newline
133= \frac{5x^2+17x+18}{8} + \frac{4x^2+14x+1}{15} + \frac{13x^2+5x+1}{8}\newline
134= 3x^2+14x+7 + 18x^2+6x+14 + 4x^2+3x+12\newline
135= 6x^2 + 4x + 14
136\]</span></p><p>We can now take the <em>constant coefficient</em>, or just evaluate the obtained polynomial at 0, <span class="math inline">\(p(0) = 6 \cdot 0^2 + 4 \cdot 0 + 14 = 14\)</span>, and we obtain our original secret <span class="math inline">\(s=14\)</span>.</p>
137
138<h3>Conclusions</h3>
139
140<p>As an example of an use case of <em>Shamir Secret Sharing</em> we can think of social recovery of keys, there is an useful implementation of this scheme is used in the <a href="https://bs.parity.io/">banana split by Parity</a>. Also, here it is an implementation of the scheme in <code>Go</code>&amp;<code>Rust</code> done a couple of years ago: <a href="https://github.com/arnaucube/shamirsecretsharing">https://github.com/arnaucube/shamirsecretsharing</a>.</p>
141
142<p><em>Lagrange Interpolation</em> in its own way, is a very useful tool in many schemes, it is also used in KZG Commitments, in zkSNARKs, zkSTARKs, PLONK, etc. In most of the schemes where polynomials are involved it becomes a very useful tool.</p>
143
144    </div>
145
146    <footer style="text-align:center; margin-top:100px;margin-bottom:50px;">
147      <div class="container">
148        <div class="row">
149          <ul class="list-inline">
150            <li><a href="https://twitter.com/arnaucube"
151                   style="color:gray;text-decoration:none;"
152                   target="_blank">twitter.com/arnaucube</a>
153            </li>
154            <li><a href="https://github.com/arnaucube"
155                   style="color:gray;text-decoration:none;"
156                   target="_blank">github.com/arnaucube</a>
157            </li>
158          </ul>
159        </div>
160        <div class="row" style="display:inline-block;">
161          Blog made with <a href="http://github.com/arnaucube/blogo/"
162                            target="_blank" style="color: gray;text-decoration:none;">Blogo</a>
163        </div>
164      </div>
165    </footer>
166
167    <script>
168    </script>
169    <script src="js/external-links.js"></script>
170    <script>hljs.initHighlightingOnLoad();</script>
171    <script defer src="js/katex/katex.min.js"></script>
172    <script defer src="js/katex/auto-render.min.js"></script>
173    <script>
174      document.addEventListener("DOMContentLoaded", function() {
175        renderMathInElement(document.body, {
176          displayMode: false,
177          // customised options
178          // • auto-render specific keys, e.g.:
179          delimiters: [
180            {left: '$$', right: '$$', display: true},
181            {left: '$', right: '$', display: false},
182            {left: "\\[", right: "\\]", display: true},
183            {left: "\\(", right: "\\)", display: false},
184          ],
185          // • rendering keys, e.g.:
186          throwOnError : true
187        });
188      });
189
190      ///
191      let theme = localStorage.getItem("theme");
192      if ((theme === "light-theme")||(theme==null)) {
193          theme = "light-theme";
194          document.getElementById("themeSwitcher").checked = false;
195      } else if (theme === "dark-theme") {
196          theme = "dark-theme";
197          document.getElementById("themeSwitcher").checked = true;
198      }
199      document.body.className = theme;
200      localStorage.setItem("theme", theme);
201
202      function switchTheme() {
203        theme = localStorage.getItem("theme");
204        if (theme === "light-theme") {
205          theme = "dark-theme";
206          document.getElementById("themeSwitcher").checked = true;
207        } else {
208          theme = "light-theme";
209          document.getElementById("themeSwitcher").checked = false;
210        }
211        document.body.className = theme;
212        localStorage.setItem("theme", theme);
213
214        console.log(theme);
215      }
216    </script>
217  <script>
218    function tagLinks(tagName) {
219      var tags = document.getElementsByTagName(tagName);
220      for (var i=0, hElem; hElem =  tags[i]; i++) {
221        if (hElem.parentNode.className=="row postThumb") {
222          continue;
223        }
224        hElem.id = hElem.innerHTML.toLowerCase().replace(" ", "-");
225        hElem.innerHTML = "<a style='text-decoration:none;color:black;' href='#"+hElem.id+"'>"+hElem.innerHTML+"</a>";
226      }
227    }
228    tagLinks("h2");
229    tagLinks("h3");
230    tagLinks("h4");
231    tagLinks("h5");
232    </script>
233    <script src="js/mermaid.min.js"></script>
234
235
236  </body>
237</html>
238