# Exercises

- Page ID
- 7332

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: