arnaucube
arnaucube/arnaucube.comPublic Self-hosted repository
arnaucube.com/blog/shamir-secret-sharing.html
blog/shamir-secret-sharing.htmlRaw
  1<!DOCTYPE html>
  2<html lang="en">
  3
  4  <head>
  5    <meta name="description" content="Overview of Langrange Polynomial interpolation and Shamir's secret sharing." />
  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="Overview of Langrange Polynomial interpolation and Shamir's secret sharing.">
 10
 11    <meta property="og:title" content=" Lagrange Polynomial Interpolation and Shamir secret sharing - arnaucube - blog" />
 12    <meta property="og:description" content="Overview of Langrange Polynomial interpolation and Shamir's secret sharing." />
 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="Overview of Langrange Polynomial interpolation and Shamir's secret sharing.">
 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    <link rel="icon" type="image/png" href="img/logoArnauCubeFavicon.png">
 23
 24    <meta name="viewport" content="width=device-width, initial-scale=1">
 25
 26    <link href="css/bootstrap.min.css" rel="stylesheet">
 27    <link rel="stylesheet" href="css/style.css">
 28
 29    <!-- highlightjs -->
 30    <!-- <link rel="stylesheet" href="js/highlightjs/atom-one-dark.css"> -->
 31    <link rel="stylesheet" href="js/highlightjs/atom-one-light.css">
 32    <!-- <link rel="stylesheet" href="js/highlightjs/gruvbox-dark.css"> -->
 33    <script src="js/highlightjs/highlight.pack.js"></script>
 34
 35    <!-- katex -->
 36    <link rel="stylesheet" href="js/katex/katex.min.css">
 37  <link rel="alternate" type="application/rss+xml" title="arnaucube - blog RSS" href="https://arnaucube.com/blog/rss.xml">
 38</head>
 39
 40  <body>
 41
 42    <!-- o_gradient_background" -->
 43    <nav id="mainNav" class="navbar navbar-default navbar-fixed-top"
 44                      style="height:50px;font-size:100%;">
 45      <div class="container">
 46        <div style="float:left;">
 47        <a href="/blog" style="color:#000;display:inline-block;">blog</a>
 48        <span style="margin-right:20px; margin-left:20px;">|</span>
 49        <a href="/blog/notes.html" style="font-size:90%;color:#000;display:inline-block;">notes</a>
 50        </div>
 51        <div style="float:right;">
 52          <a href="/" style="color:#000;display:inline-block;margin-right:10px;">arnaucube.com</a>
 53          <a href="/blog/rss.xml" target="_blank"
 54            type="application/rss+xml" title="subscribe via RSS" aria-label="subscribe via RSS">
 55              <img width="12px;" src="img/rss.png" />
 56          </a>
 57          <div class="onoffswitch" style="margin-left:0px;display:inline-block;" title="change theme">
 58            <input onclick="switchTheme()" type="checkbox" name="onoffswitch" class="onoffswitch-checkbox"
 59              id="themeSwitcher">
 60            <label class="onoffswitch-label" for="themeSwitcher"></label>
 61          </div>
 62        </div>
 63      </div>
 64      <!-- <img style="height:5px; width:100%; margin-top:8px;" src="img/gradient-line.jpg" /> -->
 65    </nav>
 66
 67
 68
 69    <div class="container" style="margin-top:0px;max-width:800px;">
 70      <h2>Lagrange Polynomial Interpolation and Shamir secret sharing</h2>
 71
 72<p><em>2021-10-10</em></p>
 73
 74<blockquote>
 75<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>
 76</blockquote>
 77
 78<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.
 79A 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>
 80
 81<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>
 82
 83<h3>Lagrange polynomial interpolation</h3>
 84
 85<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>
 86
 87<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.
 88From 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>
 89
 90<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>
 91
 92<div style="text-align:center;">
 93    <img style="width:300px;margin-bottom:20px;" src="img/posts/shamir-secret-sharing/line.png" />
 94</div>
 95
 96<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>
 97
 98<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>
 99
100<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.
101<div style="text-align:center;">
102    <img style="width:300px;margin-bottom:20px;" src="img/posts/shamir-secret-sharing/degree2.png" />
103</div></p>
104
105<p>This is generalized by using <em>Lagrange polynomial interpolation</em>, which defines:</p>
106
107<p>For a set of points <span class="math inline">\((x_0, y_0), (x_1, y_1), ..., (x_n, x_n)\)</span>,</p>
108<p><span class="math display">\[
109I(x) = \sum_{i=0}^n y_i l_i(x)\newline
110where \space\space\space l_i(x) = \prod\_{0\leq j \leq n, j\neq i} \frac{x-x_j}{x_i - x_j}
111\]</span></p>
112<h3>Shamir&rsquo;s secret sharing</h3>
113
114<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>
115
116<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>
117
118<p>We can see this with an example with actual numbers (we will use small numbers):
119Imagine 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>
120
121<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>
122
123<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>
124
125<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>
126<p><span class="math display">\[
127p(x) = 14 + 4 x + 6 x^2,\newline
128p(1)=14 + 4 \cdot 1 + 6 \cdot 1^2 = 24 \space (mod \space 19) = 5\newline
129p(2)=14 + 4 \cdot 2 + 6 \cdot 2^2 = 46 \space (mod \space 19) = 8\newline
130p(3)=14 + 4 \cdot 3 + 6 \cdot 3^2 = 80 \space (mod \space 19) = 4\newline
131p(4)=14 + 4 \cdot 4 + 6 \cdot 4^2 = 126 \space (mod \space 19) = 12\newline
132p(5)=14 + 4 \cdot 5 + 6 \cdot 5^2 = 184 \space (mod \space 19) = 13
133\]</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;.
134In 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>
135<p><span class="math display">\[
136I(x) = \sum_{i=0}^n y_i l_i(x) \space\space
137where \space\space\space l_i(x) = \prod\_{0 \leq j \leq n \\ j\neq i} \frac{x-x_j}{x_i - x_j}
138\]</span></p><p><span class="math display">\[
139l_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
140l_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
141l_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
142\]</span></p><p><span class="math display">\[
143I(x) = y_2 \cdot l_2(x) + y_4 \cdot l_4(x) + y_5 \cdot l_5(x)\newline
144= 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
145= \frac{5x^2+17x+18}{8} + \frac{4x^2+14x+1}{15} + \frac{13x^2+5x+1}{8}\newline
146= 3x^2+14x+7 + 18x^2+6x+14 + 4x^2+3x+12\newline
147= 6x^2 + 4x + 14
148\]</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>
149
150<h3>Conclusions</h3>
151
152<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>
153
154<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>
155
156    </div>
157
158    <footer style="text-align:center; margin-top:100px;margin-bottom:50px;">
159      <div class="container">
160        <br>
161        <a href="/blog">Go to main</a>
162        <br><br>
163        <div class="row">
164          <ul class="list-inline">
165            <li><a href="https://twitter.com/arnaucube"
166                   style="color:gray;text-decoration:none;"
167                   target="_blank">twitter.com/arnaucube</a>
168            </li>
169            <li><a href="https://github.com/arnaucube"
170                   style="color:gray;text-decoration:none;"
171                   target="_blank">github.com/arnaucube</a>
172            </li>
173          </ul>
174        </div>
175        <div class="row" style="display:inline-block;">
176          Blog made with <a href="http://github.com/arnaucube/blogo/"
177                            target="_blank" style="color: gray;text-decoration:none;">Blogo</a>
178        </div>
179      </div>
180    </footer>
181
182    <script>
183    </script>
184    <script src="js/external-links.js"></script>
185    <script>hljs.initHighlightingOnLoad();</script>
186    <script defer src="js/katex/katex.min.js"></script>
187    <script defer src="js/katex/auto-render.min.js"></script>
188    <script>
189      document.addEventListener("DOMContentLoaded", function() {
190        renderMathInElement(document.body, {
191          displayMode: false,
192          // customised options
193          // • auto-render specific keys, e.g.:
194          delimiters: [
195            {left: '$$', right: '$$', display: true},
196            {left: '$', right: '$', display: false},
197            {left: "\\[", right: "\\]", display: true},
198            {left: "\\(", right: "\\)", display: false},
199            {left: "\\begin{equation}", right: "\\end{equation}", display: true}
200          ],
201          // • rendering keys, e.g.:
202          throwOnError : true
203        });
204      });
205
206      ///
207      let theme = localStorage.getItem("theme");
208      if ((theme === "light-theme")||(theme==null)) {
209          theme = "light-theme";
210          document.getElementById("themeSwitcher").checked = false;
211      } else if (theme === "dark-theme") {
212          theme = "dark-theme";
213          document.getElementById("themeSwitcher").checked = true;
214      }
215      document.body.className = theme;
216      localStorage.setItem("theme", theme);
217
218      function switchTheme() {
219        theme = localStorage.getItem("theme");
220        if (theme === "light-theme") {
221          theme = "dark-theme";
222          document.getElementById("themeSwitcher").checked = true;
223        } else {
224          theme = "light-theme";
225          document.getElementById("themeSwitcher").checked = false;
226        }
227        document.body.className = theme;
228        localStorage.setItem("theme", theme);
229
230        console.log(theme);
231      }
232    </script>
233    <script>
234    function tagLinks(tagName) {
235      var tags = document.getElementsByTagName(tagName);
236      for (var i=0, hElem; hElem =  tags[i]; i++) {
237        if (hElem.parentNode.className=="row postThumb") {
238          continue;
239        }
240        hElem.id = hElem.innerHTML.toLowerCase().replace(" ", "-");
241        hElem.innerHTML = "<a style='color:black!important;' href='#"+hElem.id+"'>"+hElem.innerHTML+"</a>";
242      }
243    }
244    tagLinks("h2");
245    tagLinks("h3");
246    tagLinks("h4");
247    tagLinks("h5");
248    </script>
249    <script>
250function generateTOC(tocContainerId = "toc") {
251    const tocContainer = document.getElementById(tocContainerId);
252    if (!tocContainer) return;
253
254    const headings = document.querySelectorAll("h2, h3, h4, h5, h6");
255    if (!headings.length) return;
256
257    // Generate IDs if missing
258    headings.forEach((heading, index) => {
259        if (!heading.id) {
260            heading.id =
261                heading.textContent
262                    .trim()
263                    .toLowerCase()
264                    .replace(/[^\w\s-]/g, "")
265                    .replace(/\s+/g, "-") +
266                "-" +
267                index;
268        }
269    });
270
271    const toc = document.createElement("ul");
272    let currentLevel = 1;
273    let currentList = toc;
274    const stack = [toc];
275
276    headings.forEach((heading) => {
277        const level = parseInt(heading.tagName.substring(1), 10);
278
279        const li = document.createElement("li");
280        const a = document.createElement("a");
281
282        a.href = "#" + heading.id;
283        a.textContent = heading.textContent;
284
285        li.appendChild(a);
286
287        if (level > currentLevel) {
288            for (let i = currentLevel; i < level; i++) {
289                const nestedList = document.createElement("ul");
290
291                const lastLi =
292                    currentList.lastElementChild ||
293                    currentList.appendChild(document.createElement("ul"));
294
295                lastLi.appendChild(nestedList);
296
297                stack.push(nestedList);
298                currentList = nestedList;
299            }
300        } else if (level < currentLevel) {
301            for (let i = currentLevel; i > level; i--) {
302                stack.pop();
303            }
304            currentList = stack[stack.length - 1];
305        }
306
307        currentList.appendChild(li);
308        currentLevel = level;
309    });
310
311    tocContainer.innerHTML = "";
312    tocContainer.appendChild(toc);
313}
314
315document.addEventListener("DOMContentLoaded", () => {
316    generateTOC();
317});
318    </script>
319    <script src="js/mermaid.min.js"></script>
320
321  </body>
322</html>
323