# Exercises

3.1: Generalize Construction 3.2.1 to be an n-out-of-n secret-sharing scheme, and prove that your scheme is correct and secure.

3.2: Prove Theorem 3.2.2.

3.3: Fill in the details of the following alternative proof of Theorem 3.2.1: Starting with $$\mathscr{L}_{\text{tsss-L}}$$, apply the first step of the proof as before, to duplicate the main body into 3 branches of a new if-statement. Then apply Exercise 2.8 to the second branch of the if statement. Argue that mL can be replaced with mR and complete the proof.

3.4: Suppose $$T$$ is a fixed (publicly known) invertible $$n \times n$$ matrix over $$\mathbb{Z}_p$$, where $$p$$ is a prime.

(a). Show that the following two libraries are interchangeable:

$\mathscr{L}_{\text{left}}\space\space\space\space\space\space\space\mathscr{L}_{\text{right}}\\\underline{\text{QUERY}():}\space\space\space\space\space\space\space\underline{\text{QUERY}():}\\r\leftarrow (\mathbb{Z}_p)^n \space\space\space\space\space\space\space r\leftarrow (\mathbb{Z}_p)^n\\ \text{return}\space r \space\space\space\space\space\space\space\text{return}\space T\times r\nonumber$

(b). Show that the following two libraries are interchangeable: 3.5: The text gives a proof of Lemma 3.4.1 for the special case where the calling program always calls $$\text{QUERY}$$ with $$|U| = t − 1$$. This exercise shows one way to complete the proof. Define the following “wrapper” library: (a). Argue that $$\mathscr{L}_{sss-real} \equiv \mathscr{L}_{\text{wrap}} \diamondsuit \mathscr{L}^{’}_{\text{sss-real}}$$, where on the right-hand side $$\mathscr{L}^{’}_{\text{sss-real}}$$ refers to $$\mathscr{L}_{\text{sss-real}}$$ but with its QUERY subroutine renamed to QUERY’.

(b). Argue that $$\mathscr{L}_{sss-rand} \equiv \mathscr{L}_{\text{wrap}} \diamondsuit \mathscr{L}^{’}_{\text{sss-rand}}$$, with the same interpretation as above.

(c). Argue that for any calling program ?, the combined program $$? \diamondsuit \mathscr{L}_{\text{wrap}}$$ only calls QUERY’ with $$|U| = t − 1$$. Hence, the proof presented in the text applies when the calling program has the form $$? \diamondsuit \mathscr{L}_{\text{wrap}}$$.

(d). Combining the previous parts, show that $$\mathscr{L}_{\text{sss-real}} \equiv \mathscr{L}_{\text{sss-rand}}$$ (i.e., the two libraries are interchangeable with respect to arbitrary calling programs).

3.6: Let S be a TSSS with $$? = \{ 0,1 \} ^ { \ell }$$ and where each share is also a string of bits. Prove that if $$S$$ satisfies security then every user’s share must be at least $$\ell$$ bits long.

Hint: Prove the contrapositive. Suppose the first user’s share is less than $$\ell$$ bits (and that this fact is known to everyone). Show how users 2 through t can violate security by enumerating all possibilities for the first user’s share.

3.7: n users have shared two secrets using Shamir secret sharing. User $$i$$ has a share $$s_i = (i,y_i)$$ of the secret m, and a share $$s^{’}_i = (i,y^{’}_i)$$ of the secret $$m^{’}$$ . Both sets of shares use the same prime modulus $$p$$.

Suppose each user $$i$$ locally computes $$z_i = y_i + y^{’}_i \% p$$.

(a). Prove that if the shares of m and shares of m’ had the same threshold, then the resulting $$\{(i,z_i) | i \le n\}$$ are a valid secret-sharing of the secret $$m + m^‘$$.

(b). Describe what the users get when the shares of $$m$$ and $$m^‘$$ had different thresholds (say, $$t$$ and $$t^‘$$, respectively).

3.8: Suppose there are 5 people on a committee: Alice (president), Bob, Charlie, David, Eve. Suggest how they can securely share a secret so that it can only be opened by:

• Alice and any one other person
• Any three people

Describe in detail how the sharing algorithm works and how the reconstruction works (for all authorized sets of users).

3.9: Suppose there are 9 people on an important committee: Alice, Bob, Carol, David, Eve, Frank, Gina, Harold, & Irene. Alice, Bob & Carol form a subcommittee; David, Eve & Frank form another subcommittee; and Gina, Harold & Irene form another subcommittee.

Suggest how a dealer can share a secret so that it can only be opened when a majority of each subcommittee is present. Describe why a 6-out-of-9 threshold secret-sharing scheme does not suffice

Hint: 3.10: Generalize the previous exercise. A monotone formula is a boolean function $$\Phi : \{ 0,1 \} ^ { \mathrm { n } } \rightarrow \{ 0,1 \}$$ that when written as a formula uses only AND and OR operations (no NOTS). For a set $$A \subseteq \{1,. . . , n\}$$, let $$χ_A$$ be the bitstring where whose $$i$$th bit is 1 if and only if $$i \in A$$.

For every monotone formula $$\phi : \{ 0,1 \} ^ { n } \rightarrow \{ 0,1 \}$$, construct a secret-sharing scheme whose authorized sets are $$A \subseteq \{1,. . . , n\} | \phi(χ_A) = 1\}$$. Prove that your scheme is secure.

Hint: express the formula as a tree of AND and OR gates.

3.11: Prove that share $$s_2$$ in Construction 3.5.1 is distributed independently of the secret $$m$$.

3.12: Construct a 3-out-of-3 visual secret sharing scheme. Any two shares should together reveal nothing about the source image, but any three reveal the source image when stacked together.

3.13: Using actual transparencies or with an image editing program, reconstruct the secret shared in these two images: 