General solution to the special problem of distributing shares using Shamir’s secret sharing scheme

In this paper, we solve the following problem. For a group of n participants, we need to distribute two shares to each of them in such a way that each pair of participants forms a (3, 4)-threshold access structure. In other words, each pair of participants can find some secret using any 3 out of the 4 shares they have. Obviously, this problem has a trivial solution: to share the same secret between everyone using a (3, 2n)-threshold secret sharing scheme. However, of theoretical and practical interest is the case when each pair of participants recovers a secret different from the others. In particular, the solution to this problem is necessary for the key agreement protocol proposed in [1]. In this paper, we find a complete solution to considered problem for Shamir’s secret sharing scheme. In addition, non-interactive methods for randomizing the key agreement protocol from [1] are studied. Unfortunately, it turns out that they do not enhance the security of this protocol.