MATH 470 Lecture 18

« previous | Tuesday, March 26, 2013 | next »

Begin Exam 2 content

Secret Sharing

A $(T,W)$-threshhold scheme is a way to share a message among $W$ participants so that any subset of $T$ participants can recover the message, but no smaller subset.

Small example: (2,2)-threshhold schemes have been in various movies involving nuclear missiles (e.g. War Games)

Another example: (3,55)-threshhold scheme could protect the password to some chocolate

In 1979, Adi Shamir found following scheme to hide a message $M$

1. Pick a prime $p\geq \max {(W,M)}$
2. Pick $t-1$ random numbers $s_{1},\ldots ,s_{T-1}$ in $\mathbb {Z} /p\mathbb {Z}$
3. Define $p(x)=M+s_{1}\,x+\dots +s_{T-1}\,x^{T-1}$
4. Pick distinct random numbers $x,\ldots ,x_{w}$, and to the $i$^th participant, give $(x_{i},p(x_{i}))$

Idea: $n$ points in Euclidean space define a unique $n$-degree polynomial curve.

Lemmas

1. No subset of $T-1$ participants can recover $M$.
2. Any subset of $T$ participants can recover $M$.

Proof. Take, say, the first $T$ participants $(x_{1},p(x_{1})),\ldots ,(x_{T},p(x_{T}))$. We get

${\begin{aligned}M+s_{1}\,x_{1}+\dots +s_{T-1}\,x_{1}^{T-1}&=p(x_{1})\\\vdots \\M+s_{1}\,x_{T}+\dots +s_{T-1}\,x_{T}^{T-1}&=p(x_{T})\end{aligned}}$

Which is a $T\times T$ linear system of equations, so we can solve

${\begin{bmatrix}1&x_{1}&\dots &x_{1}^{T-1}\\\vdots &\ddots &&\vdots \\\vdots &&\ddots &\vdots \\1&x_{T}&\dots &x_{T}^{T-1}\end{bmatrix}}\,{\begin{bmatrix}M\\s_{1}\\\vdots \\s_{T-1}\end{bmatrix}}={\begin{bmatrix}p(x_{1})\\\vdots \\\vdots \\p(x_{T})\end{bmatrix}}$

Claim: The preceding matrix has a nonzero determinant and thus we have a unique solution!

${\begin{vmatrix}1&x_{1}&\dots &x_{1}^{T-1}\\\vdots &\ddots &&\vdots \\\vdots &&\ddots &\vdots \\1&x_{T}&\dots &x_{T}^{T-1}\end{vmatrix}}=\prod _{n\geq i>j\geq 1}(x_{i}-x_{j})$

This matrix is a van Der Monde matrix.

Back to ChOcOlAtE

${\begin{aligned}p&=131\\T&=3\\W&=55\end{aligned}}$

So we need to solve ${\begin{bmatrix}1&x_{1}&x_{1}^{2}\\1&x_{2}&x_{2}^{2}\\1&x_{3}&x_{3}^{2}\end{bmatrix}}\,{\begin{bmatrix}M\\s_{1}\\s_{2}\end{bmatrix}}={\begin{bmatrix}p(x_{1})\\p(x_{2})\\p(x_{3})\end{bmatrix}}$

For ${\vec {x}}=\left\langle 12,38,2\right\rangle$ and ${\vec {p}}({\vec {x}})=\left\langle 96,25,17\right\rangle$, we get $M=23$

Spoils of the Hunt

Digital Signatures

In our Iran/UN example, we used the RSA digital signature. We also have El-Gamal and DSA (which is still used today).

If Alice needs to sign a message $M$,

1. Alice sets up as in RSA $(p,q,n,e,d)$ and publishes $(e,n)$ and keeps $(d,p,q)$ private.
2. The signature $M^{d}{\pmod {n}}$ is published

Any user can verify the signature via

$\left(M^{d}\right)^{e}=m{\pmod {n}}$

Note: In practice, digital signatures are slow, so usually, only a short digest of the message is signed. This is one setting where hash functions enter.

El Gamal

To sign a message $M$

1. Alice sets up as in El Gamal $\left(p,\alpha ,a,\beta =\alpha ^{a}\right)$ and picks a random $k\in \left(\mathbb {Z} /(p-1)\mathbb {Z} \right)^{*}$
2. Alice computes $r=\alpha ^{k}{\pmod {p}}$ and
3. $s=k^{-1}\left(M-a\,r\right){\pmod {p-1}}$
4. Alice sends $(M,r,s)$

To verify, the user must:

1. download the public part $(p,\alpha ,\beta )$ and then
2. Accept if $\beta ^{r}\,r^{s}\equiv \alpha ^{M}{\pmod {p}}$.

Verification works because

${\begin{aligned}\beta ^{r}\,r^{s}&\equiv \alpha ^{m}{\pmod {p}}\\\left(\alpha ^{a}\right)^{r}\,\left(\alpha ^{k}\right)^{s}&\equiv \alpha ^{m}{\pmod {p}}\\\alpha ^{a\,r+k\,s}&\equiv \alpha ^{m}{\pmod {p}}\\\alpha ^{a\,r+k(k^{-1}(m-ar))}&\equiv \alpha ^{m}{\pmod {p}}\\\alpha ^{{\cancel {a\,r}}+m{\cancel {-a\,r}}}&\equiv \alpha ^{m}{\pmod {p}}\end{aligned}}$

DSA

Adopmed by NIST in 1994

1. Alice finds a 160-bit prime $q$ and a larger prime $p$ with $q\mid (p-1)$
2. Alice picks a primitive root $g$ mod $p$ and sets $\alpha =g^{\frac {p-1}{q}}{\pmod {p}}$
3. Alice picks a secret $a\in \left\{1,\ldots ,q-1\right\}$ and calculates $\beta =\alpha ^{a}$
4. Pick random $k\in \left\{1,\ldots ,q-2\right\}$
5. Compute $r=\left(\alpha ^{k}{\pmod {p}}\right){\pmod {q}}$
6. Compute $s=k^{-1}(m+ar){\pmod {q}}$
7. Signature is $(r,s)$

To check signature,

1. compute $u_{1}=s^{-1}\,m{\pmod {q}}$ and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle u_2 = s^{-1} \, r \pmod{q}}
2. Accept signature iff Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left( \alpha^{u_1} \, \beta^{u_2} \pmod{p} \right) \equiv r \pmod{q}}