Dominik Farhan

Threshold schemes $(k,l)$

Divides to $k$ parts. $l$ are enough to recover the secret.

We are always calculating in some huge finite field.

$(k,2)$

f(t) = at + b

f(0) = x

f(1) = \text{random}

generating $x^i$ :

x^i = f(i)

$(k,l)$

f

is a polynomial of degree less than

l

over a finite field.

f(0) = x

f(1) \text{ up to } f(l-1) \text{ are random}

we share $f(1) \text{ up to } f(k) .$

The board from the 3rd lecture, by Martin Mareš, http://mj.ucw.cz/vyuka/2021/kry/.

Lemma I.

x_1, \dots, x_t

are all roots of nonzero polynomial

p

then

$p(x) = (x-x_1)(x-x_2) \dots (x-x_t) \cdot q(x)$ , where $q(x)$ is a polynomial with no roots in the field. Which implies that poly with degree $d$ has atmost the same number of roots.

Lemma II.

If polynomials with a degree less than $d$ agree in $d$ points then they are equal.

Proof

r := p-q, \text{deg} < d, x_1,\dots x_d \text{ are roots of }r \implies r=0 \implies p =q

Lagrange theorem

For every $x_1,\dots, x_d$ and $y_1, \dots, y_d$ $\exists ! p \text{ deg} < d: \forall i \in {\left[d\right]}: p(x_i) = y_i$ .

Lagrange interpolation is a way to find such polynomial.

Simple example

Threshold schemes (k,l)(k,l)(k,l)