# 17.1 Secret Splitting

The first situation that we present is the simplest. Consider the case where you have a message $M$, represented as an integer, that you would like to split between two people Alice and Bob in such a way that neither of them alone can reconstruct the message $M$. A solution to this problem readily lends itself: Give Alice a random integer $r$ and give Bob $M-r$. In order to reconstruct the message $M$, Alice and Bob simply add their pieces together.

A few technical problems arise from the fact that it is impossible to choose a random integer in a way that all integers are equally likely (the sum of the infinitely many equal probabilities, one for each integer, cannot equal 1). Therefore, we choose an integer $n$ larger than all possible messages $M$ that might occur and regard $M$ and $r$ as numbers mod $n$. Then there is no problem choosing $r$ as a random integer mod $n$; simply assign each integer mod $n$ the probability $1/n$.

Now let us examine the case where we would like to split the secret among three people, Alice, Bob, and Charles. Using the previous idea, we choose two random numbers $r$ and $s$ mod $n$ and give $M-r-s\text{\hspace{0.17em}}(\text{mod}\text{\hspace{0.17em}}n)$ to Alice, $r$ to Bob, and $s$ to Charles. To reconstruct the message $M$, Alice, Bob, and Charles simply add their respective numbers.

For the more general case, if we wish to split the secret $M$ among $m$ people, then we must choose $m-1$ random numbers ${r}_{1}\text{,}\text{}\dots \text{\hspace{0.17em}}\text{,}\text{}{r}_{m-1}$ mod $n$ and give them to $m-1$ of the people, and $M-\sum _{k=1}^{m-1}{r}_{k}\text{\hspace{0.17em}}(\text{mod}\text{\hspace{0.17em}}n)$ to the remaining person.