slides/src/shamirsecretsharing/shamirsecretsharing.md
src/shamirsecretsharing/shamirsecretsharing.mdRaw
1# Shamir's Secret Sharing
2
3<img src="https://arnaucube.com/img/logoArnauCubeTransparent.png" style="max-width:20%; float:right;" />
4
5- https://arnaucube.com
6- https://github.com/arnaucube
7- https://twitter.com/arnaucube
8<br><br><br>
9<div style="float:right;font-size:80%;">
10 <a href="https://creativecommons.org/licenses/by-nc-sa/4.0/"><img src="https://licensebuttons.net/l/by-nc-sa/4.0/88x31.png" /></a>
11 <br>
12 2019-07-05
13</div>
14
15---
16
17# Intro
18- I'm not an expert on the field, neither a mathematician. Just an engineer with interest for cryptography
19- Short talk (15 min), with the objective to make a practical introduction to the Shamir's Secret Sharing algorithm
20- Is not a talk about mathematical demostrations, is a talk with the objective to get the basic notions to be able to do a practical implementation of the algorithm
21- After the talk, we will do a practical workshop to implement the concepts. We can offer support for Go, Rust, Python and Nodejs (you can choose any other language, but we will not be able to help)
22
23---
24
25- Cryptographic algorithm
26- Created by Adi Shamir, in 1979
27 - also known by the $RSA$ cryptosystem
28 - explained in few months ago in a similar talk: https://github.com/arnaucube/slides/rsa
29
30---
31## What's this about?
32- imagine having a password that you want to share with 5 persons, in a way that they need to join their parts to get the original password
33- take the password, split it in 5 parts, and give one part to each one
34- when they need to recover it, they just need to get together, put all the pieces and recover the password (the `secret`)
35- this, has the problem that if a person looses its part, the secret will not be recovered anymore.. luckly we have a solution here:
36
37---
38
39- Shamir's Secret Sharing:
40 - from a secret to be shared, we generate 5 parts, but we can specify a number of parts that are needed to recover the secret
41 - so for example, we generate 5 parts, where we will need only 3 of that 5 parts to recover the secret, and the order doesn't matter
42 - we have the ability to define the thresholds of $M$ parts to be created, and $N$ parts to be able the recover
43
44---
45
46- 2 points are sufficient to define a line
47- 3 points are sufficient to define a parabola
48- 4 points are sufficient to define a cubic curve
49- $K$ points are suficient to define a polynomial of degree $k-1$
50
51We can create infinity of polynomials of degree 2, that goes through 2 points, but with 3 points, we can define a polynomial of degree 2 unique.
52
53
54
55---
56
57## Naming
58
59- `s`: secret
60- `m`: number of parts to be created
61- `n`: number of minimum parts necessary to recover the secret
62- `p`: random prime number, the Finite Field will be over that value
63
64---
65
66## Secret generation
67- we want that are necessary $n$ parts of $m$ to recover $s$
68 - where $n<m$
69- need to create a polynomial of degree $n-1$
70$f(x) = \alpha_0 + \alpha_1 x + \alpha_2 x^2 + \alpha_3 x^3 + ... + + \alpha_{n-1} x^{n-1}$
71- where $\alpha_0$ is the secret $s$
72- $\alpha_i$ are random values that build the polynomial
73*where $\alpha_0$ is the secret to share, and $\alpha_i$ are the random values inside the $Finite Field$
74
75---
76
77$f(x) = \alpha_0 + \alpha_1 x + \alpha_2 x^2 + \alpha_3 x^3 + ... + + \alpha_{n-1} x^{n-1}$
78
79- the packets that we will generate are $P = (x, f(x))$
80 - where $x$ is each one of the values between $1$ and $m$
81 - $P_1=(1, f(1))$
82 - $P_2=(2, f(2))$
83 - $P_3=(3, f(3))$
84 - ...
85 - $P_m=(m, f(m))$
86
87---
88## Secret recovery
89- in order to recover the secret $s$, we will need a minimum of $n$ points of the polynomial
90 - the order doesn't matter
91- with that $n$ parts, we do Lagrange Interpolation/Polynomial Interpolation
92
93---
94
95## Polynomial Interpolation / Lagrange Interpolation
96- for a group of points, we can find the smallest degree polynomial that goees through all that points
97 - this polynomial is unique for each group of points
98
99
100
101---
102
103
104
105---
106
107$L(x) = \sum_{j=0}^{n} y_j l_j(x)$
108
109<br><br>
110
111
112
113---
114
115## Wikipedia example
116*example over real numbers, in the practical world, we use the algorithm in the Finite Field over $p$
117<span style="font-size:70%;float:right;">(more details: https://en.wikipedia.org/wiki/Shamir's_Secret_Sharing#Problem)</span><br>
118- $s=1234$
119- $m=6$
120- $n=3$
121- $f(x) = \alpha_0 + \alpha_1 x + \alpha_2 x^2$
122 - $\alpha_0 = s = 1234$
123 - $\alpha_1 = 166$ *(random)*
124 - $\alpha_2 = 94$ *(random)*
125- $f(x) = 1234 + 166 x + 94 x^2$
126
127---
128
129- $f(x) = 1234 + 166 x + 94 x^2$
130- we calculate the points $P = (x, f(x))$
131 - where $x$ is each one of the values between $1$ and $m$
132 - $P_1=(1, f(1)) = (1, 1494)$
133 - $P_2=(2, f(2)) = (2, 1942)$
134 - $P_3=(3, f(3)) = (3, 2578)$
135 - $P_4=(4, f(4)) = (4, 3402)$
136 - $P_5=(5, f(5)) = (5, 4414)$
137 - $P_6=(6, f(6)) = (6, 5614)$
138---
139
140- to recover the secret, let's imagine that we take the packets 2, 4, 5
141 - $(x_0, y_0) = (2, 1942)$
142 - $(x_0, y_0) = (4, 3402)$
143 - $(x_0, y_0) = (5, 4414)$
144
145---
146
147- let's calculate the Lagrange Interpolation
148 - 
149 - 
150 - 
151 - 
152- obtaining $f(x) = \alpha_0 + \alpha_1 x + \alpha_2 x^2$, where $\alpha_0$ is the secret $s$ recovered
153 - where we eavluate the polynomial at $f(0)$, obtaining $\alpha_0 = s$
154- *we are not going into details now, but if you want in the practical workshop we can analyze the 'mathematical' part of all of this
155
156---
157
158# And now... practical implementation
159- full night long
160- big ints are your friends
161- $L(x) = \sum_{j=0}^{n} y_j l_j(x)$
162
163
164# About
165
166<img src="https://arnaucube.com/img/logoArnauCubeTransparent.png" style="max-width:20%; float:right;" />
167
168- https://arnaucube.com
169- https://github.com/arnaucube
170- https://twitter.com/arnaucube
171<br>
172<div style="float:right;font-size:80%;">
173 <a href="https://creativecommons.org/licenses/by-nc-sa/4.0/"><img src="https://licensebuttons.net/l/by-nc-sa/4.0/88x31.png" /></a>
174 <br>
175 2019-07-05
176</div>