17.1 Secret Splitting – 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 Mr. 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 Mrs(modn) 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 m1 random numbers r1, , rm1 mod n and give them to m1 of the people, and Mk=1m1rk(modn) to the remaining person.