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

Last updated
Save as PDF

Page ID: 7328

\( \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}}\)

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