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

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

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.

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

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.

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.

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.

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

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

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: