Skip to main content
[ "article:topic", "showtoc:no", "license:ccbync", "authorname:mrosulek" ]
Engineering LibreTexts

3.2: A Simple 2-out-of-2 Scheme

  • Page ID
    7328
  • Believe it or not, we have already seen a simple secret-sharing scheme! In fact, it might even be best to think of one-time pad as the simplest secret-sharing scheme, since by itself it is not so useful for encryption.

    Construction \(\PageIndex{1}\) : 2-out-of-2 TSSS

    Screen Shot 2019-02-16 at 10.17.02 PM.png

    Since it’s a 2-out-of-2 scheme, the only authorized set of users is {1,2}, so we write Reconstruct to expect as input both shares \(s_1\) and \(s_2\). Correctness follows easily from what we’ve already learned about the properties of XOR.

    Theorem \(\PageIndex{1}\) :

    Construction \(\PageIndex{1}\)  is a secure 2-out-of-2 threshold secret-sharing scheme.

    Proof:

    Let \(\Sigma\) denote Construction \(\PageIndex{1}\). We will show that \(\mathscr{L}^{\Sigma}_{\text{tsss-L}} \equiv \mathscr{L}^{\Sigma}_{\text{tsss-R}}\) using a hybrid proof.

    Screen Shot 2019-02-16 at 10.20.24 PM.png

    As usual, the starting point is \(\mathscr{L}^{\Sigma}_{\text{tsss-L}}\), shown here with the details of the secret-sharing scheme filled in (and the types of the subroutine arguments omitted to reduce clutter).

    Screen Shot 2019-02-16 at 10.21.17 PM.png

    It has no effect on the library’s behavior if we duplicate the main body of the library into 3 branches of a new if-statement. The reason for doing so is that the scheme generates \(s_1\) and \(s_2\) differently. This means that our proof will eventually handle the 3 different unauthorized sets ({1}, {2}, and \(\oslash\)) in fundamentally different ways.

    Screen Shot 2019-02-16 at 10.25.50 PM.png

    The definition of \(s_2\) has been changed in the first if-branch. This has no effect on the library’s behavior since \(s_2\) is never actually used in this branch.

    Screen Shot 2019-02-16 at 11.10.14 PM.png

    Recognizing the second branch of the if-statement as a one-time pad encryption (of \(m_L\) under key \(s_1\)), we factor out the generation of \(s_2\) in terms of the library \(\mathscr{L}^{OTP}_{\text{ots-L}}\) from the one-time secrecy definition. This has no effect on the library’s behavior. Importantly, the subroutine in \(\mathscr{L}^{OTP}_{\text{ots-L}}\) expects two arguments, so that is what we must pass. We choose to pass \(m_L\) and \(m_R\) for reasons that should become clear very soon.

    Screen Shot 2019-02-16 at 11.12.14 PM.png

    We have replaced \(\mathscr{L}^{OTP}_{\text{ots-L}}\) with \(\mathscr{L}^{OTP}_{\text{ots-R}}\). From the one-time secrecy of one-time pad (and the composition lemma), this change has no effect on the library’s behavior

    Screen Shot 2019-02-16 at 11.13.45 PM.png

    A subroutine has been inlined; no effect on the library’s behavior.

    Screen Shot 2019-02-16 at 11.15.02 PM.png

    The code has been simplified. Specifically, the branches of the if-statement can all be unified, with no effect on the library’s behavior. The result is \(\mathscr{L}^{\Sigma}_{\text{tsss-R}}\).

    We showed that \(\mathscr{L}^{\Sigma}_{\text{tsss-L}} \equiv \mathscr{L}_{\text{hyb-1}} \equiv · · · \equiv \mathscr{L}_{\text{hyb-5}} \equiv \mathscr{L}^{\Sigma}_{\text{tsss-R}}\), and so the secret-sharing scheme is secure.

    We in fact proved a slightly more general statement. The only property of one-time pad we used was its one-time secrecy. Substituting one-time pad for any other one-time secret encryption scheme would still allow the same proof to go through. So we actually proved the following:

    Theorem \(\PageIndex{2}\) :

    If \(\Sigma\) is an encryption scheme with one-time secrecy, then the following 2-out-of-2 threshold secret-sharing scheme \(S\) is secure:

    Screen Shot 2019-02-16 at 11.18.57 PM.png