3.6: Exercise

Exercise \(3.1\)

Generalize Construction \(3.5\) to be an \(n\)-out-of- \(n\) secret-sharing scheme, and prove that your scheme is correct and secure.

Exercise \(3.2\)

Prove Theorem \(3.7\)

Exercise \(3.3\)

Fill in the details of the following alternative proof of Theorem 3.6: Starting with \(\mathcal{L}_{\mathrm{tsss}-\mathrm{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.3\) to the second branch of the if-statement. Argue that \(m_{L}\) can be replaced with \(m_{R}\) and complete the proof.

Exercise \(3.4\)

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

1. Show that the following two libraries are interchangeable:

Figure \(\PageIndex{1}\): Copy and Paste Caption here. (Copyright; author via source)

2. Show that the following two libraries are interchangeable:

Figure \(\PageIndex{1}\): Copy and Paste Caption here. (Copyright; author via source)

Exercise \(3.5\)

Consider a \(t\)-out-of- \(n\) threshold secret sharing scheme with \(\mathcal{M}=\{0,1\}^{\ell}\), and where each user’s share is also a string of bits. Prove that if the scheme is secure, then every user’s share must be at least \(\ell\) bits long.

Hint: Prove the contrapotive. Support the first user's share is less than \(\ell\) bits (and that this fact is known to everyone). Show how users 2 thought \(t\) can violate security by enumerating all possibilities for the first user's share. Give your answer in the form of an distinguisher on the relevant libraries.

Exercise \(3.6\)

\(n\) users have shared two secrets using Shamir secret sharing. User \(i\) has a share \(s_{i}=\left(i, y_{i}\right)\) of the secret \(m\), and a share \(s_{i}^{\prime}=\left(i, y_{i}^{\prime}\right)\) of the secret \(m^{\prime}\). Both sets of shares use the same prime modulus \(p\).

Suppose each user \(i\) locally computes \(z_{i}=\left(y_{i}+y_{i}^{\prime}\right) \% p\).

1. Prove that if the shares of \(m\) and shares of \(m^{\prime}\) had the same threshold, then the resulting \(\left\{\left(i, z_{i}\right) \mid i \leqslant n\right\}\) are a valid secret-sharing of the secret \(m+m^{\prime} .\)
2. Describe what the users get when the shares of \(m\) and \(m^{\prime}\) had different thresholds (say, \(t\) and \(t^{\prime}\), respectively).

Exercise \(3.7\)

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).

Note: It is fine if different users have shares which are of different sizes (e.g., different number of bits to represent), and it is also fine if the Reconstruct algorithm depends on the identities of the users who are contributing their shares.

Exercise \(3.8\)

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:

Figure \(\PageIndex{1}\): Copy and Paste Caption here. (Copyright; author via source)

Exercise \(\star 3.9\)

1. (a) Generalize the previous exercise. A monotone formula is a boolean function \(\phi\) : \(\{0,1\}^{n} \rightarrow\{0,1\}\) that when written as a formula uses only AND and or operations (no NOTs). For a set \(A \subseteq\{1, \ldots, n\}\), let \(\chi_{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 \(\left\{A \subseteq\{1, \ldots, n\} \mid \phi\left(\chi_{A}\right)=1\right\}\). Prove that your scheme is secure.

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

2. (b) Give a construction of a \(t\)-out-of- \(n\) secret-sharing scheme in which all shares are binary strings, and the only operation required of Share and Reconstruct is Xor (so no mod- \(p\) operations).

   How big are the shares, compared to the Shamir scheme?

Exercise \(3.10\)

Prove that share \(s_{2}\) in Construction \(3.14\) is distributed independently of the secret \(m\).

Exercise \(3.11\)

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

Figure \(\PageIndex{1}\): Copy and Paste Caption here. (Copyright; author via source)

Exercise \(\star 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.