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 <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’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 ‘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>
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’s secret sharing</h3>
117
118<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>
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 ‘secret parts’.
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>&<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