Introduction to Cryptography with Coding Theory, 3rd Edition

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