MATH 470 Lecture 18

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

Begin Exam 2 content

Secret Sharing

A 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 (T,W)} -threshhold scheme is a way to share a message among 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 W} participants so that any subset of 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 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 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 M}

1. Pick a prime 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 p \ge \max{(W,M)}}
2. Pick 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 t-1} random numbers 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 s_1, \ldots, s_{T-1}} in 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 \mathbb{Z}/p \mathbb{Z}}
3. Define 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 p(x) = M + s_1 \, x + \dots + s_{T-1} \, x^{T-1}}
4. Pick distinct random numbers 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 x, \ldots, x_w} , and to the 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 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 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 M^d \pmod{n}} is published

Any user can verify the signature via

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( 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 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 M}

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

To verify, the user must:

1. download the public part 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 (p,\alpha, \beta)} and then
2. Accept if 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 \beta^r \, r^s \equiv \alpha^M \pmod{p}} .

Verification works because

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 \begin{align} \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{align}}

DSA

Adopmed by NIST in 1994

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

To check signature,

1. compute 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_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}}