secret-sharing.tex

\section{Secret Sharing}\label{s:secret-sharing}
Secret sharing is a method for distributing a secret between $N$ different parties, where a secret message $m$ is divided into parts, giving each participant its own unique part $(s_1, s_2, \dots, s_N)$.
Combining some of the parts or all of them are needed in order to reconstruct the original secret.
The most common type of secret sharing is a scheme with one dealer and $N$ different players.
Initially, the dealer splits the secret to shares and gives each player a split.
Only with all -- or most of the shares $k \geq T$  ($T$ is a threshold) -- someone is able to reconstruct the original secret.
The dealer accomplishes this by giving each player a share in such a way that any group of $T$ or more players can together reconstruct the secret but no group of fewer than $T$ players can.
Such a system is called a $(T, N)$ - threshold scheme.

A naive secret sharing scheme between a dealer and two parties is to apply bitwise \texttt{XOR} to the secret and a random string of the same length.
For the sake of simplicity, let us assume that the secret message m is a string of 5 bits (either 0 or 1), \textit{e.g.} 01101.
Then, the dealer generates a random string of 5 bits $s_1$ (\textit{e.g.} $10011$) and performs the \texttt{XOR} operation between $s_1$ and $m$; a string $s_2 = 11110$ arises.
Finally, the dealer gives the $s_1$ and $s_2$ to the two parties.
Neither one of them is able to retrieve the secret message $m$ without the other half share, and also nor is able to retrieve any information about the original message.

There exist more complex and elaborate systems for more than two parties, such as Shamir’s \cite{shamir1979share}, Blakley’s \cite{blakley1994linear}, or Additive \cite{kim2003designs} secret sharing schemes.


\subsection{Shamir Secret Sharing}\label{ss:shamir-secret-sharing}
Secret sharing was proposed in \cite{shamir1979share} by Shamir, and it was the first method to enable distribution of a secret to $N$ parties.
A secret message $m$ is divided into $N$ parts, giving each participant its own unique part, where any $T$ subset of $N$ can recover the secret, but no $T-1$ element subset can.

Adi Shamir's threshold scheme is based on the idea of polynomial interpolation -- the interpolation of a given dataset by the polynomial of lowest possible degree that passes through the points of the dataset --, using Lagrange coefficients.
Shamir's secret sharing scheme constructs a polynomial $P$ of degree $N-1$, where $N$ is the number of players, as follows.


\subsubsection{Algorithm}\label{sss:shamir-algorithm}
\begin{itemize}
  \item Dealer chooses a random polynomial of degree $N - 1$ so that $P(0) = m$, where $m$ is the secret message, and also the number $T$ of sufficient subsets that can reconstruct the secret.

  \textit{For example\footnote{This example is based on a similar example in \url{https://en.wikipedia.org/wiki/Shamir's_Secret_Sharing} Wikipedia link.}}, let us suppose our secret message $m = 1234$ and $N = 6$ parties, but any subset of $T = 3$ is sufficient to reconstruct the secret.
  Then our polynomial should have degree 2, $f(x) = ax^2 + bx + m$.
  The dealer chooses $N - 1$ random numbers, \textit{i.e.} $a = 94$ and $b = 166$, thus our polynomial is $f(x) = 94x^2 + 166x + 1234$.


  \item Dealer distributes $N$ pairs $(x_i , P(x_i)),$ $x_i \neq 0$

  First the dealer creates the $N$ pairs.
  \textit{For example}:\\
  $D_0 = (1, 1494)$, $D_1 = (2, 1942)$, $D_2 = (3, 2578)$, $D_3 = (4, 3402)$, $D_4 = (5, 4414)$, $D_5 = (6, 5614)$ and consecutively he\myslash she distributes them to the $N$ parties.


  \item $N$ players can reconstruct the polynomial $P$ with their pairs, however $N - 1$ cannot

  In order to reconstruct the secret any $T$ points will be enough, \textit{for instance}, $D_1, D_3$ and $D_4$.
  Computing the Lagrange polynomials:\\
  $l_0 = \cfrac{x - x_1}{x_0 - x_1} \times \cfrac{x - x_2}{x_0 - x_2} = \cfrac{x - 4}{2 - 4} \times \cfrac{x - 5}{2 - 5} = \cfrac{1}{6}x^2 - \cfrac{3}{2}x + \cfrac{10}{3}$

  $l_1 = \cfrac{x - x_0}{x_1 - x_0} \times \cfrac{x - x_2}{x_1 - x_2} = \cfrac{x - 2}{4 - 2} \times \cfrac{x - 5}{4 - 5} = \cfrac{1}{2}x^2 + \cfrac{7}{2}x - 5$

  $l_2 = \cfrac{x - x_0}{x_2 - x_0} \times \cfrac{x - x_1}{x_2 - x_1} = \cfrac{x - 2}{5 - 2} \times \cfrac{x - 4}{5 - 4} = \cfrac{1}{3}x^2 - 2x + \cfrac{8}{3}$

  Therefore:

  $f(x) = \sum_{i=0}^{2} y_i \times l_i(x) = 94x^2 + 166x + 1234$

  Each party can compute $f(0)$ in order to obtain the secret, in this case $f(0) = 1234$.
\end{itemize}

It is evident, that in Shamir's scheme two points are sufficient to define a line $f(x) = ax + b$, three points are sufficient to define a parabola $f(x) = ax^2 + bx + c$, four points to define a cubic curve $f(x) = ax^3 + bx^2 + cx + d$ and so forth.
That is, it takes $T$ points to define a polynomial of degree $T-1$, where $T - 1$ will be the sufficient number of parties that can reconstructed the secret message.

\subsubsection{Threat Model}\label{sss:shamir-threat-model}
The Shamir secret sharing scheme can tolerate both passive and active adversaries, however in the latter case it has more strict bounds.
Shamir's sharing algorithm is secure against a passive adversary when $T < \cfrac{N}{2}$, while it achieves information-theoretic security for $T < \cfrac{N}{3}$ with an active adversary.
This means that even if the adversary has unbounded computational power, they cannot learn any information about the secret underlying a share.
The BGW \cite{brakerski2014leveled} protocol, which defines how to compute addition and multiplication on secret shares, is often used to compute functions with Shamir secret shares.



\subsection{Additive Secret Sharing}\label{ss:additive-secret-sharing}
Another form of secret sharing, and probably the simplest one, is additive sharing.
Again, a secret message $m$ is divided into $N$ parts, where each participant has its own unique part.
In contrast with Shamir's sharing algorithm, all parts are necessary in order to recover the original secret.

\subsubsection{Algorithm}\label{sss:additive-algorithm}
\begin{itemize}

  \item Dealer chooses a randomly $N - 1$ numbers such that $x_i \in \mathbb{Z}, i \in [1, N-1]$

  \item Computing $x_N$ from the random numbers is pretty trivial; $x_N = m - x_1 - x_2 - \dots - x_{N-1}$

  \item Finally, the dealer distributes the $N$ secrets ($x_1, \dots x_N$)

  \item In order to reconstruct the original message $m$, the parties have to combine their secrets: $m = x_1 + x_2 + \dots + x_N$
\end{itemize}

Seeing any $N-1$ values (\textit{i.e.} $x_1, \dots x_{N-1}$) does not give any clue about what $m$ could be, since the remaining $x_i$ may change the final result to any element of $\mathbb{Z}$ with equal probability.
More elaborate schemes than the $(\mathbb{Z}, +)$ have been introduced, in the form of $(A, \oplus)$ (which means in group $A$ using the operation $\oplus$), such as linear secret sharing.

There are many systems that have implemented various forms of SMPC with secret sharing schemes.
The most popular is SPDZ \cite{damgaard2012multiparty, damgaard2013practical}, which implements MPC with additive secret shares and is secure against active adversaries.
Another popular system that implements SMPC using additive secret shares is the Sharemind Secure Computing Platform, which we survey in section \ref{c:sharemind}.


\subsubsection{Threat Model}\label{sss:additive-threat-model}
In contrast to Shamir's secret sharing scheme, that can tolerate up to $T < \cfrac{N}{2}$ passive adversaries or $T < \cfrac{N}{3}$ active, as mentioned in \ref{sss:shamir-threat-model}, additive secret sharing schemes can tolerate the adversary controlling all but one party, that is $T < N$.
As we already mentioned, in order to reconstruct the original message $m$, all parties have to add their secrets ($m = x_1 + x_2 + \dots + x_N$).
It has become evident, that if one $x_i$ is missing, the initial message $m$ cannot be reconstructed.
% Additive schemes maintain security against a passive and active adversary with unbounded computational power.



\subsection{Secret Sharing Homomorphism}\label{ss:secret-sharing-homomorphism}
In \cite{benaloh1986secret}, Benaloh observed that many secret sharing schemes have a homomorphic property which allows multiple secrets to be combined by direct computation on shares.

Suppose we have a secret $m$ that can be computed from $T$ sub-secrets $\{m_i\}^T_{i=1}$ using a functions $f$ as follows $m = f(m_1, \dots, m_T)$.
Let $\oplus$ and $\otimes$ be binary functions on elements of the secret domain $S$ and of the share domain $T$, respectively.
We say that a $(k, N)$ threshold scheme has the $(\oplus, \otimes)$-homomorphism property (or is $(\oplus, \otimes)$-homomorphic) if for all $f: T^k \rightarrow S$, whenever a message

\hfil $m = f(m_1, \dots, m_k)$

and another message

\hfil  $m' = f(m'_1, \dots, m'_k)$

then the composition of the shares are the shares of the composition:

\hfil $m \oplus m' = f(m_1 \otimes m'_1, \dots, m_k \otimes m'_k)$


Shamir’s polynomial based secret sharing \ref{ss:shamir-secret-sharing} scheme is $(+, +)$-homomorphic since the sum of the polynomials use to share the sub-secrets is itself a polynomial that can be used to deal shares of the super secret.