\documentclass[12pt]{article}
%\usepackage{amsmath,amssymb,psfrag,epsfig,boxedminipage,helvet,theorem,endnotes,version}
\usepackage{amsthm}
\newcommand{\remove}[1]{}
\setlength{\oddsidemargin}{-.2in}
\setlength{\evensidemargin}{-.2in}
\setlength{\textwidth}{6.5in}
\setlength{\topmargin}{-0.8in}
\setlength{\textheight}{9.5in}



\newcommand{\handout}[2]{
\renewcommand{\thepage}{\footnotesize COMS W4261, Introduction to
  Cryptography, #1, p. \arabic{page}}
\noindent
{\bf COMS W4261: Introduction to Cryptography.}

\noindent
{Instructor: Prof.~Tal Malkin}

\bigskip
\begin{center}
{\Large #1}
\end{center}
}


\newcommand{\gen}{\mbox{\tt Gen}}
\newcommand{\enc}{\mbox{\tt Enc}}
\newcommand{\dec}{\mbox{\tt Dec}}


\newcommand{\share}{\mbox{\tt Share}}
\newcommand{\rec}{\mbox{\tt Reconstruct}}
\newcommand{\M}{{\cal M}}
\newcommand{\tofn}{$t$-out-of-$n$} 


\newtheorem{theorem}{Theorem} 
\newtheorem{definition}{Definition}


\newcommand{\sol}{{\bf Solution}: }

\newcommand{\zo}{\{0,1\}}
\newcommand{\zoell}{\{0,1\}^\ell}
\newcommand{\zon}{\{0,1\}^n}
\newcommand{\zok}{\{0,1\}^k}

\newcommand*\concat{\mathbin{\|}}

\newcommand\xor{\oplus}


\begin{document}

\handout{\bf Lecture Notes on Secret Sharing}{}
\begin{abstract}
These are lecture notes from the first two lectures in Fall 2016,
focusing on technical material we saw for secret sharing (including a
proof by reduction using the hybrid proof technique).   The notes
do not include the general introduction to the course and modern
crypto, as well as some discussion and motivation for secret sharing. 
Also not covered here is Shamir's secret sharing, which we saw in the
third lecture.  
\end{abstract}

\section{Definition}

Intuitively, a secret sharing scheme allows a {\em dealer\/} to share
a secret $s$ among 
 $n$ parties $P_1,\ldots,P_n$, such that any {\em authorized} subset
 of parties can use all their shares to reconstruct the secret, while
 any other (non-authorized) subset learns nothing about the secret
 from their shares.
 
 We discussed motivating scenarios for secret sharing in class, and it
 is also a useful tool in many larger cryptographic systems (notably,
 secure computation).

 Secret sharing can be defined with respect to any access structure
 that specifies the set of authorized subsets, as long as that access
 structure is monotone (namely, if a subset is authorized, any larger
 subset should also be authorized).  In class, we gave a definition
 for the common case of {\em \tofn\ } (or {\em threshold\/} secret
 sharing, where authorized subsets are all those of size at least $t$,
 while sets of size less than $t$ are not authorized.

 \begin{definition}[\tofn\ secret sharing syntax and correctness]
   A {\em \tofn\ secret sharing scheme} over message space
   $\cal M$ is a pair of algorithms $(\share,\rec)$ such that:
   \begin{itemize}
   \item \share\ is a randomized algorithm that on any input $m\in\M$
     outputs a $n$-tuple of shares $(s_1,\ldots,s_n)$.
   \item \rec\ is a deterministic algorithm that given a $t$-tuple of
     shares outputs a message in $\M$
   \end{itemize}
   and satisfying the following {\em correctness} requirement:

   $ \forall m\in\M, \forall
   S=\{i_1,\ldots,i_t\}\subseteq\{1,\ldots,n\}$  of size $t$, 
   \[ \Pr_{\share(m)\rightarrow
     (s_1,\ldots,s_n)}[\rec(s_{i_1},\ldots,s_{i_t})=m] = 1 
   \]
 \end{definition}

 We discussed how we should go about defining security for such a
 \tofn\ secret sharing scheme.  Clearly, we need to require
 that any subset of size less than $t$ cannot reconstruct the secret
 from its shares.  But this is not sufficient:  we want to require
 that such a subset cannot, for example figure out the first bit of
 the secret, or the parity (xor of all bits), or be able to use their
 shares together with some  prior information on what the secret may
 be in order to deduce even more information.\footnote{This is a theme
   we will see again and again in cryptography: we prefer our
   definition to hold against adversaries who may or may not have
   arbitrary side information.  This is important to make our
   definitions of security stronger, and also so that the security
   does not depend on the context or application scenarios where the
   primitive is being used as a component.}

 We ended up with two definitions, which we claimed (though didn't
 proof) are equivalent. These definitions capture the idea that the shares
 of any unauthorized subset contain no information at all about the
 secret.  Indeed, the definitions require that these shares look
 exactly the same whether they came from  secret $m$ or from secret
 $m'$, for any possible secrets $m,m'$.

 \begin{definition}[secret sharing security via identical
     distributions]   \label{ss_identical} 
   A \tofn\ secret sharing scheme $(\share,\rec)$ over \M\ is perfectly
   secure if:

   $\forall m,m'\in\M$, $\forall S\subseteq\{1,\ldots,n\}$ s.t.~$|S|<t$,
   the following distributions are identical:
      \[ \{ (s_i | i\in S) :  (s_1,\ldots,s_n)  \leftarrow \share(m) \} \]
   \[ \{  (s'_i | i\in S) :  (s'_1,\ldots,s'_n) \leftarrow \share(m')  \} \]
 \end{definition} 
    
Recall that two distributions are identical if they give exactly the
same probability for every possible value.  Thus, the above definition
can be restated as follows:
$\forall m,m'\in\M$, $\forall S\subseteq\{1,\ldots,n\}$ s.t.~$|S|<t$,
and for any set $\alpha=(\alpha_1,\ldots,\alpha_{|S|})$, we have that
\[ \Pr_{\share(m)\rightarrow (s_1,\ldots,s_n)}[(s_i| i\in S) = \alpha]
= \Pr_{\share(m')\rightarrow (s'_1,\ldots,s'_n)}[(s'_i| i\in S) =
  \alpha]\]

The second (and equivalent) definition we gave is in terms of an
adversarial algorithm $A$ trying to learn information about the
secret.
Intuitively, we require that even if the adversary is
trying to learn 
just {\em one} bit of information to differentiate between shares of $m$ or
$m'$ (for any pair of secrets $m,m'$), it will fail.  

\begin{definition}[secret sharing security with adversaries]
  \label{ss_adv}
  A \tofn\ secret sharing scheme $(\share,\rec)$ over \M\ is perfectly
  secure if:

   $\forall m,m'\in\M$, $\forall S\subseteq\{1,\ldots,n\}$
  s.t.~$|S|<t$, $\forall A$,
  \[\Pr_{\share(m)\rightarrow (s_1,\ldots,s_n)}[A( (s_i | i\in S)) =  1]
   = 
  \Pr_{\share(m')\rightarrow (s'_1,\ldots,s'_n)}[A( (s'_i | i\in S)) = 1]\] 

\end{definition}

\section{A 2-out-of-2 Secret Sharing Scheme}
Consider the following simple 2-out-of-2 secret sharing scheme for
$\ell$-bit secrets.

\medskip\noindent
$\share_{2-2}$:  On input $m\in\{0,1\}^\ell$,
\begin{itemize}
  \item select $s_0\in\{0,1\}^\ell$ uniformly at random.
  \item set $s_1= s_0\xor m$
  \item output $(s_0,s_1)$ 
\end{itemize} 

\medskip\noindent 
$\rec_{2-2}$: On input $(s_0,s_1)\in \{0,1\}^\ell \times \{0,1\}^\ell$,
\begin{itemize}
  \item output $s_0 \xor s_1$ 
\end{itemize}

Note that in this scheme, the size of each share is the size of the
secret ($\ell$ bits).  It can be shown that this size is required
(there's no scheme where each share is shorter). 

\begin{theorem}
  The scheme $(\share_{2-2}, \rec_{2-2})$ above is a correct and secure
  2-out-of-2 secret sharing scheme over $\M=\{0,1\}^\ell$. 
\end{theorem}

\begin{proof}
 Correctness follows immediately from the way $\share_{2-2}$ and
$\rec_{2-2}$ were defined: 
% 
$\forall m\in\{0,1\}^\ell$, 
\[\Pr_{\share(m)\rightarrow (s_0,s_1)}[\rec(s_0,s_1)=m] =
%  \Pr_{\share(m)\rightarrow (s_0,s_1)}[s_0\xor s_1=m] = 
    \Pr_{\share(m)\rightarrow (s_0,s_1)}[s_0\xor s_0 \xor m =m] =1 \] 


Security follows intuitively since each share individually is
distributed uniformly at random, so does not contain any information
about the secret.  We prove it formally using Definition~\ref{ss_identical}.

Fix any $m,m'\in \{0,1\}^\ell$, and consider a subset of one
share.

In case it is the first share, since it is chosen uniformly, we have
that $\forall \alpha\in\{0,1\}^\ell$, 
\[
\Pr_{\share(m)\rightarrow (s_0,s_1)}[s_0=\alpha] =
  \frac{1}{2^{\ell}}
  = \Pr_{\share(m')\rightarrow (s'_0,s'_1)}[s'_0=\alpha]
  \]  

    
    In case it is the second share, we have that 
    $\forall \alpha\in\{0,1\}^\ell$, 
    \[ \Pr_{\share(m)\rightarrow (s_0,s_1)}[s_1=\alpha] =
      \Pr_{\share(m)\rightarrow (s_0,s_1)}[s_0 \xor m =\alpha] =
              \Pr_{\share(m)\rightarrow (s_0,s_1)}[s_0 = m \xor
                  \alpha]=     \frac{1}{2^{\ell}} \] 




Similarly,  \[ \Pr_{\share(m')\rightarrow (s'_0,s'_1)}[s'_1=\alpha] =
  \Pr_{\share(m')\rightarrow (s'_0,s'_1)}[s'_0 = m' \xor \alpha] =
    \frac{1}{2^{\ell}}\]
    and again both probabilities are equal. 
This completes the proof. 
\end{proof}

\subsection*{$t$-out-of-$t$ Secret Sharing Scheme} 
The above scheme is sometimes referred to as ``additive secret
sharing'', since the xor operation is addition mod 2.
We note that additive secret sharing can easily be extended
to any $t$-out-of-$t$ threshold secret sharing.  The sharing algorithm
chooses $t$ strings uniformly at random subject to the requirement
that their xor is the secret (this can be done by choosing $t-1$
strings uniformly at random, and setting the last string to be the xor
of all previous ones and the secret). The reconstruction algorithm
simply xors the shares.  We leave the proof of correctness and
security as an exercise.


\section{A 2-out-of-$n$ Secret Sharing Scheme}

We will see next time a direct way to get any \tofn\ secret
sharing. Here, we will build a 2-out-of-$n$ secret sharing from any
2-out-of-2 secret sharing.  This will allow us to show the first
instance of a reduction, and also allow us to introduce the hybrid
proof techniques -- both useful tools that we will see many more time
in this class.

\subsection{Reductions in Cryptography: General Comments} \label{reduction}
The notion of {\em reduction} is a central notion in cryptography,
which we describe here informally.  In general, to show that
$P \Rightarrow Q$ for some cryptographic primitives $P,Q$, we
typically show a construction of $Q$ that calls $P$ as a subroutine
(so, we assume $P$ is given, and we construct $Q$ out of it). We then
prove correctness and security of our construction of $Q$, assuming
the correctness and security of the underlying $P$. 

The security proof typically has the following structure.  To prove
that security of $P$ implies security of $Q$, we prove the
contrapositive: If $Q$ is not secure, then we show $P$ is not secure
either.  So, we start by assuming we are given an adversary $A$
breaking the security of our constructed $Q$.  We use it to construct an
adversary $B$, which can call $A$ as a subroutine, and breaks $P$.

We will now see how to apply this general approach to our current
example. 

\subsection{Building $2$-out-of-$n$ Secret Sharing from $2$-out-of-$2$
Secret Sharing}

Suppose we are given a 2-out-of-2 secret sharing
scheme $(\share_{2-2},\rec_{2-2})$ (e.g., the one we showed above).  We
want to use it to construct a $2$-out-of-$n$ secret sharing scheme,
namely sharing the secret among $n$ parties, so that any two of them can
reconstruct, but any single party learns nothing about the secret. 

A first idea is to just share the secret via a fresh 2-out-of-2
sharing for every possible pair of parties.  The new share of each party
consists of $n-1$  2-out-of-2 shares (one for each of the other
parties).  When two parties get together, they can use the two
corresponding 2-out-of-2 shares to reconstruct the secret.

The above idea works (satisfies correctness and security). However,
the size of the share for each party is $(n-1)$ times the 2-out-of-2 share
size, so at least $(n-1)\ell$ for $\ell$ bit secrets.  Can we do
better?

In the above, we shared the secret afresh $n$ times.  The idea for the
improved 2-out-of-$n$  scheme is to have a smaller number of
2-out-of-2 sharings, as long as we have the property that any pair of
parties has at least one complete pair of two corresponding shares (or
``two halves'' from the same sharing).   We can achieve this property
with only $\log n$ 2-out-of-2 sharings, where each party gets one half
of each of the $\log n$ pairs of shares, corresponding to the binary
representation of the party's index.
The resulting share size will be $\log n$ times the 2-out-of-2 share
size, so we can do this with $(\log n)\ell$ share size for $\ell$ bit
secrets. The scheme is specified below. 


\medskip\noindent 
$\share_{2-n}$:  On input $m\in\{0,1\}^\ell$,
\begin{itemize}
\item For $k=1$ to $\log n$
  \begin{itemize}
  \item Run $\share_{2-2}(m)\rightarrow (s_0^k, s_1^k)$
  \end{itemize}

\item For $i=0$ to $n-1$, if binary representation of $i$ is
  $i_1\ldots i_{\log n}$, set $S_i=(i, s_{i_1}^1,\ldots,s_{i_{\log
    n}}^{\log n})$ 
\item  Output $(S_0,\ldots,S_{n-1})$.
\end{itemize}

\medskip\noindent
$\rec_{2-n}$:  On input $(S_i,S_j)$,  
\begin{itemize}
  \item Consider the binary representations of the indices
    $i=i_1\ldots i_{\log n}$ and $j=j_1\ldots j_{\log n}$.
  \item Find a bit position $k$ where they differ, namely
    $i_k \neq j_k$ (thus, $s_{i_k}^k =s_0^k, s_{j_k}^k= s_1^k$ or vice
    versa).  
  \item Run $\rec_{2-2}(s_0^k,s_1^k)$ and output the same. 
\end{itemize}



\begin{theorem}
If $(\share_{2-2},\rec_{2-2})$ is a correct and secure 2-out-of-2
secret sharing scheme over $\M=\{0,1\}^\ell$, then the scheme
$(\share_{2-n},\rec_{2-n})$ specified above is a correct and secure
2-out-of-$n$ secret sharing scheme over $\M$. 
\end{theorem}

\begin{proof} 
  Correctness:  $\forall m\in\{0,1\}^\ell$, $\forall i\neq j \in
  \{0,\ldots,n-1\}$, 
  \begin{eqnarray*}
  \Pr_{\share_{2-n}(m)\rightarrow(S_0,\ldots,S_{n-1})}[\rec_{2-n}(S_i,S_j)=m]
  =\\
 = \Pr_{\share_{2-2}(m)\rightarrow(s_0^k,s_1^k)}[\rec_{2-2}(s_0^k,s_1^k)=m]
 = 1
  \end{eqnarray*}
  where the first equality follows from the construction and the fact
  that any indices $i\neq j$ differ in at least one position $k$, and
  the second equality follows from the correctness of 
  $(\share_{2-2},\rec_{2-2})$.

  For security, we could use the definition via identical
  distributions (Definition~\ref{ss_identical}) fairly easily.
  However, for pedagogical reasons we will prove security via the
  adversary based definition (Definition~\ref{ss_adv}).  As discussed,
  this will allow us to introduce a new proof technique and common
  proof structure.

  As described in Section~\ref{reduction}, we start by assuming that
  the 2-out-of-$n$ scheme above is not secure.  This means (by
  negation of Definition~\ref{ss_adv}) that $\exists m,m' \in
  \{0,1\}^\ell$, $\exists i\in\{0,\ldots,n-1\}$, $\exists A$, such that
  \begin{equation} \label{eq_A}
    \Pr_{\share_{2-n}(m)\rightarrow (S_1,\ldots,S_n)}[A(S_i)=1] \neq
    \Pr_{\share_{2-n}(m')\rightarrow (S'_1,\ldots,S'_n)}[A(S'_i)=1]
  \end{equation}
  %
  Our goal is to use this to construct an adversary $B$ that breaks
  the 2-out-of-2 scheme.


  
  In Equation~(\ref{eq_A}) above, we have two distributions such that
  when $A$ is called on one it outputs 1 with a different probability
  than when it's called on the other.
  Recall that in the lefthandside distribution (which we will name
  $H^0$), we have $S_i = (s_{i_1}^1,\ldots,s_{i_{\log n}}^{\log n})$,
  where each $(s_0^k,s_1^k)$ is the output of $\share_{2-2}(m)$.
  In the righthandside distribution (which we will name $H^{\log n}$),
  we have $S'_i = (s^{'1}_{i_1},\ldots,s^{'\log n}_{i_{\log n}})$,
  where each $(s^{'k}_0,s^{'k}_1)$ is the output of $\share_{2-2}(m')$.

  We will define intermediate distributions $H^j$ (``hybrids'') where for each
  share, the first $j$ components are taken from $m'$, while the rest
  are taken from $m$.  That is, for every $j\in\{0,\ldots,\log n\}$,
  we define
  \begin{eqnarray*}
    H^j =
  \{ \forall k\in\{1,\ldots,\log n\} \, \,
  \share^k_{2-2}(m)\rightarrow (s^k_0,s^k_1), \,
  \share^k_{2-2}(m')\rightarrow (s^{'k}_0,s^{'k}_1) : \\ 
  (s^{'1}_{i_1},\ldots,s^{'j}_{i_j},s^{j+1}_{i_{j+1}},\ldots,s^{\log
    n}_{i_{\log n}})
  \}
  \end{eqnarray*}

  Using this notation,  Equation~(\ref{eq_A}) can be written as:
  $\Pr[A(H^0)=1] \neq \Pr[A(H^{\log n})=1]$.

 It follows that there must exist a $j\in \{1,\ldots,\log n\}$ such
 that
 \begin{equation} \label{eq_B}
   \Pr[A(H^{j-1})=1] \neq \Pr[A(H^{j})=1]\end{equation}
 (otherwise, if all
 adjacent hybrids produce equal probabilities, the end hybrids would
 also have equal probabilities).

 Equation~(\ref{eq_B}) says that $A$ outputs 1 with different
 probabilities when applied to
 $$ (s^{'1}_{i_1},\ldots,s^{'j-1}_{i_{j-1}},s^{j}_{i_{j}},s^{j+1}_{i_{j+1}},
 \ldots,s^{\log   n}_{i_{\log n}})$$
 vs.~when applied to 
 $$(s^{'1}_{i_1},\ldots,s^{'j-1}_{i_{j-1}},s^{'j}_{i_j},s^{j+1}_{i_{j+1}},\ldots,s^{\log
    n}_{i_{\log n}})$$

 
 We now have two ``adjacent'' hybrids, differing in only one location ($j$),
 that $A$ behaves differently on.  We are finally ready to define $B$,
 that will attack the 2-out-of-2 sharing, by ``plugging it in'' that
 location. Specifically, we define $B$ as follows (where $i,j,m,m'$
 are all hard-coded into $B$): 

 \medskip\noindent
 B: on input {\bf s},
 \begin{itemize}
 \item   For $k=1,\ldots,j-1$, run $\share_{2-2}(m')\rightarrow
   (s^{'k}_0,s^{'k}_1)$.
 \item  For $k=j+1,\ldots,\log n$, run
   $\share_{2-2}(m)\rightarrow (s^k_0,s^k_1)$
 \item Set $S_i=(s^{'1}_{i_1},\ldots,s^{'j-1}_{i_{j-1}}, {\bf s} ,s^{j+1}_{i_{j+1}},
   \ldots,s^{\log   n}_{i_{\log n}})$
 \item Run $A(S_i)$ and output the same. 
 \end{itemize} 

 
 Now it is not hard to see that for the same $m,m',i,j$ from above
 we have that 
 $$ \Pr_{\share_{2-2}(m)\rightarrow
   (s_0,s_1)}[B(s_{i_j})=1]=\Pr[A(H^{j-1})=1]$$
 while
 $$ \Pr_{\share_{2-2}(m')\rightarrow
   (s'_0,s'_1)}[B(s'_{i_j})=1]=\Pr[A(H^{j})=1]$$
 By Equation~\ref{eq_B} these two are not equal, and thus $B$ breaks
 the security of the 2-out-of-2 secret sharing scheme (as per
 Definition~\ref{ss_adv}).

 We have shown that if the security of our 2-out-of-$n$ is broken,
 then so is the security of the underlying 2-out-of-2 scheme
 (contradiction). This completes the proof.
 
\end{proof}


\end{document} 
