arnaucube.com/public/shamir-secret-sharing.html
public/shamir-secret-sharing.htmlRaw
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="https://cdn.jsdelivr.net/npm/bootstrap@5.0.2/dist/css/bootstrap.min.css" rel="stylesheet" integrity="sha384-EVSTQN3/azprG1Anm3QDgpJLIm9Nao0Yz1ztcQTwFspd3yD65VohhpuuCOmLASjC" crossorigin="anonymous">
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="https://cdn.jsdelivr.net/npm/katex@0.13.11/dist/katex.min.css" integrity="sha384-Um5gpz1odJg5Z4HAmzPtgZKdTBHZdw8S29IecapCSB31ligYPhHQZMIlWLYQGVoc" crossorigin="anonymous">
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’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 $k$ different parts, and set a minimum threshold $n$, which defines the number of required parts to recover the <em>secret</em>, so just by putting together any $n$ 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 $n$ distinct points over $\mathbb{R}^2$, there is a unique polynomial $p(x) \in \mathbb{R[x]}$ of degree $n-1$ which goes through all of them.
76From the ‘other side’ point of view, this means that if we have a polynomial of degree $n-1$, we can take $n$ points (or more) from it, and we will be able to recover the original polynomial from those $n$ points.</p>
77
78<p>We can see this starting with a line. If we are given any two points $P_0=(x_0, y_0)$ and $P_1=(x_1, y_1)$ 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 $1$ polynomial, so, if we pick $2$ points from it, we later can recover the original line.</p>
85
86<p>Same happens with polynomials of degree $2$. Let $p(x)$ be a polynomial of degree $2$ defined by $p(x)= x^2 - 5x - 6$. We can create infinity of polynomials of degree $2$ that go through $2$ points, but with 3 points there is a unique polynomial degree $2$</p>
87
88<p>As the degree is $2$, if we pick $3$ 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 $(x_0, y_0), (x_1, y_1), …, (x_n, x_n)$,</p>
96
97<p>$$
98I(x) = \sum_{i=0}^n y_i l_i(x)\newline
99where \space\space\space l_i(x) = \prod_{0\leq j \leq n, j\neq i} \frac{x-x_j}{x_i - x_j}
100$$</p>
101
102<h3>Shamir’s secret sharing</h3>
103
104<p>As we’ve seen, for a degree $n-1$ polynomial we can pick $n$ 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>
105
106<p>Let $s$ be our secret. We want to generate $k$ pieces and set a threshold $n$ which is the minimum number of pieces that are needed to reconstruct the secret $s$. We can define a polynomial of degree $n-1$, and pick $k$ points from that polynomial, so in this way with just putting together $n$ points of $k$ we will be able to reconstruct the original polynomial. And, we can place our secret $s$ in the <em>constant term</em> of the polynomial (the one that has $x^0$), in this way, when we reconstruct the polynomial using $n$ out of $k$ points, we will be able to recover the secret $s$.</p>
107
108<p>We can see this with an example with actual numbers (we will use small numbers):
109Imagine that we want to generate $5$ pieces from our secret, and define that just by putting together $3$ of the pieces we can recover the secret, this means setting $n=3$ and $k=5$. Then we will generate a polynomial of degree $n-1=2$, by $p(x) = \alpha_0 + \alpha_1 x + \alpha_2 x^2$, where $\alpha_0 = s$ (the secret).</p>
110
111<p>We will work over a finite field of size $p$, where $p$ is a prime number. For our example we will work over $\mathbb{F}_{19}$, 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>
112
113<p>Let our secret be $s=14$. We now generate our polynomial of degree $n-1=2$, where $s$ will be the constant coefficient: $p(x)= s + \alpha_1 x^1 + \alpha_2 x^2$. We can set $\alpha_1$ and $\alpha_2$ into any random value, as example $\alpha_1=4$ and $\alpha_2=6$. So we have our polynomial: $p(x) = 14 + 4 x + 6 x^2$.</p>
114
115<p>Now that we have the polynomial, we can pick $k$ points from it, using incremental indexes for the $x$ coordinate: $P_1=(1, p(1)), P_2=(2, p(2)), \space\ldots\space, P_k=(k, p(k))$. With the numbers of our example this is (remember, we work over $\mathbb{F}_{19}$):
116$$
117p(x) = 14 + 4 x + 6 x^2,\newline
118p(1)=14 + 4 \cdot 1 + 6 \cdot 1^2 = 24 \space (mod \space 19) = 5\newline
119p(2)=14 + 4 \cdot 2 + 6 \cdot 2^2 = 46 \space (mod \space 19) = 8\newline
120p(3)=14 + 4 \cdot 3 + 6 \cdot 3^2 = 80 \space (mod \space 19) = 4\newline
121p(4)=14 + 4 \cdot 4 + 6 \cdot 4^2 = 126 \space (mod \space 19) = 12\newline
122p(5)=14 + 4 \cdot 5 + 6 \cdot 5^2 = 184 \space (mod \space 19) = 13
123$$
124So our $k$ points are: $(1,5), (2,8), (3,4), (4,12), (5,13)$. We can distribute these points as our ‘secret parts’.
125In order to recover the secret, we need at least $n=3$ points, for example $P_1$, $P_3$, $P_5$, and we compute the <em>Lagrange polynomial interpolation</em> to recover the original polynomial (remember, we work over $\mathbb{F}_{19}$):</p>
126
127<p>$$
128I(x) = \sum_{i=0}^n y_i l_i(x) \space\space
129where \space\space\space l_i(x) = \prod_{0 \leq j \leq n \ j\neq i} \frac{x-x_j}{x_i - x_j}
130$$
131$$
132l_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
133l_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
134l_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
135$$
136$$
137I(x) = y_2 \cdot l_2(x) + y_4 \cdot l_4(x) + y_5 \cdot l_5(x)\newline
138= 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
139= \frac{5x^2+17x+18}{8} + \frac{4x^2+14x+1}{15} + \frac{13x^2+5x+1}{8}\newline
140= 3x^2+14x+7 + 18x^2+6x+14 + 4x^2+3x+12\newline
141= 6x^2 + 4x + 14
142$$</p>
143
144<p>We can now take the <em>constant coefficient</em>, or just evaluate the obtained polynomial at 0, $p(0) = 6 \cdot 0^2 + 4 \cdot 0 + 14 = 14$, and we obtain our original secret $s=14$.</p>
145
146<h3>Conclusions</h3>
147
148<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>
149
150<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>
151
152 </div>
153
154 <footer style="text-align:center; margin-top:100px;margin-bottom:50px;">
155 <div class="container">
156 <div class="row">
157 <ul class="list-inline">
158 <li><a href="https://twitter.com/arnaucube"
159 style="color:gray;text-decoration:none;"
160 target="_blank">twitter.com/arnaucube</a>
161 </li>
162 <li><a href="https://github.com/arnaucube"
163 style="color:gray;text-decoration:none;"
164 target="_blank">github.com/arnaucube</a>
165 </li>
166 </ul>
167 </div>
168 <div class="row" style="display:inline-block;">
169 Blog made with <a href="http://github.com/arnaucube/blogo/"
170 target="_blank" style="color: gray;text-decoration:none;">Blogo</a>
171 </div>
172 </div>
173 </footer>
174
175 <script>
176 </script>
177 <script src="js/external-links.js"></script>
178 <script>hljs.initHighlightingOnLoad();</script>
179 <script defer src="https://cdn.jsdelivr.net/npm/katex@0.13.11/dist/katex.min.js" integrity="sha384-YNHdsYkH6gMx9y3mRkmcJ2mFUjTd0qNQQvY9VYZgQd7DcN7env35GzlmFaZ23JGp" crossorigin="anonymous"></script>
180 <script defer src="https://cdn.jsdelivr.net/npm/katex@0.13.11/dist/contrib/auto-render.min.js" integrity="sha384-vZTG03m+2yp6N6BNi5iM4rW4oIwk5DfcNdFfxkk9ZWpDriOkXX8voJBFrAO7MpVl" crossorigin="anonymous"></script>
181 <script>
182 document.addEventListener("DOMContentLoaded", function() {
183 renderMathInElement(document.body, {
184 displayMode: false,
185 // customised options
186 // • auto-render specific keys, e.g.:
187 delimiters: [
188 {left: '$$', right: '$$', display: true},
189 {left: '$', right: '$', display: false},
190 ],
191 // • rendering keys, e.g.:
192 throwOnError : true
193 });
194 });
195
196 ///
197 let theme = localStorage.getItem("theme");
198 if ((theme === "light-theme")||(theme==null)) {
199 theme = "light-theme";
200 document.getElementById("themeSwitcher").checked = false;
201 } else if (theme === "dark-theme") {
202 theme = "dark-theme";
203 document.getElementById("themeSwitcher").checked = true;
204 }
205 document.body.className = theme;
206 localStorage.setItem("theme", theme);
207
208 function switchTheme() {
209 theme = localStorage.getItem("theme");
210 if (theme === "light-theme") {
211 theme = "dark-theme";
212 document.getElementById("themeSwitcher").checked = true;
213 } else {
214 theme = "light-theme";
215 document.getElementById("themeSwitcher").checked = false;
216 }
217 document.body.className = theme;
218 localStorage.setItem("theme", theme);
219
220 console.log(theme);
221 }
222 </script>
223 <script>
224 function tagLinks(tagName) {
225 var tags = document.getElementsByTagName(tagName);
226 for (var i=0, hElem; hElem = tags[i]; i++) {
227 if (hElem.parentNode.className=="row postThumb") {
228 continue;
229 }
230 hElem.id = hElem.innerHTML.toLowerCase().replace(" ", "-");
231 hElem.innerHTML = "<a style='text-decoration:none;color:black;' href='#"+hElem.id+"'>"+hElem.innerHTML+"</a>";
232 }
233 }
234 tagLinks("h2");
235 tagLinks("h3");
236 tagLinks("h4");
237 tagLinks("h5");
238 </script>
239 <script src="https://cdn.jsdelivr.net/npm/mermaid/dist/mermaid.min.js"></script>
240
241
242 </body>
243</html>
244