commit 3d6a4646aaa9fe64e5f9bf5e151106525eea6a7f
parent 7022f91ac9c65ace33aff029873be71a09c1572b
Author: oscarbenedito <oscar@obenedito.org>
Date:   Mon, 24 Feb 2020 00:15:41 +0100

Fix MathJax x-overflow

Diffstat:
Massets/css/style.scss | 2+-
Mcontent/blog/2020-02-23-sharing-a-secret.pdc | 6++++++
Mcontent/jsweblabels.html | 2+-

3 files changed, 8 insertions(+), 2 deletions(-)
diff --git a/assets/css/style.scss b/assets/css/style.scss
@@ -687,6 +687,6 @@ article {

/* Others
-------------------------------------------------- */
-.table-container {
+.x-overflow-container {
overflow-x: auto;
}
diff --git a/content/blog/2020-02-23-sharing-a-secret.pdc b/content/blog/2020-02-23-sharing-a-secret.pdc
@@ -19,7 +19,9 @@ Shamir's method is based on the fact that given $n + 1$ pairs $(x_i, y_i)$ such

Let's put it into practice. Given a secret $S$, to be shared with $n$ parties in a way that any $k$ parties can retrieve it, we'll build the following polynomial:

+<div class="x-overflow-container">
$$p(x) = S + a_1 x + a_2 x^2 + ... + a_{k-1} x^{k-1},$$
+</div>

where $a_i$ are random numbers, $\forall i \in \{1, \dots, k-1\}$. Now we'll evaluate our polynomial on $n$ different points (and different from 0) to obtain $n$ pairs of the form $(x_i, p(x_i))$. This will be the shares of the secret. Each party will get one share. We know that $k$ shares define a unique polynomial $p$ of degree $k-1$, (if we find it, we'll find $S$). On the other hand, there are an infinite amount of polynomials of degree $k-1$ that interpolate $k-1$ points, so the secret cannot be easily obtained by gaining access to $k-1$ shares[^integers].

@@ -29,11 +31,15 @@ If we want to recover the secret from $k$ shares, we can interpolate the $k$ poi

[^proof]: Let's quickly proof that the $p$ defined in Lagrange's form ($\bar{p}$ from now on) is the same as the previously defined $p$. $\bar{p}$ is clearly a polynomial of degree (at most) $k-1$, since it is the sum of polynomials of degree $k-1$, so we only need to proof that it interpolates the points given (we'll asume that the fact that there is only one polynomial of degree at most $k-1$ that interpolates $k$ points is true). That is easy to proof since $i \neq j \implies l_i(x_j) = 0$ and $l_i(x_i) = 1$, therefore having $\bar{p}(x_i) = p(x_i) l_i(x_i) = p(x_i)$.

+<div class="x-overflow-container">
$$p(x) = \sum_{i=1}^{k} p(x_i) l_i(x),$$
+</div>

where

+<div class="x-overflow-container">
$$l_i(x) = \prod_{\begin{smallmatrix}1\leq m\leq k\\ m\neq i\end{smallmatrix}} \frac{x-x_m}{x_i-x_m}.$$
+</div>

Now, evaluating on $x = 0$ we'll find the secret (because $p(0) = S$).

diff --git a/content/jsweblabels.html b/content/jsweblabels.html
@@ -6,7 +6,7 @@ type: page