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\ge \max (W,M)$
2. Pick $t-1$ random numbers $s_1,\dots ,s_{T-1}$ in $\mathbb{\mathbb{Z}}/p\mathbb{\mathbb{Z}}$
3. Define $p(x)=M+s_{1}x+\dots +s_{T-1}{x}^{T-1}$
4. Pick distinct random numbers $x,\dots ,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)),\dots ,(x_T,p(x_T))$. We get

$\begin{array}{rl}M+s_1{x}_1+\dots +s_{T-1}{x}_1^{T-1}& =p(x_1)\\ ⋮\\ M+s_1{x}_T+\dots +s_{T-1}{x}_T^{T-1}& =p(x_T)\end{array}$

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

$\left[\begin{array}{cccc}1& x_1& \dots & x_1^{T-1}\\ ⋮& \ddots & & ⋮\\ ⋮& & \ddots & ⋮\\ 1& x_T& \dots & x_T^{T-1}\end{array}\right]\left[\begin{array}{c}M\\ s_1\\ ⋮\\ s_{T-1}\end{array}\right]=\left[\begin{array}{c}p(x_1)\\ ⋮\\ ⋮\\ p(x_T)\end{array}\right]$

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

$\left|\begin{array}{cccc}1& x_1& \dots & x_1^{T-1}\\ ⋮& \ddots & & ⋮\\ ⋮& & \ddots & ⋮\\ 1& x_T& \dots & x_T^{T-1}\end{array}\right|=\prod _{n\ge i>j\ge 1}(x_i-x_j)$

This matrix is a van Der Monde matrix.

Back to ChOcOlAtE

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

So we need to solve $\left[\begin{array}{ccc}1& x_1& x_1^2\\ 1& x_2& x_2^2\\ 1& x_3& x_3^2\end{array}\right]\left[\begin{array}{c}M\\ s_1\\ s_2\end{array}\right]=\left[\begin{array}{c}p(x_1)\\ p(x_2)\\ p(x_3)\end{array}\right]$

For $\overrightarrow{x}=⟨12,38,2⟩$ and $\overrightarrow{p}(\overrightarrow{x})=⟨96,25,17⟩$, 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(\mathrm{mod}n)$ is published

Any user can verify the signature via

${\left(M^d\right)}^e=m(\mathrm{mod}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 $(p,\alpha ,a,\beta ={\alpha }^a)$ and picks a random $k\in {(\mathbb{\mathbb{Z}}/(p-1)\mathbb{\mathbb{Z}})}^{*}$
2. Alice computes $r={\alpha }^k(\mathrm{mod}p)$ and
3. $s=k^{-1}(M-ar)(\mathrm{mod}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(\mathrm{mod}p)$.

Verification works because

$\begin{array}{rl}{\beta }^r{r}^s& \equiv {\alpha }^m(\mathrm{mod}p)\\ {\left({\alpha }^a\right)}^r{\left({\alpha }^k\right)}^s& \equiv {\alpha }^m(\mathrm{mod}p)\\ {\alpha }^{ar+ks}& \equiv {\alpha }^m(\mathrm{mod}p)\\ {\alpha }^{ar+k(k^{-1}(m-ar))}& \equiv {\alpha }^m(\mathrm{mod}p)\\ {\alpha }^{\cancel{ar}+m\cancel{-ar}}& \equiv {\alpha }^m(\mathrm{mod}p)\end{array}$

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}}(\mathrm{mod}p)$
3. Alice picks a secret $a\in \{1,\dots ,q-1\}$ and calculates $\beta ={\alpha }^a$
4. Pick random $k\in \{1,\dots ,q-2\}$
5. Compute $r=\left({\alpha }^k(\mathrm{mod}p)\right)(\mathrm{mod}q)$
6. Compute $s=k^{-1}(m+ar)(\mathrm{mod}q)$
7. Signature is $(r,s)$

To check signature,

1. compute $u_1=s^{-1}m(\mathrm{mod}q)$ and $u_2=s^{-1}r(\mathrm{mod}q)$
2. Accept signature iff $\left({\alpha }^{u_1}{\beta }^{u_2}(\mathrm{mod}p)\right)\equiv r(\mathrm{mod}q)$