Secret Sharing Schemes Based on Error-Correcting Codes

Abstract

In this thesis we present a new secret sharing scheme based on binary error-correcting codes, which can realize arbitrary (monotone or non-monotone) access structures. In this secret sharing scheme the secret is a codeword in a binary error-correcting code and the shares are binary words of the same length. When a group of participants wants to reconstruct the secret, the participants calculate the sum of their shares and apply Hamming decoding to that sum. The shares have the property that, when the group is authorized, the secret is the codeword which is closest to the sum of the shares. Otherwise, the sum differs strongly enough from the secret such that Hamming decoding yields another codeword. The shares can be described by the solutions of a system of linear equations which is closely related to first order Reed-Muller codes. We consider the case that there are only two different Hamming distances from the sums of the shares to the secret: one small distance k for the authorized sets and one large distance g for unauthorized sets. For this case a method of how to find suitable shares for arbitrary access structures is presented. In the resulting secret sharing scheme large code lengths are needed and the security distance g is rather small. In order to find classes of access structures which have more efficient and secure realizations, we classify the access structures such that all access structures of one class allow the same parameters g and k. Furthermore we study several changes in the access structure and their impact on the possible realizations. This gives rise to special classes of access structures defined by veto sets and necessary sets, which are particularly suitable for our approach.