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