Unconditional Cryptography

☆ Secret Sharing

DNS (for Domain Name System) maps human-memorable Internet domains like joyofcryptography.com to machine-readable IP addresses like 104.21.52.139. The traditional DNS protocol is not authenticated, meaning that a malicious DNS server could answer client queries with incorrect IP addresses. An extension to DNS, called DNSSEC, adds some cryptographic authentication to the protocol, to prevent this problematic behavior.

DNSSEC requires one “master key,” which holds authority over the entire Internet's DNS information. The organization that maintains the DNSSEC master key has chosen the following interesting backup strategy: The master key is split into seven pieces, with each piece given to a trusted human. In order to recover the key, one must combine any five of these seven pieces. On the other hand, combining any four of the seven pieces reveals no information about the key!

How is this possible? The answer is a primitive called a secret-sharing scheme, the topic of this chapter.

3.1. Defining secret sharing

Secret sharing is a way to encode a value $\ptxt$ into several pieces, called shares. The encoding is associated with a threshold value $t$ such that:

It is possible to recover $\ptxt$ from any $t$ of the shares.
Any collection of fewer than $t$ shares reveals nothing about $\ptxt$ .

It's often useful to think of one person, called the dealer, having the secret $\ptxt$ , generating the shares, and then distributing each share to a separate user. (This is not the only way to use secret sharing, but it is the easiest to talk about.)

We will number the users 1 through $n$ , and name the shares $S_1, \ldots, S_n$ , with user $i$ receiving share $S_i$ . Any subset $\mathcal{U} \subseteq \{1, \ldots, n\}$ can refer to a set of users, and we use the following notation to refer to their corresponding set of shares:

// shares belonging to users in

\U

\Filter(\U, S_1, \ldots, S_n)

for

i=1

n

i \not\in \U

S_i := \mynull

return

(S_1, \ldots, S_n)

For example:

\begin{aligned} \Filter(\{1,3,5\}, \bit{A}, \bit{B}, \bit{C}, \bit{D}, \bit{E}) &= (\bit{A}, \mynull, \bit{C}, \mynull, \bit{E}); \\ \Filter(\{2,3,4\}, \bit{A}, \bit{B}, \bit{C}, \bit{D}, \bit{E}) &= (\mynull, \bit{B}, \bit{C}, \bit{D},\mynull).\end{aligned}

The reason we replace shares with $\mynull$ , rather than removing them altogether to make a shorter list, is that it preserves information about which share belongs to which user—information that can be used by the algorithm that recovers the secret from the shares.

Definition 3.1.1 (Secret sharing scheme: syntax & correctness)

A $t$ -out-of- $n$ secret sharing scheme consists of the following algorithms:

$\Share$ : a randomized algorithm that takes a value $\ptxt \in \M$ as input, and outputs a list of $n$ shares $S \in \mathcal{S}^n$ .
$\Reconstruct$ : a deterministic algorithm that takes a partial list of shares $S \in (\mathcal{S} \cup \{\mynull\})^n$ as input, and outputs a value $\ptxt \in \M$ .

The value $t$ is called the threshold of the scheme.

The scheme is correct if, for all $\ptxt \in \M$ and all $\U \subseteq \{1, \ldots, n\}$ with $|\U| = t$ , we have:

\PR{ \Reconstruct\Bigl( \Filter\bigl( \U, \Share(\ptxt)\bigr)\Bigr) = \ptxt } = 1.

In other words, the secret $\ptxt$ can be recovered just from the shares belonging to users $\U$ .

The goal of secret sharing is that any collection of fewer than $t$ shares should reveal nothing about the secret. We formalize this security requirement in an attack scenario in which a victim runs the $\Share$ algorithm. Since the only input to the $\Share$ algorithm is not a key, we can let the adversary have control over it. Next, the output of $\Share$ is passed through the $\Filter$ function before being given to the adversary, to ensure that the adversary sees fewer than $t$ shares. Finally, we can rephrase the informal security goal in the real-or-random paradigm: Any collection of fewer than $t$ shares appears uniformly distributed (i.e., looks like random junk).

Thus, we define two libraries that give output $\Filter( \U, S_1, \ldots, S_n)$ to the adversary. In one library, $S_1, \ldots, S_n$ are valid shares, and in the other they are chosen uniformly. The question remains: Where does $\U$ come from? We want our security guarantee to apply no matter what $\U$ is used, as long as $|\U| < t$ . Thus, we simply let the adversary choose $\U$ . The library enforces the constraint $|\U| < t$ by simply returning an error if the adversary chooses $\U$ too large.

Definition 3.1.2 (Security for secret sharing schemes)

A $t$ -out-of- $n$ secret sharing scheme $\Sigma$ is secure if the following two libraries are interchangeable:

\lib{ss-real}^\Sigma

\ssshare(\ptxt, \U)

|\U| \ge \Sigma.t

: return

\myerr

(S_1, \ldots, S_n) := \Sigma.\Share(\ptxt)

return

\Filter(\U, S_1, \ldots, S_n)

\equiv

\lib{ss-rand}^\Sigma

\ssshare(\ptxt, \U)

|\U| \ge \Sigma.t

: return

\myerr

for

i=1

\Sigma.n

S_i \gets \Sigma.\mathcal{S}

return

\Filter(\U, S_1, \ldots, S_n)

A Bad Secret Sharing Scheme: The “obvious” way to split a secret is to simply chop it into pieces. The secret can then be reconstructed by concatenating these pieces. This obvious approach is not a secure secret sharing scheme!

Example 3.1.3 (Naïve secret sharing scheme)

The following is not a secure $n$ -out-of- $n$ secret sharing scheme:

\M := \bits^{nk}

\Share(\ptxt)

write

S_1 \| S_2 \| \cdots \| S_n := \ptxt

// this means: chop

\ptxt

into

n

// pieces, each

k

bits long;

S_i

// is the

i

th piece

return

(S_1, S_2, \ldots, S_n)

\quad

n

-out-of-

n

scheme, so

// each

S_i

is non-

\mynull

\Reconstruct(S_1, \ldots, S_n)

return

S_1 \| \cdots \| S_n

In other words, the following two libraries are not interchangeable:

\lib{ss-real}

\ssshare(\ptxt, \U)

|\U| \ge n

: return

\myerr

\Share(\ptxt)

S_1 \| S_2 \| \cdots \| S_n := \ptxt

return

\Filter(\U, S_1, \ldots, S_n)

\not\equiv

\lib{ss-rand}

\ssshare(\ptxt, \U)

|\U| \ge n

: return

\myerr

for

i=1

n

S_i \gets \bits^k

return

\Filter(\U, S_1, \ldots, S_n)

The reason is simple: Each share reveals some information about the secret! The first share reveals the first $k$ bits of $\ptxt$ , and so on. The attack is therefore quite simple:

\A

\ptxt := \bit0^{nk}

\U := \{1, \ldots, n-1\}

(S_1, \ldots, S_n) := \ssshare(\ptxt,\U)

return

S_1 == \bit0^k

When $\A$ is linked to $\lib{ss-real}$ , $S_1$ contains the first $k$ bits of $\ptxt = \bit0^{nk}$ , which are all zeros. So $\A$ returns $\mytrue$ with probability 1 in this case. However, when $\A$ is linked to $\lib{ss-rand}$ , $S_1$ is sampled uniformly from $\bits^k$ , so $\A$ outputs $\mytrue$ only with probability $1/2^k$ .

3.2. 2-out-of-2 secret sharing

The simplest possible flavor of a secret sharing scheme is 2-out-of-2: The secret is split into two shares, both of which are needed to reconstruct the secret. Believe it or not, you've already seen a 2-out-of-2 secret sharing scheme: one-time pad! One share is the key, and the other is the ciphertext. The key alone reveals nothing about the plaintext; the ciphertext alone also reveals nothing about the plaintext. But by combining the two together in the right way, you can learn the plaintext.

Construction 3.2.1 (2-out-of-2 secret sharing based on OTP)

OTP secret sharing is defined by the following:

\begin{aligned} \M &= \bits^\ell \\ \mathcal{S} &= \bits^\ell \end{aligned}

\quad

\Share(\ptxt)

S_1 \gets \bits^\ell

S_2 := S_1 \oplus \ptxt

return

(S_1, S_2)

\quad

// 2-out-of-2 scheme, so both

// shares must be present

\Reconstruct(S_1,S_2)

return

S_1 \oplus S_2

To see why construction 3.2.1 is correct, we can use the usual rules of xor:

\Reconstruct(S_1, S_2) = S_1 \oplus S_2 = S_1 \oplus (S_1 \oplus \ptxt) = \ptxt.

Claim 3.2.2 (Security of OTP secret sharing)

Construction 3.2.1 is a secure 2-out-of-2 secret sharing scheme. In other words,

\lib{ss-real}

\ssshare(\ptxt, \U)

|\U| \ge 2

: return

\myerr

(S_1, S_2) := \Share(\ptxt)

S_1 \gets \bits^\ell

S_2 := S_1 \oplus \ptxt

return

\Filter(\U, S_1, S_2)

\equiv

\lib{ss-rand}

\ssshare(\ptxt, \U)

|\U| \ge 2

: return

\myerr

S_1 \gets \bits^\ell

S_2 \gets \bits^\ell

return

\Filter(\U, S_1, S_2)

Proof:

The only legal choices for $\U$ are:

$\U = \emptyset$ , causing $\ssshare$ to output $(\mynull,\mynull)$ ,
$\U = \{1\}$ , causing $\ssshare$ to output $(S_1,\mynull)$ , and
$\U=\{2\}$ , causing $\ssshare$ to output $(\mynull,S_2)$ .

There is not much to say about the first case, but we need to show that in the other cases, the output share is distributed uniformly. The case of $S_1$ is simple, because $\Share$ literally samples $S_1$ uniformly. The case of $S_2$ is exactly the one-time secrecy of OTP.

The $\lib{ss-*}$ libraries treat all choices of $\U$ in the same manner (this was the purpose of introducing the $\Filter$ function). But, as we just saw, different choices of $\U$ demand different justifications for their security. So the first step of our security proof introduces a hybrid library that handles the different cases of $\U$ in different branches of an if-statement. That way, we can apply different reasoning steps to these different parts of the library's code.

Hybrid Sequence:

[ [ ['111','add','hl'], ['108','add','hl'], ['122','add','hl'], ['29','remove','slide-up'], ['10','add','slide-down'] ], [ ['16','add','hl'], ['16','remove','hidden'], ['17','remove','indent-1'], ['17','add','hl'], ['17','remove','hidden'], ['18','add','hl'], ['18','remove','hidden'], ['6','remove','indent-1'], ['112','add','hl'], ['112','remove','slide-left'], ['20','add','hl'], ['20','remove','hidden'], ['21','add','hl'], ['21','remove','hidden'], ['7','remove','indent-1'], ['8','remove','indent-1'], ['24','add','hl'], ['24','remove','hidden'], ['9','remove','indent-1'], ['109','add','hl'], ['109','remove','slide-left'], ['26','add','hl'], ['26','remove','hidden'], ['27','add','hl'], ['27','remove','hidden'], ['28','add','hl'], ['28','remove','hidden'], ['3','add','hidden'], ['17','add','indent-2'], ['6','add','indent-2'], ['111','remove','hl'], ['111','add','slide-right'], ['7','add','indent-2'], ['8','add','indent-2'], ['9','add','indent-2'], ['108','remove','hl'], ['108','add','slide-right'], ['122','remove','hl'], ['122','add','slide-right'] ], [ ['16','remove','hl'], ['17','remove','hl'], ['18','remove','hl'], ['112','remove','hl'], ['20','remove','hl'], ['21','remove','hl'], ['24','remove','hl'], ['109','remove','hl'], ['26','remove','hl'], ['27','remove','hl'], ['28','remove','hl'], ['18','add','hl'], ['6','add','hl'], ['114','add','hl'], ['24','add','hl'], ['27','add','hl'], ['44','remove','slide-up'], ['29','add','slide-down'] ], [ ['111','add','hl'], ['111','remove','slide-right'], ['18','remove','hl'], ['18','add','hidden'], ['6','remove','hl'], ['6','add','hidden'], ['114','remove','hl'], ['114','add','slide-right'], ['24','remove','hl'], ['24','add','hidden'], ['27','remove','hl'], ['27','add','hidden'] ], [ ['111','remove','hl'], ['7','add','hl'], ['117','add','hl'], ['47','remove','slide-up'], ['44','add','slide-down'] ], [ ['118','add','hl'], ['118','remove','slide-left'], ['119-slide','remove','slide-left'], ['7','remove','hl'], ['7','add','hidden'], ['117','remove','hl'], ['117','add','slide-right'] ], [ ['118','remove','hl'] ], [ ['119-flip','add','flipped'], ['47','add','slide-down'] ], [ ['120','add','hl'], ['122','add','hl'] ], [ ['121','add','hl'], ['121','remove','slide-right'], ['122','add','hl'], ['122','remove','slide-right'], ['120','remove','hl'], ['120','add','slide-left'], ['122','remove','hl'], ['122','add','slide-left'], ['119-slide','add','slide-left'] ], [ ['121','remove','hl'], ['122','remove','hl'], ['16','add','hl'], ['20','add','hl'], ['21','add','hl'], ['109','add','hl'], ['26','add','hl'], ['28','add','hl'], ['98','remove','slide-up'] ], [ ['100','remove','hidden'], ['17','remove','indent-2'], ['114','add','hl'], ['114','remove','slide-right'], ['8','remove','indent-2'], ['9','remove','indent-2'], ['108','add','hl'], ['108','remove','slide-right'], ['122','add','hl'], ['122','remove','slide-left'], ['16','remove','hl'], ['16','add','hidden'], ['17','add','indent-1'], ['20','remove','hl'], ['20','add','hidden'], ['21','remove','hl'], ['21','add','hidden'], ['8','add','indent-1'], ['9','add','indent-1'], ['109','remove','hl'], ['109','add','slide-right'], ['26','remove','hl'], ['26','add','hidden'], ['28','remove','hl'], ['28','add','hidden'] ], [ ['114','remove','hl'], ['108','remove','hl'], ['122','remove','hl'] ] ]

The starting point is

\lib{ss-real}

First, separate the cases for

\U

into different branches of an if-statement. Within each branch, we can inline the behavior of

\Filter(\U,\cdot)

. These changes have no effect on the library's behavior.

S_2

is not used at all in the if-branch, so it can be removed without affecting the library's behavior.

The “else if" branch generates and returns a OTP encryption of

\ptxt

, using

S_1

as the key. We can use the security of OTP to show that the resulting output is uniform. In this three-hop maneuver,

S_1

becomes

\key

from the

\lib{otp-real}

library and

S_2

becomes

\ctxt

The branches of the if-statement can now be unified by writing them in terms of

\Filter

. The result is

\lib{ss-rand}

, which completes the proof.

Lss-real\lib{ss-real}Lss-real​
Lss-rand\lib{ss-rand}Lss-rand​
ss.share\sssharess.share(M,U\ptxt, \UM,U):
if ∣U∣⩾2|\U| \ge 2∣U∣⩾2: return err\myerrerr
if U={1}\U = \{ 1 \}U={1}:
S1↞{0,1}ℓS_1 \gets \bits^\ellS1​↞{0,1}ℓ
S2:=S1⊕MS_2 := S_1 \oplus \ptxtS2​:=S1​⊕M

      // 
          Share(M)\Share(\ptxt)Share(M)
        
          Filter({1},(S1,S2))\Filter\bigl(\{1\}, (S_1,S_2)\bigr)Filter({1},(S1​,S2​)):
        
      return (S1,null)(S_1, \mynull)(S1​,null)
           
else if U={2}\U = \{ 2\}U={2}:
S1↞{0,1}ℓS_1 \gets \bits^\ellS1​↞{0,1}ℓ
S2S_2 S2​:={}:= {}:=
              S1⊕MS_1 \oplus \ptxtS1​⊕M
            
              otp.enc(M)\otpenc(\ptxt)otp.enc(M)
            
          ↞{0,1}ℓ{}\gets \bits^\ell↞{0,1}ℓ
        
// Filter({2},(S1,S2))\Filter\bigl(\{2\}, (S_1,S_2)\bigr)Filter({2},(S1​,S2​)):

      return 
          Filter(U,S1,S2)\Filter(\U, S_1, S_2)Filter(U,S1​,S2​)
        
          (null,S2)(\mynull, S_2)(null,S2​)
        
          Filter(U,S1,S2)\Filter(\U, S_1, S_2)Filter(U,S1​,S2​)
        
else: // U=∅\U = \emptysetU=∅
// Filter(∅,(S1,S2))\Filter\bigl(\emptyset, (S_1,S_2)\bigr)Filter(∅,(S1​,S2​)):
return (null,null)(\mynull, \mynull)(null,null)

\link

\lib{otp-real}

\otpenc

(

\ptxt

\key \gets \bits^\ell

\ctxt := \key \oplus \ptxt

return

\ctxt

\lib{otp-rand}

\otpenc

(

\ptxt

\ctxt \gets \bits^\ell

return

\ctxt

3.3. Polynomial interpolation

You are probably familiar with the fact that two points determine a line. It is also true that three points determine a parabola, and so on. The final secret-sharing scheme in this chapter is based on the following principle:

$d+1$ points determine a unique degree- $d$ polynomial.

Notation & Terminology

In this section, if $F$ is a polynomial that can be written as:

F(X) = c_d X^d + c_{d-1} X^{d-1} + \cdots + c_0,

then we will describe $F$ as degree- $d$ . It would be more accurate to describe $F$ as a polynomial of degree at most $d$ , since the leading coefficient could be zero.

Throughout this section, we will use capital $X$ to denote the formal variable of a polynomial, and lowercase $x_i$ 's to denote specific values/scalars.

The process of finding the polynomial that passes through a given set of points is called interpolation.

Theorem 3.3.1 (Polynomial interpolation)

Let $\{ (x_1, y_1), \ldots, (x_{d+1}, y_{d+1})\} \subseteq \mathbb{R}^2$ be a set of points whose $x_i$ values are all distinct. Then there is a unique degree- $d$ polynomial $F(X)$ with real coefficients that satisfies $y_i = F(x_i)$ for all $i$ .

Proof:

As a warm-up, consider the following polynomial:

A(X) = (X-x_2)( X - x_3) \cdots (X - x_{d+1}).

This is the product of $d$ terms, so it has degree $d$ . Additionally:

On input $x_1$ , we get $A(x_1) = (x_1 - x_2)(x_1 - x_3) \cdots (x_1 - x_{d+1})$ , which is nonzero because all of the $x_i$ values are distinct.
On input $x_i$ for $i\ne 1$ , $A(x_i)$ includes a term $(x_i - x_i) = 0$ , so the output is zero.

Of course $A(X)$ can be evaluated at any point, but we care only about its behavior on these special points.

Suppose we divide $A(X)$ by the fixed, nonzero value $A(x_1)$ :

\displaystyle L_1(X) = \frac{ (X-x_2)( X - x_3) \cdots (X - x_{d+1}) } { (x_1 - x_2)( x_1 - x_3) \cdots (x_1 - x_{d+1}) } .

The result is another degree- $d$ polynomial that satisfies:

L_1(x_i) = \begin{cases} 1 & \text{ if } i=1 \\ 0 & \text{ if } i\ne1 . \end{cases}

In the same way, we can define other polynomials $L_j$ :

\displaystyle L_j(X) = \frac{ (X-x_1) \cdots (X - x_{j-1}) (X - x_{j+1}) \cdots (X - x_{d+1}) } { (x_j-x_1) \cdots (x_j - x_{j-1}) (x_j - x_{j+1}) \cdots (x_j - x_{d+1}) } .

The pattern is that the numerator is “missing” the term $(X - x_j)$ and the denominator is missing the term $(x_j - x_j)$ , to avoid dividing by zero. Polynomials of this kind are called Lagrange polynomials. They are all degree- $d$ , and they satisfy the property:

L_j(x_i) = \begin{cases} 1 & \text{ if } i=j \\ 0 & \text{ if } i\ne j. \end{cases}

Now consider the following polynomial:

F(X) = y_1 L_1(X) + y_2 L_2(X) + \cdots + y_{d+1} L_{d+1}(X).

This $F(X)$ is degree- $d$ since it is the sum of degree- $d$ polynomials (the $y_i$ values are just scalars). Evaluating $F(X)$ on one of the special $x_i$ values results in:

\begin{aligned} F(x_i) &= y_1 L_1(x_i) + \cdots + y_i L_i(x_i) + \cdots + y_{d+1} L_{d+1}(x_i) \\ &= y_1 \cdot 0 + \cdots + y_i \cdot 1 + \cdots + y_{d+1} \cdot 0 \\ &= y_i.\end{aligned}

So $F(x_i) = y_i$ for every $x_i$ ; in other words, $F(X)$ interpolates the given points.

Next, we show that $F$ is unique. Suppose some other polynomial $F'$ also interpolates the given points: $F(x_i) = F'(x_i) = y_i$ for all $i \in \{1,\ldots, d+1\}$ . Then the polynomial $G(X) = F(X)-F'(X)$ also is degree- $d$ , and it satisfies $G(x_i) = 0$ for all $i$ . In other words, $G(X)$ has (at least) $d+1$ roots. But the only degree- $d$ polynomial with $d+1$ roots is the identically-zero polynomial $G(X) = 0$ . If $G(X)=0$ then $F = F'$ ; thus, $F$ is unique.

Example 3.3.2 (Polynomial interpolation)

What is the degree-3 polynomial that passes through the points $(3,1)$ , $(4,1)$ , $(5,9)$ , and $(2,6)$ ?

$i$	1	2	3	4
$x_i$	3	4	5	2
$y_i$	1	1	9	6

First, let's construct the appropriate Lagrange polynomials:

\begin{aligned} L_1(X) & = \frac{(X - 4)(X - 5)(X - 2)} {(3 - 4)(3 - 5)(3 - 2)} = \frac{X^3 - 11 X^2 + 38 X - 40} {2} \\[4pt] L_2(X) & = \frac{(X - 3)(X - 5)(X - 2)} {(4 - 3)(4 - 5)(4 - 2)} = \frac{X^3 - 10 X^2 + 31 X - 30} {-2} \\[4pt] L_3(X) & = \frac{(X - 3)(X - 4)(X - 2)} {(5 - 3)(5 - 4)(5 - 2)} = \frac{X^3 - 9 X^2 + 26 X - 24} {6} \\[4pt] L_4(X) & = \frac{(X - 3)(X - 4)(X - 5)} {(2 - 3)(2 - 4)(2 - 5)} = \frac{X^3 - 12 X^2 + 47 X - 60} {-6}\end{aligned}

Check for yourself that $L_j(x_i) = 1$ if and only if $i=j$ . The next step is easier if we rewrite all Lagrange polynomials to have the same denominator 6:

\begin{aligned} L_1(X) &= \frac{3 X^3 - 33 X^2 + 114 X - 120} {6} ; & L_3(X) &= \frac{X^3 - 9 X^2 + 26 X - 24} {6}; \\ L_2(X) &= \frac{-3X^3 + 30 X^2 - 93 X + 90} {6}; & L_4(X) &= \frac{-X^3 + 12 X^2 - 47 X + 60} {6}.\end{aligned}

Our desired polynomial is

\begin{aligned} F(X) &= y_1 \cdot L_1(X) + y_2 \cdot L_2(X) + y_3 \cdot L_3(X) + y_4 \cdot L_4(X) \\ &= 1\cdot L_1(X) + 1\cdot L_2(X) + 9 \cdot L_3(X) + 6 \cdot L_4(X)\\ &= \frac 16 \left( \begin{array}{rrrr} 1\cdot\big( \phantom{{}-{}} 3 X^3 & {} - 33 X^2 & {} + 114X & {} -120 \big) \\ {}+ 1 \cdot\big( -3 X^3 & {} + 30 X^2 & {} - 93X & {} +90 \big) \\ {}+ 9 \cdot\big( \phantom{{}-3} X^3 &{} -9X^2 & {} + 26X & {} -24 \big) \\ {}+6 \cdot\big( \phantom{3} -X^3 & {} + 12X^2 & {} -47X & {} + 60 \big) \end{array} \right) \\ &= \frac16 \Bigl( 3 X^3 - 12 X^2 - 27 X + 114 \Bigr)\\[4pt] &= \frac12 \Bigl( X^3 - 4X^2 - 9X + 38 \Bigr).\end{aligned}

We can double-check that $F$ gives the correct values:

\begin{aligned} F(x_1) & = F(\hl{3}) = \frac12 ( \hl{3}^3 - 4 \cdot \hl{3}^2 - 9 \cdot \hl{3} + 38 ) = 1 = y_1, \\ F(x_2) & = F(\hl{4}) = \frac12 ( \hl{4}^3 - 4 \cdot \hl{4}^2 - 9 \cdot \hl{4} + 38 ) = 1 = y_2, \\ F(x_3) & = F(\hl{5}) = \frac12 ( \hl{5}^3 - 4 \cdot \hl{5}^2 - 9 \cdot \hl{5} + 38 ) = 9 = y_3, \\ F(x_4) & = F(\hl{2}) = \frac12 ( \hl{2}^3 - 4 \cdot \hl{2}^2 - 9 \cdot \hl{2} + 38 ) = 6 = y_4.\end{aligned}

3.4. Multiplicative inverses modulo a prime

Addition, subtraction, and multiplication are simple operations mod $\nmod$ . Just perform the operation over the integers and reduce the result mod $\nmod$ . In this way, we can define operations on $\Z_\nmod$ whose results are always in $\Z_\nmod$ . This section is about how to make sense of division mod $\nmod$ . How can we divide two numbers in $\Z_\nmod$ to obtain a result also in $\Z_\nmod$ ?

It is helpful to rethink what an expression like “1/2” means in the first place. The best way to define “1/2” is the solution to the equation $2x=1$ . Try to convince yourself that any time you divide by two, what you are really doing is multiplying by the value $x$ that satisfies $2x=1$ .

Even though there is no solution to $2x=1$ in the integers, there could be a solution mod $\nmod$ . If $x \in \Z_\nmod$ satisfies $2x \equiv_\nmod 1$ , then it is reasonable for us call $x$ “1/2.”

Example 3.4.1 (“1/2” under different moduli)

6 is a solution to $2 x \equiv_{11} 1$ . Thus, “1/2” in $\Z_{11}$ is 6.
8 is a solution to $2 x \equiv_{15} 1$ . Thus, “1/2” in $\Z_{15}$ is 8.
There is no solution to $2 x \equiv_{10} 1$ . If $x$ is an integer, then $2x$ is even, and its remainder mod 10 is also even, and thus cannot equal 1. So “1/2” does not exist in $\Z_{10}$ .

More generally, dividing by $b$ is just multiplying by the $x$ that satisfies $xb = 1$ . This special value $x$ is called the multiplicative inverse of $b$ .

Definition 3.4.2 (Multiplicative inverse)

$x$ is a multiplicative inverse of $b$ mod $\nmod$ if $xb \equiv_\nmod 1$ . When this is the case, we often write $x \equiv_\nmod \hl{b^{-1}}$ .

Example 3.4.3 (Multiplicative inverses)

6 is an inverse of 2 mod 11, since $6 \cdot 2 \equiv_{11} 1$ .
3 is an inverse of 7 mod 10, since $3 \cdot 7 \equiv_{10} 1$ .
4 is its own inverse mod 15, since $4 \cdot 4 \equiv_{15} 1$ .

3.4.1. Computing inverses

You might be disappointed if you write (1/2) % 11 (sometimes the operator is named mod) in your favorite programming language—the result might be 0.5. Your program divided 1/2 to get a real number (floating point) 0.5, then divided 0.5 by 11 and computed the remainder, which of course was 0.5.

We can always add, subtract, or multiply mod $\nmod$ by first performing the operation over the integers and then reducing the result mod $\nmod$ . This works because adding, subtracting, or multiplying integers always gives an integer result, But division of integers doesn't always result in an integer, so division mod $\nmod$ is not equivalent in general to dividing over the integers and reducing the result mod $\nmod$ .

So how can you actually compute inverses mod $\nmod$ ? We discuss the algorithms behind modular inverses in more detail in chapter 15, but for now you can simply use a good numerical library. Numerical examples in this book will use SageMath (sagemath.org), an open-source system that uses Python syntax. Sage's built-in % operator is smart enough to do what we want:

sage: (1/2) % 11 6

Beware that Sage treats expressions like 1/2 and 0.5 differently:

sage: 0.5 % 11 0.500000000000000

Sage stores 1/2 as a rational number with exact precision (it stores the numerator and denominator separately as integers), instead of converting it to a floating point number. It can therefore interpret $(a/b) \pct \nmod$ as $a b^{-1} \pct \nmod$ .

If you want to be even more explicit, you can define a Mod object, which “knows” that it lives in $\Z_\nmod$ and overloads its arithmetic operations to be the mod- $\nmod$ operations:

sage: x = Mod(2,11) sage: 1/x 6 sage: x + 100 3

A Mod object can be converted back into an integer with the lift method:

sage: x.lift() + 100 102

3.4.2. Prime moduli

We have seen examples where multiplicative inverses exist and other examples where they don't. If you want to know the rule that characterizes exactly when $b$ has a multiplicative inverse mod $\nmod$ , take a look at chapter 15. For this chapter, we only need to understand the case where the modulus is prime.

Claim 3.4.4 (Multiplicative inverses modulo a prime)

When $\nmod$ is a prime, every $b \in \{1, \ldots, \nmod-1\}$ has a multiplicative inverse mod $\nmod$ .

This algebraic property is one reason prime numbers are useful in cryptography.

Proof:

For the sake of contradiction, suppose that none of the integers $b, 2b, 3b, \ldots$ are congruent to 1 mod $\nmod$ . Reduce that sequence mod $\nmod$ to obtain:

b \pct p, \quad (2a) \pct p,\quad (3a) \pct \nmod,\quad \ldots

Each item in the sequence is an integer in the range $\{0, \ldots, \nmod-1\}$ , and we have assumed that no term is equal to 1. With only $\nmod-1$ values possible in this sequence, there must be a repeat within the first $\nmod$ terms:

(i \cdot b) \pct \nmod = (j \cdot b) \pct \nmod, \text{ for some distinct $i,j \in \{1, \ldots, \nmod\}$.}

Equivalently,

i \cdot b \equiv_\nmod j\cdot b \implies |i-j|\cdot b \equiv_\nmod 0 \implies\nmod \text{ divides } |i-j| \cdot b.

An important fact about primes is the following:

Fact 3.4.5 (Prime divisors)

If $\nmod$ is a prime, and $u$ and $v$ are integers such that $\nmod \mid uv$ , then $\nmod \mid u$ or $\nmod \mid v$ (or both).

From this fact, we can conclude that $\nmod$ divides either $|i-j|$ or $b$ . But both $|i-j|$ and $b$ are positive, and strictly less than $\nmod$ . ( $|i-j|$ is the difference of distinct elements of $\{1, \ldots, \nmod\}$ .) This gives us the desired contradiction: $\nmod$ cannot divide a positive number smaller than itself.

Interpolation: In the previous section we proved that $d+1$ points determine a unique degree- $d$ polynomial. More precisely, we proved the statement with respect to the real numbers. It is also true working modulo a prime:

Theorem 3.4.6 (Polynomial interpolation modulo a prime)

Let $\nmod$ be a prime, and let $\{ (x_1, y_1), \ldots, (x_{d+1}, y_{d+1})\} \subseteq {} \hl{(\Z_\nmod)}^2$ be a set of points whose $x_i$ values are all distinct. Then there is a unique degree- $d$ polynomial $F(X)$ with coefficients in $\Z_\nmod$ that satisfies $y_i \hl{\equiv_\nmod} F(x_i)$ for all $i$ .

Proof:

The proof is essentially the same as that of theorem 3.3.1. In that proof we defined the Lagrange polynomials as:

\displaystyle L_j(X) = \frac{ (X-x_1) \cdots (X - x_{j-1}) (X - x_{j+1}) \cdots (X - x_{d+1}) } { (x_j-x_1) \cdots (x_j - x_{j-1}) (x_j - x_{j+1}) \cdots (x_j - x_{d+1}) } .

These expressions are valid modulo a prime; to be completely precise, you can imagine multiplying the numerator by the inverse of the denominator.

To prove that a unique polynomial interpolates the given points, we used the fact that the only degree- $d$ polynomial with more than $d$ roots is the identically zero polynomial. This fact is also true in $\Z_\nmod$ when $\nmod$ is prime, but we do not prove it here.

Example 3.4.7 (Polynomial interpolation modulo a prime)

Suppose we are interested in the polynomial that interpolates the points from the previous section's example, but this time in $\Z_{11}$ :

$i$	1	2	3	4
$x_i$	3	4	5	2
$y_i$	1	1	9	6

We previously computed the example over the real numbers as:

\displaystyle F(X) = \frac12 ( X^3 - 4X^2 - 9 X + 38 ).

To get the answer in $\Z_{11}$ (i.e., a polynomial with coefficients in $\Z_{11}$ ), just replace “division by 2” with “multiplication by 2's inverse mod 11,” which in this case is 6.

\begin{aligned} \displaystyle F(X) &= \frac12 ( X^3 - 4X^2 - 9 X + 38 ) \\ &\equiv_{11} 6 ( X^3 - 4X^2 - 9 X + 38 ) \\ &\equiv_{11} 6 X^3 - 2 X^2 - 10 X + 8.\end{aligned}

(If you like, you could also replace negative coefficients with positive ones by reducing mod 11, obtaining $F(X) = 6X^3 + 9X^2 + X + 8$ .) We can double-check that $F$ gives the correct values:

\begin{aligned} F(x_1) & = F(\hl{3}) = 6 \cdot \hl{3}^3 - 2 \cdot \hl{3}^2 - 10 \cdot \hl{3} + 8 = 122 \equiv_{11} 1 = y_1, \\ F(x_2) & = F(\hl{4}) = 6 \cdot \hl{4}^3 - 2 \cdot \hl{4}^2 - 10 \cdot \hl{4} + 8 = 320 \equiv_{11} 1 = y_2, \\ F(x_3) & = F(\hl{5}) = 6 \cdot \hl{5}^3 - 2 \cdot \hl{5}^2 - 10 \cdot \hl{5} + 8 = 658 \equiv_{11} 9 = y_3, \\ F(x_4) & = F(\hl{2}) = 6 \cdot \hl{2}^3 - 2 \cdot \hl{2}^2 - 10 \cdot \hl{2} + 8 = 28\phantom{0} \equiv_{11} 6 = y_4.\end{aligned}

Example 3.4.8 (Polynomial interpolation in Sage)

To solve this example in Sage, you can do the following:

sage: R = PolynomialRing(Zmod(11), 'X') sage: R.lagrange_polynomial([ (3,1), (4,1), (5,9), (2,6) ]) 6*X^3 + 9*X^2 + X + 8

The first line establishes R as the set of polynomials with coefficients in $\Z_{11}$ , with formal variable X.

If you want to interpolate over the real numbers or rationals—and remember, it makes a difference in Sage—you can use RR or QQ in place of Zmod(11):

sage: R = PolynomialRing(RR, 'X') sage: R.lagrange_polynomial([ (3,1), (4,1), (5,9), (2,6) ]) 0.500000000000000*X^3 - 2.00000000000000*X^2 - 4.50000000000000*X + 19.0000000000000 sage: R = PolynomialRing(QQ, 'X') sage: R.lagrange_polynomial([ (3,1), (4,1), (5,9), (2,6) ]) 1/2*X^3 - 2*X^2 - 9/2*X + 19

3.5. Shamir secret sharing

This section introduces Shamir's secret sharing scheme, a $t$ -out-of- $n$ secret sharing scheme that cleverly uses polynomial interpolation. The idea is that the shares are points that all lie on the same degree- $(t-1)$ polynomial $Q(X)$ . We have seen that any $t$ such points uniquely determine $Q(X)$ . The secret is just another special point on the polynomial, usually $Q(0)$ .

To share a secret $\ptxt$ , the dealer must choose a polynomial $Q(X)$ of degree $t-1$ satisfying $Q(0)=\ptxt$ . It does this by fixing $Q$ 's constant coefficient to be $\ptxt$ and choosing the $t-1$ other coefficients uniformly at random from $\Z_\pmod$ , where $\pmod$ is a prime. Then the $n$ shares are $Q(1), \ldots, Q(n)$ , with all operations taken mod $\pmod$ .

Construction 3.5.1 (Shamir secret sharing)

Let $\pmod$ be a prime and let $t$ and $n$ be integers with $t \le n < \pmod$ . Then Shamir secret sharing consists of the following algorithms and parameters $\M = \mathcal{S} = \Z_\pmod$ :

            Share(M)\Share(\ptxt)Share(M):
          
// uniformly chosen degree-(t−1)(t-1)(t−1) 
// polynomial with Q(0)=MQ(0) = \ptxtQ(0)=M
q0:=Mq_0 := \ptxtq0​:=M
for i=1i = 1i=1 to t−1t-1t−1:
qi↞Zpq_i \gets \Z_\pmodqi​↞Zp​
Q(X):=qt−1Xt−1+⋯+q0Q(X) := q_{t-1} X^{t-1} +  \cdots + q_0Q(X):=qt−1​Xt−1+⋯+q0​
for i=1i = 1i=1 to nnn:
Si:=Q(i)%pS_i := Q(i) \pct \pmodSi​:=Q(i)%p
return (S1,…,Sn)(S_1, \ldots, S_n)(S1​,…,Sn​)

// expect

t

of the

S_i

's to be non-

\mynull

\Reconstruct(S_1, \ldots, S_n)

for

i=1

n

S_i \ne \mynull

\mathcal{I} := \mathcal{I} \cup \{ (i, S_i) \}

\mathcal{I}

= points on which to interpolate

\begin{aligned}Q(X) := {} & \text{unique degree-}(t-1) \\[-3pt] & \text{polynomial interpolating} \\[-3pt] & \text{points in } \mathcal{I}\end{aligned}

return

Q(0) \pct \pmod

The restriction $n < \pmod$ comes from the fact that the shares are $Q(1), \ldots, Q(n)$ and the secret is $Q(0)$ , so the numbers $\{0, \ldots, n\}$ must be distinct mod $\pmod$ .

Example 3.5.2 (Shamir secret sharing)

Here is an example of 4-out-of-7 Shamir sharing over $\Z_{11}$ . Suppose the secret is $\ptxt = 8$ , then the $\Share$ algorithm will define a polynomial $Q(X)$ by sampling $t-1 = 3$ coefficients $q_1, q_2, q_3$ and fixing coefficient $q_0 = \ptxt = 8$ . Suppose the results are

q_1 = 1, \qquad q_2 = 9, \qquad q_3 = 6,

and so the secret polynomial is $Q(X) = 6 X^3 + 9 X^2 + X + 8$ . The 7 shares are:

\begin{aligned} Q(1) &= 6 \cdot \hl{1}^3 + 9 \cdot \hl{1}^2 + \hl{1} + 8 \equiv_{11} 3, & Q(5) &= 6 \cdot \hl{5}^3 + 9 \cdot \hl{5}^2 + \hl{5} + 8 \equiv_{11} 9, \\ Q(2) &= 6 \cdot \hl{2}^3 + 9 \cdot \hl{2}^2 + \hl{2} + 8 \equiv_{11} 6, & Q(6) &= 6 \cdot \hl{6}^3 + 9 \cdot \hl{6}^2 + \hl{6} + 8 \equiv_{11} 6, \\ Q(3) &= 6 \cdot \hl{3}^3 + 9 \cdot \hl{3}^2 + \hl{3} + 8 \equiv_{11} 1, & Q(7) &= 6 \cdot \hl{7}^3 + 9 \cdot \hl{7}^2 + \hl{7} + 8 \equiv_{11} 6, \\ Q(4) &= 6 \cdot \hl{4}^3 + 9 \cdot \hl{4}^2 + \hl{4} + 8 \equiv_{11} 1.\end{aligned}

Any four of these shares can be combined to reconstruct the secret. Suppose users 2, 3, 4, and 5 combine their shares $Q(2), Q(3), Q(4), Q(5)$ . They use polynomial interpolation to recover $Q(X)$ — in this case, their computation is precisely what is described in example 3.4.7. Upon recovering $Q(X)$ , they evaluate it at zero to obtain the secret $q_0 = 8$ .

Next, we turn our attention to the security of Shamir secret sharing. We must show that if you see less than $t$ shares, then those shares look like random junk.

Claim 3.5.3 (Security of Shamir secret sharing)

Shamir secret sharing (construction 3.5.1) is a secure secret sharing scheme. That is, the following libraries are interchangeable:

\lib{ss-real}

\ssshare(\ptxt, \U)

|\U| \ge t

: return

\myerr

(S_1, \ldots, S_n) := \Share(\ptxt)

q_0 := \ptxt

for

i = 1

t-1

q_i \gets \Z_\pmod

Q(X) := q_{t-1} X^{t-1} + \cdots + q_0

for

i = 1

n

S_i := Q(i) \pct \pmod

return

\Filter(\U, S_1, \ldots, S_n)

\equiv

\lib{ss-rand}

\ssshare(\ptxt, \U)

|\U| \ge t

: return

\myerr

for

i=1

n

S_i \gets \Z_\pmod

return

\Filter(\U, S_1, \ldots, S_n)

Proof:

Rather than showing a sequence of hybrids, for this proof we will reason directly about output probabilities, similar to our security proof for OTP in chapter 1. The output of $\ssshare(\ptxt,\U)$ is a list containing $\Z_\pmod$ -elements in the positions given by $\U$ and $\mynull$ everywhere else (assuming $|\U| < t$ ). Thus, there are $\pmod^{|\U|}$ outputs possible for a specific choice of $\U$ , and our goal is to show that the output of $\ssshare$ is uniformly distributed among these possibilities.

We will consider only the case where $|\U| = t-1$ ; exercise 3.1 asks you to show that this special case implies security in general. We will show that for any $\ptxt \in \Z_\pmod$ and any $|\U| = t-1$ , the output of $\ssshare(\ptxt,\U)$ is uniformly distributed, among the $\pmod^{t-1}$ possibilities that are consistent with this choice of $\U$ .

Fix a particular $\ptxt \in \Z_\pmod$ and $\U \subseteq \{1,\ldots, n\}$ with $|\U| = t-1$ , and a particular list $(S_1, \ldots, S_n)$ that consists of $\Z_\pmod$ -elements in the positions given in $\U$ and contains $\mynull$ everywhere else. It suffices to prove that:

\PR{ \ssshare(\ptxt,\U) = (S_1, \ldots, S_n) } = 1/\pmod^{t-1}.

This event happens only when $\Share$ chooses a polynomial $Q(X)$ such that $Q(i) \equiv_\pmod S_i$ for all $i \in \U$ . Additionally, $\Share$ always chooses a polynomial satisfying $Q(0) \equiv_\pmod \ptxt$ . But there is only one $Q(X)$ of degree $t-1$ that interpolates these $t$ specific values. So the probability that $\ssshare(\ptxt,\U) = (S_1, \ldots, S_n)$ is exactly the probability that $\Share$ chooses this one particular polynomial $Q(X)$ . But $\Share$ chooses each coefficient $q_1, \ldots, q_{t-1}$ uniformly from $\Z_\pmod$ , and they will match the coefficients of this particular $Q(X)$ with probability $1/\pmod^{t-1}$ . Thus, the output of $\ssshare$ is uniformly distributed.

Exercises

The libraries in definition 3.1.2 require the adversary to choose $\U$ with $|\U| < t$ . When this is not the case, they return an error.

Prove that it suffices to restrict the adversary to $\U$ with $|\U| = t-1$ . In other words, if $\Sigma$ is a secret sharing scheme for which the following libraries are interchangeable, then $\Sigma$ is also secure according to definition 3.1.2.

$\ssshare(\ptxt, \U)$ :

if $|\U| \ne t-1$ : return $\myerr$

$(S_1, \ldots, S_n) := \Sigma.\Share(\ptxt)$

return $\Filter(\U, S_1, \ldots, S_n)$

$\equiv$

$\ssshare(\ptxt, \U)$ :

if $|\U| \ne t-1$ : return $\myerr$

for $i=1$ to $n$ :

$S_i \gets \Sigma.\mathcal{S}$

return $\Filter(\U, S_1, \ldots, S_n)$

$,$
There are three major divisions at PizzaCorp: the crust division, the sauce division, and the cheese division. Each division has an executive board consisting of five people. The CEO of PizzaCorp would like to divide the secret family recipe among the executives so that they can recover it only if a majority of executives from each division cooperate. If any division does not have a majority of executives present, then nobody should learn anything about the secret recipe.

Assuming that the CEO is aware of $t$ -out-of- $n$ secret sharing schemes, describe clearly how they can distribute values to the executives to achieve the desired outcome, and describe how the executives will recover the secret. You should give some informal reasoning about the security of your proposal, but the CEO of PizzaCorp is not interested in hearing a formal security proof.
Propose a security definition for secret sharing, using the left-or-right paradigm (section 2.7). Formally prove that if a secret sharing scheme satisfies the real-or-random definition (definition 3.1.2), then it also satisfies your definition.
Suppose a $t$ -out-of- $n$ secret sharing scheme has message space $\M$ and share space $\mathcal{S}$ . Prove that if the scheme is secure, then $|\M| \le |\mathcal{S}|$ . Use exercise 2.14 as inspiration.
Generalize construction 3.2.1 to the $n$ -out-of- $n$ case. Propose an $n$ -out-of- $n$ secret sharing scheme and prove that it is secure.
Let $\Sigma_3$ be a 3-out-of-3 secret sharing scheme, and $\Sigma_2$ be a 2-out-of-2 secret sharing scheme that is capable of sharing shares from $\Sigma_3$ (i.e., $\Sigma_3.\mathcal{S} \subseteq \Sigma_2.\M$ ). In this exercise we consider the following 2-out-of-3 scheme $\Sigma^*$ :

$\Sigma^*.\Share(\ptxt)$ :

$(S_1, S_2, S_3) := \Sigma_3.\Share(\ptxt)$

$(T_{1\to2}, T_{1\to3}) := \Sigma_2.\Share(S_1)$

$(T_{2\to1}, T_{2\to3}) := \Sigma_2.\Share(S_2)$

$(T_{3\to1}, T_{3\to2}) := \Sigma_2.\Share(S_3)$

$S^*_1 := (S_1, T_{2\to1}, T_{3\to1})$

$S^*_2 := (S_2, T_{1\to2}, T_{3\to2})$

$S^*_3 := (S_3, T_{1\to3}, T_{2\to3})$

return $(S^*_1, S^*_2, S^*_3)$
1. Describe the corresponding $\Sigma^*.\Reconstruct$ algorithm.
2. Prove that $\Sigma^*$ is a secure 2-out-of-3 secret sharing scheme.
Let $\Sigma_{\text{ss}}$ be a 2-out-of-2 secret sharing scheme, and let $\Sigma_{\text{ske-1}}$ and $\Sigma_{\text{ske-2}}$ be encryption schemes with plaintext spaces $\Sigma_{\text{ske-1}}.\M = \Sigma_{\text{ske-2}}.\M = \Sigma_{\text{ss}}.\mathcal{S}$ ; in other words, $\Sigma_{\text{ske-1}}$ and $\Sigma_{\text{ske-2}}$ can encrypt shares from $\Sigma_{\text{ss}}$ . Define the following new encryption scheme $\Sigma^*$ :

$\begin{aligned}\K &= \Sigma_{\text{ske-1}}.\K \times \Sigma_{\text{ske-2}}.\K \\ \M &= \Sigma_{\text{ss}}.\M \\ \C &= \Sigma_{\text{ske-1}}.\C \times \Sigma_{\text{ske-2}}.\C\end{aligned}$

$\Enc\bigl( (\key_1,\key_2), \ptxt \bigr)$ :

$(S_1, S_2) := \Sigma_{\text{ss}}.\Share(\ptxt)$

$\ctxt_1 := \Sigma_{\text{ske-1}}.\Enc(\key_1, S_1)$

$\ctxt_2 := \Sigma_{\text{ske-2}}.\Enc(\key_2, S_2)$

return $(\ctxt_1, \ctxt_2)$

$\quad$

$\Dec\bigl( (\key_1,\key_2), (\ctxt_1, \ctxt_2) \bigr)$ :

$S_1 := \Sigma_{\text{ske-1}}.\Dec(\key_1, \ctxt_1)$

$S_2 := \Sigma_{\text{ske-2}}.\Dec(\key_2, \ctxt_2)$

$\ptxt := \Sigma_{\text{ss}}.\Reconstruct(S_1, S_2)$

return $\ptxt$
1. Prove that $\Sigma^*$ has left-or-right one-time secrecy (definition 2.7.1) if $\Sigma_{\text{ss}}$ is a secure secret sharing scheme, and either of $\Sigma_{\text{ske-1}}, \Sigma_{\text{ske-2}}$ has left-or-right one-time secrecy. Your proof should involve two cases: In the first case, assume that $\Sigma_{\text{ske-1}}$ is secure, but assume nothing about $\Sigma_{\text{ske-2}}$ . Then repeat, swapping the roles of $\Sigma_{\text{ske-1}}$ and $\Sigma_{\text{ske-2}}$ .
2. Why do you suppose this question asks about left-or-right security rather than real-or-random?
Generalize the previous exercise to the $t$ -out-of- $n$ case. Given $n$ different encryption schemes, describe how to construct a new encryption scheme that has (left-or-right) one-time secrecy if any $t$ of the underlying schemes do. Prove security of your construction. Be careful about choosing the threshold for any secret sharing scheme you use.
It is not necessary to compute the entire polynomial during the reconstruction phase of Shamir secret sharing. All that is needed is the value $Q(0)$ . Given $x_1, \ldots, x_t$ , all distinct and all nonzero, show how to construct coefficients $c_1, \ldots, c_t$ such that

$Q(0) = c_1 Q(x_1) + c_2 Q(x_2) + \cdots + c_t Q(x_t),$

for all degree- $(t-1)$ polynomials $Q$ . To be clear, the $c_i$ coefficients depend only on the $x_i$ 's but not on $Q$ .
We didn't prove that multiplicative inverses are unique mod $\nmod$ . Prove the following: If $x$ and $x'$ are both multiplicative inverses of $b$ mod $\nmod$ , then $x \equiv_\nmod x'$ .
Prove that if $\nmod$ is composite, then there is some integer $b \in \{1, \ldots, \nmod-1\}$ that does not have a multiplicative inverse mod $\nmod$ .
Give an example of a nonzero, degree- $d$ polynomial over $\Z_\nmod$ that has more than $d$ roots. Of course, $\nmod$ cannot be prime.
Let $\nmod$ be a prime and consider the following variant of OTP:

$\K = \M = \C = \{1, \ldots, \nmod-1\}$

$\quad$

$\Enc(\key,\ptxt)$ :

$\ctxt := \key \cdot \ptxt \pct \nmod$

return $\ctxt$
1. Give the corresponding $\Dec$ algorithm and show that it is correct.
2. Prove that the scheme has one-time secrecy.
Below are parameters for Shamir's secret sharing scheme along with a set of shares. What is the secret, and what are the missing shares?

$\begin{aligned} n &= 10, \\ t &= 4, \\ \pmod &= 16261100728086947379516237825246528373, \\ S_3 &= 3256621440428047006295920894879234328, \\ S_5 &= 14962107319351742694230294996446466335, \\ S_6 &= 12284280758146456039859693602767230420, \\ S_9 &= 2618242661644870291239011221231862685.\end{aligned}$
h Suppose $n$ users hold secret shares of $\ptxt$ and $\ptxt'$ , generated by Shamir's scheme with the same threshold $t$ and same prime $\pmod$ . Each user holds a share of $\ptxt$ and a share of $\ptxt'$ . Prove that if each user locally adds their shares (mod $\pmod$ ), the result is a valid sharing of $\ptxt + \ptxt' \pct \pmod$ . In other words, prove that the following procedure always outputs $\ptxt + \ptxt' \pct \pmod$ :

$(S_1, \ldots, S_n) := \Share(\ptxt)$

$(S'_1, \ldots, S'_n) := \Share(\ptxt')$

for $i=1$ to $n$ :

$S^*_i := (S_i + S'_i) \pct \pmod$

output $\Reconstruct(S^*_1, \ldots, S^*_n)$

What polynomial do the new shares lie on?
Implement the algorithms of Shamir secret sharing in Sage.
h Secret sharing schemes must satisfy two properties: (1) any collection of $t$ shares is enough to reconstruct the secret; (2) any collection of $t-1$ shares reveals no information about the secret. Suppose we are interested only in condition (1) and not (2). Describe a way to split an $\ell$ -bit secret into $n$ “shares” of length roughly $\ell/t$ (not $\ell$ ), so that the secret can be reconstructed from any collection of $t$ shares. Unlike in secret sharing, these “shares” are now allowed to leak information about the “secret.” As such, there is no security property to prove.

Instead of encoding the target value as $Q(0)$ , encode it as the entire polynomial $Q$ .

Chapter Notes

Secret sharing was proposed independently by Shamir [200] and by Blakley [47]. The scheme from [200] is the ubiquitous one still known as Shamir's scheme.

When you must choose from several reasonable choices for a cryptographic algorithm, you may live in fear that your chosen algorithm is broken. A combiner is a way to combine several cryptographic algorithms into a single algorithm that is secure if at least one of its components is secure, even if all the others are broken. Exercise 3.7 describes a simple combiner for one-time secrecy. Several other exercises throughout the book explore combiners for other primitives. Cryptographic combiners were first explicitly studied by Herzberg [121], who called them “tolerant” constructions. The term “combiner” is due to Harnik, Kilian, Naor, Reingold, and Rosen [120].

The problem in exercise 3.17 is called information dispersal, and was introduced by Rabin [186].

☆ Secret Sharing

Chapter Contents

3.1. Defining secret sharing

3.2. 2-out-of-2 secret sharing

3.3. Polynomial interpolation

3.4. Multiplicative inverses modulo a prime

3.4.1. Computing inverses

3.4.2. Prime moduli

3.5. Shamir secret sharing

Exercises

Chapter Notes