Skip to main content
Engineering LibreTexts

3.6: Exercises

  • Page ID
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)

    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:

    Screen Shot 2019-02-18 at 1.22.14 PM.png

    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:

    Screen Shot 2019-02-18 at 1.27.13 PM.png

    (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


    Screen Shot 2019-02-18 at 1.44.22 PM.png

    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:

    Screen Shot 2019-02-18 at 1.49.11 PM.png

    3.6: Exercises is shared under a CC BY-NC-SA 4.0 license and was authored, remixed, and/or curated by Mike Rosulek.

    • Was this article helpful?