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’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 ‘other side’ 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’s secret sharing</h3>
113
114<p>As we’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’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 ‘secret parts’.
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>&<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